{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R679",
  "content_hash": null,
  "slug": "rsg-artifact-prefix-sieve-five-million",
  "type": "artifact",
  "title": "Exact square-divisor sieve and matching replay through five million",
  "summary": "Standard-library Python marks every prime-square multiple and uses augmenting paths to test distinct-prime assignments.",
  "relevance": "For Largest rainbow squarefree gap below 10^12, record rsg-artifact-prefix-sieve-five-million (“Exact square-divisor sieve and matching replay through five million”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python marks every prime-square multiple and uses augmenting paths to test distinct-prime assignments.",
  "relevance_source": "recorded",
  "body": "The program first sieves all primes through \\(\\sqrt{5{,}000{,}000}\\), then marks every integer divisible by each prime square. This classifies every integer in the range as squarefree or nonsquarefree. For every ordinary squarefree gap of endpoint distance at least 7, it reconstructs all square-prime divisors of the interior integers and runs exact bipartite matching.\n\nThe canonical report records 344 tested ordinary gaps, 33 successful rainbow gaps, and the first maximum witness. Its SHA-256 digest is `17402d48f264f6d7d21e35e8694a02ce0e88e17a386f2a0b2edef83fd5c87f3c`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all positive integers through 5000000 and every consecutive squarefree pair with upper endpoint in that interval",
    "bounds": {
      "n": {
        "min": 1,
        "max": 5000000
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_computation",
    "entrypoint": "join source_lines with newline and run with python3",
    "runtime": "CPython 3, standard library only",
    "citation": {
      "url": "https://arxiv.org/abs/1912.04972",
      "locator": "Self-contained Python standard-library replay executed by TheoremDB entry research on 2026-07-25"
    },
    "inline_source": [
      "from hashlib import sha256",
      "from json import dumps",
      "from math import isqrt",
      "",
      "LIMIT = 5_000_000",
      "WITNESS = (30_922, 30_929)",
      "",
      "prime_mark = bytearray(isqrt(LIMIT) + 1)",
      "primes = []",
      "for p in range(2, len(prime_mark)):",
      "    if prime_mark[p]:",
      "        continue",
      "    primes.append(p)",
      "    if p * p < len(prime_mark):",
      "        prime_mark[p * p :: p] = b\"\\1\" * (((len(prime_mark) - 1 - p * p) // p) + 1)",
      "",
      "nonsquarefree = bytearray(LIMIT + 1)",
      "for p in primes:",
      "    q = p * p",
      "    nonsquarefree[q :: q] = b\"\\1\" * (LIMIT // q)",
      "",
      "def square_primes(n):",
      "    out = []",
      "    for p in primes:",
      "        q = p * p",
      "        if q > n:",
      "            break",
      "        if n % q == 0:",
      "            out.append(p)",
      "    return out",
      "",
      "def matching(a, b):",
      "    choices = [square_primes(n) for n in range(a + 1, b)]",
      "    order = sorted(range(len(choices)), key=lambda i: (len(choices[i]), i))",
      "    owner = {}",
      "    assigned = [None] * len(choices)",
      "    def augment(i, seen):",
      "        for p in choices[i]:",
      "            if p in seen:",
      "                continue",
      "            seen.add(p)",
      "            j = owner.get(p)",
      "            if j is None or augment(j, seen):",
      "                owner[p] = i",
      "                assigned[i] = p",
      "                return True",
      "        return False",
      "    if all(augment(i, set()) for i in order):",
      "        return assigned",
      "    return None",
      "",
      "wa, wb = WITNESS",
      "assert not nonsquarefree[wa] and not nonsquarefree[wb]",
      "assert matching(wa, wb) == [17, 3, 5, 47, 13, 2]",
      "",
      "previous = 1",
      "long_gap_count = 0",
      "rainbow_gap_count = 0",
      "best = None",
      "for n in range(2, LIMIT + 1):",
      "    if nonsquarefree[n]:",
      "        continue",
      "    gap = n - previous",
      "    if gap >= 7:",
      "        long_gap_count += 1",
      "        assignment = matching(previous, n)",
      "        if assignment is not None:",
      "            rainbow_gap_count += 1",
      "            candidate = (gap, previous, n, assignment)",
      "            if best is None or candidate[0] > best[0]:",
      "                best = candidate",
      "    previous = n",
      "",
      "assert best == (7, 30_922, 30_929, [17, 3, 5, 47, 13, 2])",
      "report = {",
      "    \"best_assignment\": best[3],",
      "    \"best_endpoints\": [best[1], best[2]],",
      "    \"best_gap\": best[0],",
      "    \"limit\": LIMIT,",
      "    \"long_gap_count_gap_at_least_7\": long_gap_count,",
      "    \"rainbow_gap_count_gap_at_least_7\": rainbow_gap_count,",
      "}",
      "payload = dumps(report, sort_keys=True, separators=(\",\", \":\"))",
      "print(payload)",
      "print(\"report_sha256=\" + sha256(payload.encode()).hexdigest())"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1912.04972",
    "locator": "Self-contained Python standard-library replay executed by TheoremDB entry research on 2026-07-25"
  },
  "relations": [
    {
      "slug": "R682",
      "title": "The exact rainbow maximum through five million is 7",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "R683",
      "title": "The interval 30,922 to 30,929 has a six-color square-prime certificate",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "R681",
      "title": "Published squarefree-gap computations give the global upper bound 14",
      "object_type": "claim",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "rainbow-squarefree-gap-1e12",
      "title": "rainbow squarefree gap 1e12",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}