{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R64",
  "content_hash": null,
  "slug": "bdr1m-artifact-exact-prefix-sweep",
  "type": "artifact",
  "title": "Exact 100-million-state binomial recurrence sweep",
  "summary": "C++ updates prime exponents and the arbitrary-precision divisor count using exact small-integer multiplication and division.",
  "relevance": "For Most divisors of a binomial coefficient with top at most 10^6, record bdr1m-artifact-exact-prefix-sweep (“Exact 100-million-state binomial recurrence sweep”) supplies evidence or a replay used to check the packet. The record states: C++ updates prime exponents and the arbitrary-precision divisor count using exact small-integer multiplication and division.",
  "relevance_source": "recorded",
  "body": "For each fixed \\(n\\), the program starts at \\(\\binom n0=1\\) and applies\n\\[\n\\binom nk=\\binom n{k-1}\\frac{n-k+1}{k}.\n\\]\nA smallest-prime-factor sieve decomposes both update terms. When an exponent changes from \\(e\\) to \\(e'\\), the program replaces the divisor-count factor \\(e+1\\) by \\(e'+1\\). Its base-\\(10^9\\) integer class performs every division exactly and aborts on a remainder or a negative binomial exponent.\n\nThe sweep visits exactly 100,000,000 states and performs 490,041,974 prime-exponent updates. It hashes each row maximum, its location, and its decimal length in increasing row order. The final FNV-1a value is `15944218793165208384`. The one-line standard output has SHA-256 digest `acd2be4af4c40571118fca0c72418c8785bc595949f3d5cecc44bcd02f8f7c69`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all 100000000 symmetry-reduced pairs with 2 <= n <= 20000 and 1 <= k <= floor(n/2)",
    "bounds": {
      "n": {
        "min": 2,
        "max": 20000
      },
      "states": {
        "min": 100000000,
        "max": 100000000
      },
      "prime_exponent_updates": {
        "min": 490041974,
        "max": 490041974
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "runnable",
    "kind": "inline_cpp17_computation",
    "command": "c++ -O3 -std=c++17 sweep.cpp -o sweep && ./sweep 20000",
    "runtime": "C++17 standard library",
    "citation": {
      "url": "https://doi.org/10.1134/S0001434613010331",
      "locator": "Inline C++17 computation executed on 2026-07-25"
    },
    "inline_source": [
      "#include <algorithm>",
      "#include <chrono>",
      "#include <cstdint>",
      "#include <iostream>",
      "#include <string>",
      "#include <vector>",
      "struct Big {",
      "  static constexpr std::uint32_t B = 1000000000U;",
      "  std::vector<std::uint32_t> d{1};",
      "  void mul(std::uint32_t m) {",
      "    std::uint64_t carry = 0;",
      "    for (auto& x : d) {",
      "      std::uint64_t z = std::uint64_t(x) * m + carry;",
      "      x = z % B; carry = z / B;",
      "    }",
      "    if (carry) d.push_back(carry);",
      "  }",
      "  void div_exact(std::uint32_t m) {",
      "    std::uint64_t rem = 0;",
      "    for (std::size_t i = d.size(); i-- > 0;) {",
      "      std::uint64_t z = rem * B + d[i];",
      "      d[i] = z / m; rem = z % m;",
      "    }",
      "    if (rem) { std::cerr << \"nonexact division\\n\"; std::exit(3); }",
      "    while (d.size() > 1 && !d.back()) d.pop_back();",
      "  }",
      "  friend bool operator>(const Big& a, const Big& b) {",
      "    if (a.d.size() != b.d.size()) return a.d.size() > b.d.size();",
      "    for (std::size_t i = a.d.size(); i-- > 0;)",
      "      if (a.d[i] != b.d[i]) return a.d[i] > b.d[i];",
      "    return false;",
      "  }",
      "  std::string str() const {",
      "    std::string s = std::to_string(d.back());",
      "    for (std::size_t i = d.size() - 1; i-- > 0;) {",
      "      std::string q = std::to_string(d[i]);",
      "      s.append(9 - q.size(), '0'); s += q;",
      "    }",
      "    return s;",
      "  }",
      "};",
      "",
      "static std::string text(const Big& x) { return x.str(); }",
      "",
      "int main(int argc, char** argv) {",
      "  const int N = argc > 1 ? std::stoi(argv[1]) : 10000;",
      "  std::vector<int> spf(N + 1);",
      "  for (int i = 2; i <= N; ++i) {",
      "    if (!spf[i]) {",
      "      spf[i] = i;",
      "      if ((long long)i * i <= N)",
      "        for (long long j = (long long)i * i; j <= N; j += i)",
      "          if (!spf[j]) spf[j] = i;",
      "    }",
      "  }",
      "  std::vector<int> exponent(N + 1);",
      "  Big global_best;",
      "  int best_n = 2, best_k = 1;",
      "  std::uint64_t states = 0, factor_updates = 0;",
      "  std::uint64_t row_hash = 1469598103934665603ULL;",
      "  auto mix = [&](std::uint64_t x) {",
      "    for (int b = 0; b < 8; ++b) {",
      "      row_hash ^= (x >> (8 * b)) & 255;",
      "      row_hash *= 1099511628211ULL;",
      "    }",
      "  };",
      "  for (int n = 2; n <= N; ++n) {",
      "    std::fill(exponent.begin(), exponent.end(), 0);",
      "    Big tau, row_best;",
      "    int row_k = 1;",
      "    auto change = [&](int x, int sign) {",
      "      while (x > 1) {",
      "        int p = spf[x], a = 0;",
      "        do { x /= p; ++a; } while (x > 1 && spf[x] == p);",
      "        int old = exponent[p], now = old + sign * a;",
      "        if (now < 0) { std::cerr << \"negative exponent\\n\"; std::exit(2); }",
      "        tau.div_exact(old + 1);",
      "        tau.mul(now + 1);",
      "        exponent[p] = now;",
      "        ++factor_updates;",
      "      }",
      "    };",
      "    for (int k = 1; k <= n / 2; ++k) {",
      "      change(n - k + 1, +1);",
      "      change(k, -1);",
      "      ++states;",
      "      if (tau > row_best) { row_best = tau; row_k = k; }",
      "      if (tau > global_best) {",
      "        global_best = tau; best_n = n; best_k = k;",
      "      }",
      "    }",
      "    std::string r = text(row_best);",
      "    mix(n); mix(row_k); mix(r.size());",
      "    for (unsigned char c : r) { row_hash ^= c; row_hash *= 1099511628211ULL; }",
      "    if (n % 1000 == 0) {",
      "      std::cerr << \"n=\" << n << \" digits=\" << text(global_best).size() << \"\\n\";",
      "    }",
      "  }",
      "  std::cout << \"limit=\" << N << \" states=\" << states << \" factor_updates=\" << factor_updates",
      "            << \" best_n=\" << best_n << \" best_k=\" << best_k",
      "            << \" best_tau=\" << text(global_best) << \" row_hash=\" << row_hash << \"\\n\";",
      "}"
    ],
    "missing": [
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1134/S0001434613010331",
    "locator": "Inline C++17 computation executed on 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R68",
      "title": "The exact record through n=20,000 occurs at (19,971, 9,949)",
      "object_type": "claim",
      "relation": "reproduces",
      "direction": "outgoing"
    },
    {
      "slug": "binomial-divisor-record-1e6",
      "title": "binomial divisor record 1e6",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}