{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R165",
  "content_hash": null,
  "slug": "csgf-artifact-exact-recurrence-30000",
  "type": "artifact",
  "title": "Exact recurrence sweep through 30,000",
  "summary": "Inline C++20 evaluates every legal split and mex directly, then compares all 30,000 values with the theorem.",
  "relevance": "This supplies a computation, dataset, or executable check used to assess the target problem.",
  "relevance_source": "derived",
  "body": "The program computes the Sprague-Grundy recurrence without using the proposed formula for its mex values. For each \\(n\\), it enumerates every unordered unequal split \\(a+(n-a)\\), tests the gcd condition, marks \\(g(a)\\mathbin{\\mathrm{xor}}g(n-a)\\), and takes the least unmarked nonnegative integer. A separate smallest-prime-factor sieve supplies the predicted value used only for comparison.\n\nAll values through 30,000 agree. The largest value in this interval is 3,244 at the prime 29,989. Compiled with Apple clang 21.0.0 using `c++ -std=c++20 -O3 -march=native -Wall -Wextra -pedantic`, the exact recurrence run took 6.57 seconds on an arm64 workstation. Its three-line output has SHA-256 digest `fbf61f7aefc06d57ab3b5adfc1bc01c915d3c1230ebae1a4ccdfae9a62bb323d`.",
  "status": "reproduced",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "every heap size from 1 through 30000 in the unequal coprime splitting game",
    "bounds": {
      "n": {
        "min": 1,
        "max": 30000
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "runnable",
    "kind": "inline_cpp20_computation",
    "command": "c++ -std=c++20 -O3 -march=native -Wall -Wextra -pedantic main.cpp -o coprime_game && ./coprime_game",
    "entrypoint": "Join source_lines with newline, compile with the command in metadata.execution, and run",
    "runtime": "C++20",
    "citation": {
      "url": "https://oeis.org/A055396",
      "locator": "Inline C++20 source below, compiled and executed on 2026-07-24"
    },
    "inline_source": [
      "#include <algorithm>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <numeric>",
      "#include <vector>",
      "",
      "int main() {",
      "    constexpr int limit = 30000;",
      "    std::vector<int> least_prime(limit + 1);",
      "    std::vector<int> prime_index(limit + 1);",
      "    int primes_seen = 0;",
      "    for (int n = 2; n <= limit; ++n) {",
      "        if (least_prime[n] == 0) {",
      "            least_prime[n] = n;",
      "            prime_index[n] = ++primes_seen;",
      "            if (static_cast<std::int64_t>(n) * n <= limit) {",
      "                for (int multiple = n * n; multiple <= limit; multiple += n) {",
      "                    if (least_prime[multiple] == 0) {",
      "                        least_prime[multiple] = n;",
      "                    }",
      "                }",
      "            }",
      "        }",
      "    }",
      "",
      "    std::vector<int> grundy(limit + 1);",
      "    std::vector<int> seen(limit + 1);",
      "    for (int n = 1; n <= limit; ++n) {",
      "        for (int a = 1; a < n - a; ++a) {",
      "            const int b = n - a;",
      "            if (std::gcd(a, b) == 1) {",
      "                seen[grundy[a] ^ grundy[b]] = n;",
      "            }",
      "        }",
      "        int mex = 0;",
      "        while (seen[mex] == n) {",
      "            ++mex;",
      "        }",
      "        grundy[n] = mex;",
      "        const int expected =",
      "            (n == 1 || n % 2 == 0) ? 0 : prime_index[least_prime[n]] - 1;",
      "        if (grundy[n] != expected) {",
      "            std::cout << \"mismatch \" << n << \" \" << grundy[n] << \" \"",
      "                      << expected << \"\\n\";",
      "            return 1;",
      "        }",
      "    }",
      "",
      "    const auto maximum = std::max_element(grundy.begin(), grundy.end());",
      "    std::cout << \"verified_through \" << limit << \"\\n\";",
      "    std::cout << \"maximum_grundy \" << *maximum << \" at \"",
      "              << std::distance(grundy.begin(), maximum) << \"\\n\";",
      "    std::cout << \"edge_values\";",
      "    for (int n : {1, 2, 3, 4, 5, 7, 9, 11, 25, 27, 49}) {",
      "        std::cout << \" \" << n << \":\" << grundy[n];",
      "    }",
      "    std::cout << \"\\n\";",
      "}"
    ],
    "missing": [
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://oeis.org/A055396",
    "locator": "Inline C++20 source below, compiled and executed on 2026-07-24"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R167",
      "title": "The least-prime-factor formula holds for every heap",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "R166",
      "title": "The Grundy sequence is a shifted A055396",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "coprime-splitting-grundy-formula",
      "title": "coprime splitting grundy formula",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}