#!/usr/bin/env python3 # --------------------------------------------------------------------------- # VERIFY_range.py # # Ancillary file for the paper # "Sums of three composite triangular numbers" # David Niedbala Giraudin, ORCID 0009-0009-1526-1178. # Technical assistance: Claude (Anthropic). # # Recomputes, for every n <= NMAX = 8.4 * 10**9, whether n is a sum of three # composite triangular numbers T_a + T_b + T_c (a, b, c >= 3), and checks that # the integers for which this fails are exactly the 41 values listed in the # paper. Two algorithms are available; they share no code except the exact # fallback test used on the rare survivors. # # METHOD "A". For each segment of n, the set of sums # of two composite triangular numbers is built on a window just below # the segment, and n is declared covered as soon as n - T_k lies in it # for one of the first K composite triangular numbers T_k. # # METHOD "B". The set of sums of two composite # triangular numbers is built once on [0, M0]. An integer n is declared # covered as soon as n - T_c lies in it for some c, which forces T_c to # be close to n. For n <= M0 this test is exhaustive. # # In both methods an integer that is not declared covered is passed to an # exact test, which tries every c. Every exception is therefore certified by # exhaustion. As a guard against a marking error in the fast stage, a few # integers declared covered in each segment are drawn at random and re-tested # with the exact routine. # # REQUIREMENTS: Python 3 with numpy only. No other dependency, no external # data, no intermediate files. Run as # python3 VERIFY_range.py (both methods, full range) # python3 VERIFY_range.py A (method A only) # python3 VERIFY_range.py B 1e8 (method B only, up to 10**8) # Memory: about 300 MB per worker. Time: a few minutes per method on two # cores at the full range; the second argument lowers the range for a quick # trial. # --------------------------------------------------------------------------- import sys import math import time import numpy as np from multiprocessing import Pool NMAX_FULL = 8400000000 # 8.4 * 10**9, the verified range of the paper SEG = 1 << 26 # segment length, 67 108 864 K_A = 64 # method A: number of small summands tried M0_B = 4000000 # method B: range of the two-term table EXPECTED = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 23, 24, 25, 28, 29, 32, 34, 38, 39, 43, 47, 50, 54, 60, 68, 69, 73, 95, 113, 194] KMAX = math.isqrt(2 * NMAX_FULL) + 3 TRI = np.array([k * (k + 1) // 2 for k in range(KMAX + 1)], dtype=np.int64) assert int(TRI[-1]) > NMAX_FULL assert int(TRI[3]) == 6 and int(TRI[4]) == 10 def is_tri(r): """r >= 0 is triangular iff 8r + 1 is a perfect square.""" s = math.isqrt(8 * r + 1) return s * s == 8 * r + 1 def in_S2(m): """Exact: m = T_a + T_b with 3 <= a <= b. Vectorised over a.""" if m < 12: return False amax = int(np.searchsorted(TRI, m // 2, side="right")) # T_a <= m/2 if amax <= 3: return False r = m - TRI[3:amax] # candidates T_b s = np.floor(np.sqrt((8 * r + 1).astype(np.float64))).astype(np.int64) for d in (-1, 0, 1): # guard rounding t = s + d if np.any(t * t == 8 * r + 1): return True return False def exact_ok(n): """Exact: n = T_a + T_b + T_c with a, b, c >= 3. Tries every c.""" c = 3 while int(TRI[c]) <= n - 12: if in_S2(n - int(TRI[c])): return True c += 1 return False SAMPLES = 24 # covered n re-tested exactly, per segment def spot_check(covered_mask, L, seed): """Re-test exactly a few n that the fast stage declared covered.""" idx = np.nonzero(covered_mask)[0] if len(idx) == 0: return 0 rng = np.random.default_rng(seed) pick = rng.choice(idx, size=min(SAMPLES, len(idx)), replace=False) bad = [int(i) + L for i in pick if not exact_ok(int(i) + L)] assert not bad, "fast stage declared covered: %s" % bad return len(pick) # ---------------------------------------------------------------- method A def segment_A(args): L, hi = args TK = int(TRI[K_A + 2]) # T_3, ..., T_{K+2}: K summands lo = L - TK S2w = np.zeros(hi - lo, dtype=bool) # S2 on [lo, hi) amax = int(np.searchsorted(TRI, (hi - 1) // 2, side="right")) a_idx = np.arange(3, max(amax, 3), dtype=np.int64) Ta = TRI[a_idx] b0 = np.searchsorted(TRI, lo - Ta, side="left") b0 = np.maximum(b0, a_idx) # b >= a b1 = np.searchsorted(TRI, hi - Ta, side="left") # T_a + T_b < hi for ta, x0, x1 in zip(Ta.tolist(), b0.tolist(), b1.tolist()): if x0 < x1: S2w[TRI[x0:x1] + (ta - lo)] = True width = hi - L unc = np.ones(width, dtype=bool) for k in range(3, K_A + 3): off = TK - int(TRI[k]) # index of n - T_k for n = L unc &= ~S2w[off:off + width] spot_check(~unc, L, L + 1) surv = (np.nonzero(unc)[0] + L).tolist() exc = [n for n in surv if not exact_ok(n)] return L, len(surv), exc # ---------------------------------------------------------------- method B S2SMALL = None def build_small(): t = np.zeros(M0_B + 1, dtype=bool) k = 3 while 2 * int(TRI[k]) <= M0_B: ta = int(TRI[k]) j1 = int(np.searchsorted(TRI, M0_B - ta, side="right")) if j1 > k: t[TRI[k:j1] + ta] = True k += 1 return t def init_B(): global S2SMALL S2SMALL = build_small() def segment_B(args): L, hi = args width = hi - L cov = np.zeros(width, dtype=bool) c0 = max(3, int(np.searchsorted(TRI, L - M0_B, side="left"))) c1 = int(np.searchsorted(TRI, hi - 12, side="left")) for c in range(c0, c1): tc = int(TRI[c]) mlo = max(0, L - tc) mhi = min(M0_B, hi - 1 - tc) if mlo > mhi: continue cov[tc + mlo - L: tc + mhi - L + 1] |= S2SMALL[mlo:mhi + 1] spot_check(cov, L, L + 2) surv = (np.nonzero(~cov)[0] + L).tolist() exc = [n for n in surv if not exact_ok(n)] return L, len(surv), exc # ---------------------------------------------------------------- driver def run(method, nmax, workers): segs = [] L = 0 while L <= nmax: hi = min(L + SEG, nmax + 1) segs.append((L, hi)) L = hi func = segment_A if method == "A" else segment_B init = init_B if method == "B" else None t0 = time.time() exc_all = [] surv_all = 0 done = 0 with Pool(workers, initializer=init) as pool: for L, ns, exc in pool.imap(func, segs): exc_all.extend(exc) surv_all += ns done += 1 if done % 10 == 0 or done == len(segs): print(" method %s : %4d / %d segments, up to n = %.3e, " "%.0fs" % (method, done, len(segs), float(segs[done - 1][1] - 1), time.time() - t0), flush=True) exc_all.sort() print(" method %s : survivors passed to the exact test : %d" % (method, surv_all), flush=True) print(" method %s : exceptions found : %d" % (method, len(exc_all)), flush=True) print(" %s" % exc_all, flush=True) ok = exc_all == [n for n in EXPECTED if n <= nmax] print(" method %s : %s" % (method, "MATCHES the list of the paper" if ok else "MISMATCH - please report"), flush=True) return ok if __name__ == "__main__": methods = ["A", "B"] nmax = NMAX_FULL if len(sys.argv) > 1: methods = [sys.argv[1].upper()] if len(sys.argv) > 2: nmax = min(int(float(sys.argv[2])), NMAX_FULL) workers = max(1, min(4, (__import__("os").cpu_count() or 1))) print("=" * 72, flush=True) print("VERIFY_range - sums of three composite triangular numbers", flush=True) print("range n <= %d, methods %s, %d worker(s)" % (nmax, methods, workers), flush=True) print("=" * 72, flush=True) # self test of the exact routines on the small range small = [n for n in range(0, 2000) if not exact_ok(n)] assert small == EXPECTED, small print("self test: exact routine gives the 41 exceptions below 2000", flush=True) res = [run(m, nmax, workers) for m in methods] print("=" * 72, flush=True) print("ALL METHODS AGREE WITH THE PAPER" if all(res) else "DISAGREEMENT - please report", flush=True) print("=" * 72, flush=True)