#!/usr/bin/env python3 # --------------------------------------------------------------------------- # VERIFY_composite_triangular.py # # Independent verifier for the paper # "Sums of three composite triangular numbers" # # David Niedbala Giraudin, ORCID 0009-0009-1526-1178. # Technical assistance: Claude (Anthropic). # # A triangular number T_k = k(k+1)/2 is composite for every k >= 3; the only # non-composite ones are T_0 = 0, T_1 = 1 and T_2 = 3. This file checks the # records of D, the constants of the analytic chain, the class number # identities, and the exceptional set up to LIMIT. The exceptional set up to # 8.4 * 10**9 is recomputed by the companion file VERIFY_range.py. # # REQUIREMENTS: Python 3 with numpy ONLY. No scipy, no external data, no # intermediate files. Just run it (no command line arguments). # # All parameters are fixed below. Output is flushed line by line so the run # can be followed, and so a truncated run still shows what was completed. # --------------------------------------------------------------------------- import numpy as np import math import time # ----------------------------- PARAMETERS ---------------------------------- # Part 1 sieve limit. Memory is about 2 bytes per integer below the limit. # 2 * 10**7 -> about 40 MB, a few seconds # 1 * 10**8 -> about 200 MB, under a minute on a fast machine # Raise only if the machine has the room; the announced figure is printed # before any allocation is made. LIMIT = 2 * 10**7 # Part 1 skips entirely if the predicted memory exceeds this budget, in MB. MEMORY_BUDGET_MB = 600 # Number of leading composite triangular numbers used in the sieve stage. SIEVE_DEPTH = 45 # Part 4 range for the class number identity r_3(N) = 24 h(-N). CLASS_CHECK_LIMIT = 2000 # --------------------------------------------------------------------------- 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] def tri(k): return int(k) * (int(k) + 1) // 2 # --------------------------- SELF TEST ------------------------------------- # Guards against a notebook preparser turning integer literals into a type # with different semantics, and against "**" being read as anything else. def self_test(): assert tri(3) == 6 and tri(10) == 55, "triangular numbers wrong" assert int(2) ** int(10) == 1024, "exponentiation wrong" assert int(7) // int(2) == 3, "integer division wrong" assert math.isqrt(10**12) == 10**6, "isqrt wrong" a = np.arange(5, dtype=np.int64) assert int((a * a).sum()) == 30, "numpy arithmetic wrong" assert float(1) / float(4) == 0.25, "float division wrong" return True print("=" * 72, flush=True) print("VERIFIER - sums of three composite triangular numbers", flush=True) print("=" * 72, flush=True) if not self_test(): raise SystemExit("self test failed - aborting") print("self test passed", flush=True) print("", flush=True) # =========================================================================== # PART 1. The exceptional set below LIMIT. # =========================================================================== print("PART 1 - exceptional set below %d" % LIMIT, flush=True) predicted_mb = 2.0 * float(LIMIT) / float(10**6) print(" predicted memory: about %.0f MB (budget %d MB)" % (predicted_mb, MEMORY_BUDGET_MB), flush=True) if predicted_mb > float(MEMORY_BUDGET_MB): print(" SKIPPED: predicted memory exceeds the budget.", flush=True) print(" Lower LIMIT at the top of this file and run again.", flush=True) else: t0 = time.time() tris = [] k = 3 while tri(k) <= LIMIT: tris.append(tri(k)) k += 1 T = np.array(tris, dtype=np.int64) print(" composite triangular numbers up to the limit: %d" % len(T), flush=True) # S2[m] = True iff m = T_a + T_b with a, b >= 3 S2 = np.zeros(LIMIT + 1, dtype=bool) for t in T: rest = T[T <= LIMIT - t] if len(rest) == 0: break S2[rest + t] = True print(" two-term table built, density %.4f, %.1fs" % (float(S2.mean()), time.time() - t0), flush=True) # eliminate by the leading SIEVE_DEPTH composite triangular numbers uncovered = np.ones(LIMIT + 1, dtype=bool) for i in range(min(SIEVE_DEPTH, len(T))): t = int(T[i]) uncovered[t:] &= ~S2[:LIMIT + 1 - t] cand = np.nonzero(uncovered)[0] print(" survivors of the sieve stage: %d, %.1fs" % (len(cand), time.time() - t0), flush=True) # exact test on the survivors found = [] for n in cand: n = int(n) ok = False for t in T: t = int(t) if t > n - 12: break if S2[n - t]: ok = True break if not ok: found.append(n) print(" exceptions found: %d" % len(found), flush=True) print(" %s" % found, flush=True) expected_here = [n for n in EXPECTED if n <= LIMIT] if found == expected_here: print(" MATCHES the list published in the paper.", flush=True) else: print(" MISMATCH with the published list - please report.", flush=True) print(" elapsed %.1fs" % (time.time() - t0), flush=True) print("", flush=True) # =========================================================================== # PART 2. The function D(Y) = max over M <= Y of the product of (e_p + 1) # taken over the primes p = 1 mod 4 dividing M. # =========================================================================== print("PART 2 - records of D(Y)", flush=True) t0 = time.time() PRIMES_1MOD4 = [p for p in range(5, 500) if p % 4 == 1 and all(p % d for d in range(2, int(p ** 0.5) + 1))] DFS_LIMIT = 10**13 best = {} def dfs(i, M, v, emax): if v > best.get(M, 0): best[M] = v if i >= len(PRIMES_1MOD4): return p = PRIMES_1MOD4[i] e = 1 q = p while M * q <= DFS_LIMIT and e <= emax: dfs(i + 1, M * q, v * (e + 1), e) e += 1 q *= p dfs(0, 1, 1, 64) records = [] cur = 0 for M, v in sorted(best.items()): if v > cur: records.append((M, v)) cur = v print(" records (smallest M reaching each value):", flush=True) for M, v in records: print(" M = %-18d D = %d" % (M, v), flush=True) # cross check against an exhaustive scan at a smaller bound SMALL = 10**6 spf = np.arange(SMALL + 1, dtype=np.int64) for p in range(2, int(SMALL ** 0.5) + 1): if int(spf[p]) == p: seg = spf[p * p::p] spf[p * p::p] = np.where(seg == np.arange(p * p, SMALL + 1, p), p, seg) mx = 0 for M in range(1, SMALL + 1): m = M v = 1 while m > 1: p = int(spf[m]) e = 0 while m % p == 0: m //= p e += 1 if p % 4 == 1: v *= (e + 1) if v > mx: mx = v dfs_small = max(v for M, v in best.items() if M <= SMALL) print(" cross check at Y = %d : search tree gives %d, exhaustive scan gives %d" % (SMALL, dfs_small, mx), flush=True) print(" agreement: %s (%.1fs)" % (dfs_small == mx, time.time() - t0), flush=True) print("", flush=True) # =========================================================================== # PART 3. The analytic chain, in 50-digit decimal arithmetic. # Every rounding is made in the unfavourable direction: pi is # replaced by an upper bound, so the class number lower bound # A * N**(1/2 - eps) is never overstated. # =========================================================================== print("PART 3 - analytic chain", flush=True) from decimal import Decimal, getcontext getcontext().prec = 50 PI_UP = Decimal("3.14159265358979323847") # pi < PI_UP EPS = Decimal(1) / Decimal(20) A_CONST = Decimal("0.655") * EPS / PI_UP # h(-N0) > A * N0**0.45 EXPO = Decimal("0.5") - EPS print(" eps = 1/20 ; Tatuzawa needs 0 < eps < 1/2 : %s" % (EPS < Decimal("0.5")), flush=True) E20 = (Decimal(1) / EPS).exp() print(" validity threshold max(exp(1/eps), exp(11.2)) = %.4e" % float(max(E20, Decimal("11.2").exp())), flush=True) print(" A = 0.655 eps / pi >= %s" % str(A_CONST)[:14], flush=True) # the exact records around 192, re-derived from their factorisations def d_value(M): v = 1 m = M p = 2 while p * p <= m: e = 0 while m % p == 0: m //= p e += 1 if p % 4 == 1: v *= (e + 1) p += 1 if m > 1 and m % 4 == 1: v *= 2 return v M_192 = [M for M, v in records if v == 192][0] M_NEXT = [M for M, v in records if v > 192][0] assert d_value(M_192) == 192 and d_value(M_NEXT) == 216 print(" D(Y) <= 192 for every Y < %d (D(%d) = %d)" % (M_NEXT, M_NEXT, d_value(M_NEXT)), flush=True) # Range 2 : h > 3 * 192 = 576 N2 = (Decimal(576) / A_CONST) ** (Decimal(1) / EXPO) print(" Range 2 : condition holds for N > %.6e (n > %.6e)" % (float(N2), float((N2 - 3) / 8)), flush=True) # Range 1 : uniform bound D(Y) <= g(t) * Y**t N1 = {} for tt in ("0.2",): t = Decimal(tt) g = Decimal(1) for p in PRIMES_1MOD4: pt = Decimal(p) ** t if pt >= 2: break g *= max(Decimal(e + 1) / pt ** e for e in range(0, 400)) ex = EXPO - t N1[tt] = (Decimal(3) * g / (A_CONST * Decimal(2) ** t)) ** (Decimal(1) / ex) print(" Range 1, t = %-4s : g(t) = %s -> condition holds for N > %.6e" % (tt, str(g)[:8], float(N1[tt])), flush=True) # closure of the chain NV = Decimal(8) * Decimal(8400000000) + 3 # Range 3, by VERIFY_range.py assert NV > N2, "Ranges 2 and 3 do not overlap" assert (N1["0.2"] - 1) / 2 < M_NEXT, "D <= 192 does not reach Range 1" print(" Range 3 (VERIFY_range.py) reaches N = %d" % NV, flush=True) print(" overlap of Ranges 3 and 2 : factor %s" % str(NV / N2)[:8], flush=True) print(" Range 2 is valid up to N = %.4e, beyond the start %.4e of Range 1" % (float(2 * M_NEXT - 1), float(N1["0.2"])), flush=True) for f in (3, 5): c = Decimal(f) * Decimal(f) ** (-2 * EXPO) assert c > 1 print(" conductor %d : H(N) >= %d h(-N/%d) gives the factor %s > 1" % (f, f, f * f, str(c)[:7]), flush=True) assert N2 / (f * f) > E20 print(" the chain closes.", flush=True) print("", flush=True) # =========================================================================== # PART 4. Class number identities used in the counting step. # =========================================================================== print("PART 4 - class number identities", flush=True) t0 = time.time() def r3(N): c = 0 L = math.isqrt(N) for x in range(-L, L + 1): R = N - x * x if R < 0: continue M = math.isqrt(R) for y in range(-M, M + 1): z2 = R - y * y if z2 < 0: continue z = math.isqrt(z2) if z * z == z2: c += 1 if z == 0 else 2 return c def hclass(D): cnt = 0 B = math.isqrt(-D // 3) for b in range(-B, B + 1): if (b * b - D) % 4: continue ac = (b * b - D) // 4 for a in range(max(1, abs(b)), math.isqrt(ac) + 1): if ac % a: continue c = ac // a if a > c or abs(b) > a: continue if (abs(b) == a or a == c) and b < 0: continue cnt += 1 return cnt def squarefree_odd(n): d = 3 while d * d <= n: if n % (d * d) == 0: return False d += 2 return True def kron(D, p): r = D % p if r == 0: return 0 return 1 if pow(r, (p - 1) // 2, p) == 1 else -1 bad = [] for N in range(11, CLASS_CHECK_LIMIT, 8): if not squarefree_odd(N): continue if r3(N) != 24 * hclass(-N): bad.append(N) print(" r_3(N) = 24 h(-N) for N = 3 mod 8 squarefree: %s" % ("no discrepancy" if not bad else bad), flush=True) bad = [] for N0 in range(11, 400, 8): if not squarefree_odd(N0): continue if r3(9 * N0) != 24 * hclass(-N0) * (4 - kron(-N0, 3)): bad.append(N0) print(" r_3(9 N0) = 24 h(-N0) (4 - (D|3)): %s" % ("no discrepancy" if not bad else bad), flush=True) bad = [] for N0 in range(11, 200, 8): if not squarefree_odd(N0): continue if r3(25 * N0) != 24 * hclass(-N0) * (6 - kron(-N0, 5)): bad.append(N0) print(" r_3(25 N0) = 24 h(-N0) (6 - (D|5)): %s" % ("no discrepancy" if not bad else bad), flush=True) print(" elapsed %.1fs" % (time.time() - t0), flush=True) print("", flush=True) print("=" * 72, flush=True) print("verification complete", flush=True) print("=" * 72, flush=True)