How to resolve the algorithm Mian-Chowla sequence step by step in the C programming language
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()
, andfree()
.
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 themc
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
ton-1
to generate the sequence:- Sets a lower bound
le
forj
based on the previousmc[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]
andj
(i.e.,sum
) does not exist in thesums
list. - The potential sums of pairs involving
j
and elements ofmc
(fromk=0
toi
) are not already insums
.
- The sum of the current
- Once a suitable
j
is found, addsj
tomc[i]
and updates thesums
list.
- Sets a lower bound
3. Contains() Function:
- Checks if a given item
item
exists in a listlst
of sizesize
. - Iterates through the list from the last element to the first element, and returns
true
ifitem
is found. Otherwise, returnsfalse
.
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