"""Finite checks for the Erdős 137 long-block note. Run with Python 3.""" from math import isqrt def sieve(limit): least = list(range(limit + 1)) for p in range(2, isqrt(limit) + 1): if least[p] == p: for multiple in range(p * p, limit + 1, p): if least[multiple] == multiple: least[multiple] = p primes = [p for p in range(2, limit + 1) if least[p] == p] pi = [0] * (limit + 1) factors = [[] for _ in range(limit + 1)] for n in range(2, limit + 1): pi[n] = pi[n - 1] + (least[n] == n) value = n while value > 1: p = least[value] exponent = 0 while value % p == 0: value //= p exponent += 1 factors[n].append((p, exponent)) return primes, pi, factors def count_windows(length, last_start, factors): """Return the exact exponent-one count after each one-place shift.""" valuations = {} singletons = 0 def change(value, sign): nonlocal singletons for prime, exponent in factors[value]: old = valuations.get(prime, 0) new = old + sign * exponent assert new >= 0 valuations[prime] = new singletons += (new == 1) - (old == 1) for value in range(1, length + 1): change(value, 1) yield singletons for start in range(1, last_start + 1): change(start, -1) change(start + length, 1) yield singletons def main(): max_length, last_start = 256, 8192 primes, pi, factors = sieve(last_start + max_length) # Laishram's R_j < p_(3j) guarantees the infinite suffix minimum has # already been reached for every target length in this finite check. j = pi[max_length] + 1 boundary = primes[3 * j - 1] suffix = [0] * (boundary + 1) smallest = j for t in range(boundary, 0, -1): smallest = min(smallest, pi[t] - pi[t // 2]) suffix[t] = smallest assert [t for t in range(1, 42) if suffix[t] > suffix[t - 1]] == [2, 11, 17, 29, 41] assert list(count_windows(8, 2, factors)) == [2, 2, 1] failures = [] largest_loss = (0, 0, 0) for length in range(1, max_length + 1): counts = list(count_windows(length, last_start, factors)) for start in range(length // 2 + 1): end = length + start assert counts[start] == pi[end] - pi[end // 2] best = min(counts) if best != suffix[length]: failures.append((length, best, suffix[length])) loss = counts[0] - best if loss > largest_loss[0]: largest_loss = (loss, length, counts.index(best)) print(f"Checked {max_length * (last_start + 1):,} blocks.") print("Differences (length, finite minimum, Ramanujan count):", failures) print("Largest factorial excess (excess, length, earliest offset):", largest_loss) if __name__ == "__main__": main()