"""List all equal-radical block pairs in a specified gap interval, with no height cutoff.""" from argparse import ArgumentParser from functools import lru_cache from math import isqrt, prod @lru_cache(maxsize=None) def prime_divisors(n): factors = [] p = 2 while p * p <= n: if n % p == 0: factors.append(p) while n % p == 0: n //= p p = 3 if p == 2 else p + 2 if n > 1: factors.append(n) return tuple(factors) def prime_set(values): return sorted({p for v in values for p in prime_divisors(v)}) def smooth_radical(value, primes): radical = 1 for p in primes: if value % p: continue radical *= p while value % p == 0: value //= p return radical if value == 1 else None @lru_cache(maxsize=4096) def fundamental_pell_solution(D): root = isqrt(D) m, denominator, term = 0, 1, root old_p, p, old_q, q = 0, 1, 1, 0 while True: old_p, p = p, term * p + old_p old_q, q = q, term * q + old_q m = denominator * term - m denominator = (D - m * m) // denominator term = (root + m) // denominator if denominator == 1 and p * p - D * q * q == 1: return p, q def smooth_neighbors(primes): # Lehmer's Theorem 1 uses D=2*delta, including nonsquarefree D. deltas = [1] for p in primes: deltas += [p * d for d in deltas] max_index = max(3, (primes[-1] + 1) // 2) for delta in deltas: if delta == 2: continue D = 2 * delta a, b = fundamental_pell_solution(D) if smooth_radical(b, primes) is None: # b divides every later Pell y-coordinate continue u, v = 1, 0 for _ in range(max_index): u, v = a * u + D * b * v, b * u + a * v if smooth_radical(v, primes) is not None: yield (u - 1) // 2 def search(k, length, max_gap): solutions = [] for gap in range(k, max_gap + 1): options = [] for j in range(1, length): primes = prime_set(range(gap + j - k, gap + j + 1)) options.append((prod(primes), primes, gap + j)) for i in range(1, k): primes = prime_set(range(gap - i, gap - i + length + 1)) options.append((prod(primes), primes, i)) _, primes, offset = min(options) all_primes = prime_set(range(gap + 1 - k, gap + length)) for neighbor in smooth_neighbors(primes): x = neighbor - offset if x < 0: continue y = x + gap early = smooth_radical(prod(x + i for i in range(1, k + 1)), all_primes) if early is None: continue late = smooth_radical(prod(y + j for j in range(1, length + 1)), all_primes) if early == late: solutions.append((x, y)) return sorted(set(solutions)) if __name__ == "__main__": parser = ArgumentParser(description=__doc__) parser.add_argument("k", type=int, nargs="?", default=3) parser.add_argument("length", type=int, nargs="?", default=3) parser.add_argument("max_gap", type=int, nargs="?", default=1000) inputs = parser.parse_args() if not inputs.k >= inputs.length >= 3 or inputs.max_gap < inputs.k: parser.error("Supply earlier length >= later length >= 3 and gap bound >= earlier length.") assert len(set(smooth_neighbors([2, 3, 5, 7]))) == 23 results = search(inputs.k, inputs.length, inputs.max_gap) print(f"{len(results)} pairs for lengths {inputs.k}, {inputs.length} and gap <= {inputs.max_gap}") print(results)