How to resolve the algorithm Mian-Chowla sequence step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Mian-Chowla sequence step by step in the C programming language

Table of Contents

Problem Statement

The Mian–Chowla sequence is an integer sequence defined recursively.

Mian–Chowla is an infinite instance of a Sidon sequence, and belongs to the class known as B₂ sequences.

The sequence starts with: then for n > 1, an is the smallest positive integer such that every pairwise sum is distinct, for all i and j less than or equal to n.

Demonstrating working through the first few terms longhand: Speculatively try a2 = 2 There are no repeated sums so 2 is the next number in the sequence. Speculatively try a3 = 3 Sum of 4 is repeated so 3 is rejected. Speculatively try a3 = 4 There are no repeated sums so 4 is the next number in the sequence. And so on...

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Mian-Chowla sequence step by step in the C programming language

Explanation:

This code generates and displays the Mian-Chowla sequence, a sequence of positive integers with specific properties.

Key Features:

  • MianChowla() function: Generates the Mian-Chowla sequence.
  • Contains() function: Checks if a given item exists in a list.
  • Memory allocation and deallocation: Dynamically allocates and releases memory using malloc(), realloc(), and free().

How it works:

1. Main Function:

  • Sets n to be the desired length of the sequence (default: 100).
  • Calls MianChowla() to generate the sequence and stores it in the mc array.
  • Prints the first 30 and 91-100th terms of the sequence.

2. MianChowla() Function:

  • Initializes the first element of mc to 1.
  • Creates a list sums to store potential sums of pairs of numbers.
  • Iterates from i = 1 to n-1 to generate the sequence:
    • Sets a lower bound le for j based on the previous mc[i-1].
    • Iterates through potential values of j until a suitable value is found that satisfies the following conditions:
      • The sum of the current mc[i] and j (i.e., sum) does not exist in the sums list.
      • The potential sums of pairs involving j and elements of mc (from k=0 to i) are not already in sums.
    • Once a suitable j is found, adds j to mc[i] and updates the sums list.

3. Contains() Function:

  • Checks if a given item item exists in a list lst of size size.
  • Iterates through the list from the last element to the first element, and returns true if item is found. Otherwise, returns false.

4. Memory Management:

  • In the second version of the code, dynamic memory allocation and deallocation are used to adjust the size of the isSum array as needed.
  • This allows for efficient handling of larger sequences and avoids memory limitations.

5. Performance Measurement:

  • The code calculates the computation time using clock() and prints the elapsed time in milliseconds.
  • In addition, it estimates the memory allocation for the isSum array and prints it in a human-readable format.

Source code in the c programming language

#include <stdio.h>
#include <stdbool.h>
#include <time.h>
 
#define n 100
#define nn ((n * (n + 1)) >> 1)

bool Contains(int lst[], int item, int size) {
	for (int i = size - 1; i >= 0; i--)
 		if (item == lst[i]) return true;
	return false;
}
 
int * MianChowla()
{
	static int mc[n]; mc[0] = 1;
	int sums[nn];	sums[0] = 2;
	int sum, le, ss = 1;
	for (int i = 1; i < n; i++) {
		le = ss;
		for (int j = mc[i - 1] + 1; ; j++) {
			mc[i] = j;
			for (int k = 0; k <= i; k++) {
				sum = mc[k] + j;
				if (Contains(sums, sum, ss)) {
					ss = le; goto nxtJ;
				}
				sums[ss++] = sum;
			}
			break;
		nxtJ:;
		}
	}
	return mc;
}
 
int main() {
	clock_t st = clock(); int * mc; mc = MianChowla();
        double et = ((double)(clock() - st)) / CLOCKS_PER_SEC;
	printf("The first 30 terms of the Mian-Chowla sequence are:\n");
	for (int i = 0; i < 30; i++) printf("%d ", mc[i]);
	printf("\n\nTerms 91 to 100 of the Mian-Chowla sequence are:\n");
	for (int i = 90; i < 100; i++) printf("%d ", mc[i]); 
	printf("\n\nComputation time was %f seconds.", et);
}


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

// helper function for indicating memory used.
void approx(char* buf, double count)
{
    const char* suffixes[] = { "Bytes", "KiB", "MiB" };
    uint s = 0; 
    while (count >= 1024 && s < 3) { s++; count /= 1024; }
    if (count - (double)((int)count) == 0.0)
        sprintf(buf, "%d %s", (int)count, suffixes[s]);
    else
        sprintf(buf, "%.1f %s", count, suffixes[s]);
}

int main() {
    int i, j, k, c = 0, n = 100, nn = 110;
    int* mc = (int*) malloc((n) * sizeof(int));
    bool* isSum = (bool*) calloc(nn, sizeof(bool));
    char em[] = "unable to increase isSum array to %ld.";
    if (n > 100)  printf("Computing terms 1 to %d...\n", n);
    clock_t st = clock();
    for (i = 1; c < n; i++) {
        mc[c] = i;
        if (i + i > nn) {
            bool* newIs = (bool*)realloc(isSum, (nn <<= 1) * sizeof(bool));
            if (newIs == NULL) { printf(em, nn); return -1; }
            isSum = newIs;
            for (j = (nn >> 1); j < nn; j++) isSum[j] = false;
        }
        bool isUnique = true;
        for (j = 0; (j < c) && isUnique; j++) isUnique = !isSum[i + mc[j]];
        if (isUnique) {
            for (k = 1; k <= c; k++) isSum[i + mc[k]] = true;
            c++;
        }
    }
    double et = 1e3 * ((double)(clock() - st)) / CLOCKS_PER_SEC;
    free(isSum);
    printf("The first 30 terms of the Mian-Chowla sequence are:\n");
    for (i = 0; i < 30; i++) printf("%d ", mc[i]);
    printf("\n\nTerms 91 to 100 of the Mian-Chowla sequence are:\n");
    for (i = 90; i < 100; i++) printf("%d ", mc[i]);
    if (c > 100) printf("\nTerm %d is: %d" ,c , mc[c - 1]);
    free(mc);
    char buf[100]; approx(buf, nn * sizeof(bool));
    printf("\n\nComputation time was %6.3f ms.  Allocation was %s.", et, buf);
}


  

You may also check:How to resolve the algorithm Averages/Root mean square step by step in the APL programming language
You may also check:How to resolve the algorithm Documentation step by step in the Lambdatalk programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Simula programming language
You may also check:How to resolve the algorithm Sum digits of an integer step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Integer sequence step by step in the Fermat programming language