"""Find equal prime supports for disjoint blocks; starts count from one.""" from functools import lru_cache from itertools import combinations from math import isqrt import sys import numpy as np def primes_through(limit): flags = np.ones(limit + 1, dtype=bool) flags[:2] = False for p in range(2, isqrt(limit) + 1): if flags[p]: flags[p * p :: p] = False return np.flatnonzero(flags) def prime_hashes(primes): values = primes.astype(np.uint64) + np.uint64(0x9E3779B97F4A7C15) values = (values ^ (values >> 30)) * np.uint64(0xBF58476D1CE4E5B9) values = (values ^ (values >> 27)) * np.uint64(0x94D049BB133111EB) return values ^ (values >> 31) def block_signatures(limit, longest, primes): tags = prime_hashes(primes) prefix = np.zeros(limit + longest, dtype=np.uint64) for prime, tag in zip(primes, tags): prefix[prime::prime] += tag np.cumsum(prefix, out=prefix) signatures = np.empty((longest - 2, limit), dtype=np.uint64) for length, row in enumerate(signatures, 3): np.subtract(prefix[length : length + limit], prefix[:limit], out=row) for prime, tag in zip(primes, tags): if prime >= length: break for residue in range(prime): duplicates = (residue + length) // prime - 1 if duplicates: correction = (int(tag) * int(duplicates)) % (1 << 64) row[residue::prime] -= np.uint64(correction) return signatures.ravel() def exact_block_supports(primes): @lru_cache(maxsize=None) def factors(value): result = set() for prime in primes: if prime * prime > value: break if value % prime == 0: result.add(prime) while value % prime == 0: value //= prime if value > 1: result.add(value) return frozenset(result) @lru_cache(maxsize=None) def support(start, length): return frozenset().union(*(factors(n) for n in range(start, start + length))) return support def census(limit, longest): primes = primes_through(limit + longest - 1) support = exact_block_supports(primes[primes <= isqrt(limit + longest - 1)].tolist()) signatures = block_signatures(limit, longest, primes) order = np.argsort(signatures, kind="stable") sorted_tags = signatures[order] del signatures repeats = np.flatnonzero(sorted_tags[:-1] == sorted_tags[1:]) pairs = [] for run in np.split(repeats, np.flatnonzero(np.diff(repeats) != 1) + 1): if not run.size: continue blocks = [] for index in order[run[0] : run[-1] + 2]: length_index, start_index = divmod(int(index), limit) blocks.append((start_index + 1, length_index + 3)) for (x, k), (y, ell) in combinations(sorted(blocks), 2): if x + k <= y and k >= ell and support(x, k) == support(y, ell): pairs.append((k, ell, x, y)) return sorted(pairs) def check(): limit, longest = 80, 7 support = exact_block_supports([2, 3, 5, 7]) expected = [ (k, ell, x, y) for k in range(3, longest + 1) for ell in range(3, k + 1) for x in range(1, limit + 1) for y in range(x + k, limit + 1) if support(x, k) == support(y, ell) ] assert census(limit, longest) == expected assert (3, 3, 14, 48) in expected if __name__ == "__main__": check() limit, longest = map(int, sys.argv[1:]) if limit < 1 or longest < 3: raise ValueError("The start limit must be positive and the longest block at least three.") for row in census(limit, longest): print(*row)