#!/usr/bin/env python3 """job2723 tests: exact engines vs reference values, and the proven GAP bound. Run: ./.venv/bin/python3 -m unittest discover outputs/job2723 """ import sys, os, itertools, unittest from fractions import Fraction from math import prod sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import kstar_bounds as kb class ReferenceValues(unittest.TestCase): """Pin the corpus / library reference values for the exact engine.""" def test_library_reference_210_11_13(self): # .solveathome/private/lib/covering tests pin K*(210,[11,13]) = 3 self.assertEqual(kb.exact_fullperiod(210, [11, 13]), 3) def test_library_reference_210_11_alone(self): self.assertEqual(kb.exact_fullperiod(210, [11]), 1) def test_tile_slots_small(self): self.assertEqual(kb.tile_slots(30), [11, 17, 29]) self.assertEqual(len(kb.tile_slots(210)), 15) def test_corridor_small_table(self): # exact values computed here, cross-checked against the corpus route-026 # table by killer set Q (P = 210 rows: {11,13}->3, {11,13,17}->5, # {11,13,17,19}->8; P = 2310 row {13,17,19}->6). self.assertEqual(kb.exact_fullperiod(210, [11, 13]), 3) self.assertEqual(kb.exact_fullperiod(210, [11, 13, 17]), 5) self.assertEqual(kb.exact_fullperiod(210, [11, 13, 17, 19]), 8) self.assertEqual(kb.exact_fullperiod(2310, [13, 17, 19]), 6) def test_monotone_under_killer_set(self): # fold-entry jump law: K*(Q u {q}) >= K*(Q) (monotonicity) base = kb.exact_fullperiod(210, [11, 13]) for extra in ([17], [19], [17, 19]): self.assertGreaterEqual(kb.exact_fullperiod(210, [11, 13] + extra), base) class GapBoundHoldsOnAllSmallCases(unittest.TestCase): """The GAP bound is an UPPER bound: it must never be beaten by an exact value. Exhaustive over small tile moduli and killer sets. """ def test_exhaustive_small(self): checked = 0 for P in (30, 210): for size in (1, 2, 3): avail = [q for q in kb.primes_upto(29) if gcd_ok(q, P)] for Q in itertools.combinations(avail, size): if prod(Q) * len(kb.tile_slots(P)) > 30_000_000: continue exact = kb.exact_fullperiod(P, list(Q)) bound = kb.gap_bound(P, list(Q)) with self.subTest(P=P, Q=Q): if bound >= 0: self.assertLessEqual(exact, bound, f"GAP bound beaten: P={P} Q={Q} " f"exact={exact} bound={bound}") checked += 1 self.assertGreater(checked, 20) def test_corridor_is_exactly_saturated(self): # FINDING: every corridor row already has G * sum_q 1/q > 1, so the GAP # bound returns -1 (no information). This is the saturation that closes # the whole density/capacity class here; it is asserted, not worked around. for s in (7, 9, 10, 11, 13): P, Q = kb.corridor(s) if prod(Q) * len(kb.tile_slots(P)) > 5_000_000: continue G = kb.max_slot_gap(P) S = sum(Fraction(1, q) for q in Q) with self.subTest(s=s): self.assertGreater(G * S, 1, f"corridor row s={s} is NOT saturated: G={G}") self.assertEqual(kb.gap_bound(P, Q), -1) # exact value is much smaller than the raw counting numerator self.assertLessEqual(kb.exact_fullperiod(P, Q), 2 * len(Q) * G) def gcd_ok(q, P): from math import gcd return gcd(q, P) == 1 if __name__ == "__main__": unittest.main(verbosity=2)