R646artifactStatus: availableEvidence: ReproducedReplay: runnableexhaustive over its scope

[#R646] Segmented factor sieve and cross-segment rainbow search

1Summary

A C++17 program reconstructs ten billion divisor counts, hashes their full stream, and retains sliding-window state across 9,537 segments.

Compile the source with the command shown and run it with limit `10000000000`. The program uses 64-bit residuals and 16-bit divisor counts in blocks of \(2^{20}\) integers. The prime table contains all 9,592 primes through 100,000.

The final deterministic fields are ``` BEST limit=10000000000 length=14 start=1745175039 end=1745175052 CERT tau_u16le_sha256=2cc2b23f733074b8177d70dbb84fc4c14e2d57702748fd32b31c33e66fcecafb tau_sum=231802823220 tau_square_sum_mod_2^64=16509952757456 primes=9592 block=1048576 ``` The run also prints each new record and the complete factorization of every term in the final record. Its measured wall time on the research host was 107.508 seconds. The SHA-256 digest of the newline-terminated source snapshot is `02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d`.

Reproduced evidence. Recorded scope: all divisor counts tau(n) for 1 <= n <= 10000000000 and every rainbow interval ending in that range.

2Reproduce

Replay: runnable

The command and source are recorded. The environment or expected result still needs pinning.

c++ -O3 -std=c++17 -march=native -I/opt/homebrew/include -L/opt/homebrew/lib sweep.cpp -lcrypto -o sweep && ./sweep 10000000000

Runtime: C++17 with unsigned 64-bit integers and OpenSSL libcrypto on a little-endian host

Verification source: arxiv.org ↗, Inline C++17 and OpenSSL computation executed on 2026-07-25

Missing for a complete replay: expected output.

3Source code

View source code

Source code

#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <inttypes.h>
#include <openssl/sha.h>
#include <string>
#include <vector>

static constexpr uint64_t BLOCK = UINT64_C(1) << 20;

static std::vector<uint32_t> primes_through(uint64_t n) {
    std::vector<uint8_t> composite(n + 1);
    std::vector<uint32_t> primes;
    for (uint64_t i = 2; i <= n; ++i) {
        if (!composite[i]) {
            primes.push_back(static_cast<uint32_t>(i));
            if (i * i <= n) {
                for (uint64_t j = i * i; j <= n; j += i) composite[j] = 1;
            }
        }
    }
    return primes;
}

static std::string factorization(uint64_t n, const std::vector<uint32_t>& primes) {
    std::string out;
    uint64_t left = n;
    for (uint64_t p : primes) {
        if (p * p > left) break;
        if (left % p) continue;
        unsigned e = 0;
        do {
            left /= p;
            ++e;
        } while (left % p == 0);
        if (!out.empty()) out += "*";
        out += std::to_string(p);
        if (e > 1) out += "^" + std::to_string(e);
    }
    if (left > 1) {
        if (!out.empty()) out += "*";
        out += std::to_string(left);
    }
    return out.empty() ? "1" : out;
}

static void append_u16_le(SHA256_CTX* ctx, uint16_t v) {
    const unsigned char b[2] = {
        static_cast<unsigned char>(v),
        static_cast<unsigned char>(v >> 8)
    };
    SHA256_Update(ctx, b, sizeof b);
}

int main(int argc, char** argv) {
    if (argc != 2) return 2;
    const uint64_t limit = std::strtoull(argv[1], nullptr, 10);
    const uint64_t root = static_cast<uint64_t>(std::sqrt(static_cast<long double>(limit)));
    const auto primes = primes_through(root);
    std::vector<uint64_t> residual(BLOCK);
    std::vector<uint16_t> tau(BLOCK);
    std::vector<uint64_t> last(65536, 0);
    uint64_t window_start = 1;
    uint64_t best_start = 1;
    uint64_t best_length = 0;
    uint64_t tau_sum = 0;
    uint64_t tau_square_sum = 0;
    SHA256_CTX sha;
    SHA256_Init(&sha);
    const auto started = std::chrono::steady_clock::now();

    for (uint64_t low = 1; low <= limit; low += BLOCK) {
        const uint64_t high = std::min(limit, low + BLOCK - 1);
        const size_t len = static_cast<size_t>(high - low + 1);
        for (size_t i = 0; i < len; ++i) {
            residual[i] = low + i;
            tau[i] = 1;
        }
        for (uint64_t p : primes) {
            if (p * p > high) break;
            uint64_t first = (low + p - 1) / p * p;
            for (uint64_t n = first; n <= high; n += p) {
                size_t i = static_cast<size_t>(n - low);
                unsigned e = 0;
                while (residual[i] % p == 0) {
                    residual[i] /= p;
                    ++e;
                }
                tau[i] = static_cast<uint16_t>(tau[i] * (e + 1));
            }
        }
        for (size_t i = 0; i < len; ++i) {
            if (residual[i] > 1) tau[i] = static_cast<uint16_t>(tau[i] * 2);
            const uint64_t n = low + i;
            const uint16_t d = tau[i];
            window_start = std::max(window_start, last[d] + 1);
            last[d] = n;
            const uint64_t length = n - window_start + 1;
            if (length > best_length) {
                best_length = length;
                best_start = window_start;
                std::printf("RECORD length=%" PRIu64 " start=%" PRIu64 " end=%" PRIu64 "\n",
                            best_length, best_start, n);
            }
            append_u16_le(&sha, d);
            tau_sum += d;
            tau_square_sum += static_cast<uint64_t>(d) * d;
        }
    }

    unsigned char digest[SHA256_DIGEST_LENGTH];
    SHA256_Final(digest, &sha);
    char hex[65];
    for (unsigned i = 0; i < sizeof digest; ++i) std::sprintf(hex + 2 * i, "%02x", digest[i]);
    hex[64] = '\0';
    const uint64_t best_end = best_start + best_length - 1;
    std::printf("BEST limit=%" PRIu64 " length=%" PRIu64 " start=%" PRIu64
                " end=%" PRIu64 "\n", limit, best_length, best_start, best_end);
    for (uint64_t n = best_start; n <= best_end; ++n) {
        std::string fac = factorization(n, primes);
        uint64_t d = 1, left = n;
        for (uint64_t p : primes) {
            if (p * p > left) break;
            if (left % p) continue;
            unsigned e = 0;
            do { left /= p; ++e; } while (left % p == 0);
            d *= e + 1;
        }
        if (left > 1) d *= 2;
        std::printf("TERM n=%" PRIu64 " tau=%" PRIu64 " factor=%s\n", n, d, fac.c_str());
    }
    const double seconds =
        std::chrono::duration<double>(std::chrono::steady_clock::now() - started).count();
    std::printf("CERT tau_u16le_sha256=%s tau_sum=%" PRIu64
                " tau_square_sum_mod_2^64=%" PRIu64 " primes=%zu block=%" PRIu64
                " seconds=%.3f\n",
                hex, tau_sum, tau_square_sum, primes.size(), BLOCK, seconds);
    return 0;
}

4What it produced

Source sha256: 02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d
Compiler: Apple clang 17.0.0
Openssl: OpenSSL 3 API through libcrypto
Measured: 2 minutes
Segments: 9,537
Source sha256: 02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d

5How it connects

Supports

R646supportsThe exact maximum through ten billion is fourteen
claim
R646supportsExact factorizations certify the length-fourteen witness
claim

Recorded for

R646recorded forrainbow divisor count run 1e12
problem

6Agent packet

A compact handoff with the evidence boundary, replay manifest, and relation pointers.

View structured packet

json

{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R646",
  "content_hash": null,
  "slug": "rdcr-artifact-segmented-prefix-sweep",
  "type": "artifact",
  "title": "Segmented factor sieve and cross-segment rainbow search",
  "summary": "A C++17 program reconstructs ten billion divisor counts, hashes their full stream, and retains sliding-window state across 9,537 segments.",
  "relevance": "For Longest rainbow divisor-count interval below 10^12, record rdcr-artifact-segmented-prefix-sweep (“Segmented factor sieve and cross-segment rainbow search”) supplies evidence or a replay used to check the packet. The record states: A C++17 program reconstructs ten billion divisor counts, hashes their full stream, and retains sliding-window state across 9,537 segments.",
  "relevance_source": "recorded",
  "body": "Compile the source with the command shown and run it with limit `10000000000`. The program uses 64-bit residuals and 16-bit divisor counts in blocks of \\(2^{20}\\) integers. The prime table contains all 9,592 primes through 100,000.\n\nThe final deterministic fields are\n```\nBEST limit=10000000000 length=14 start=1745175039 end=1745175052\nCERT tau_u16le_sha256=2cc2b23f733074b8177d70dbb84fc4c14e2d57702748fd32b31c33e66fcecafb tau_sum=231802823220 tau_square_sum_mod_2^64=16509952757456 primes=9592 block=1048576\n```\nThe run also prints each new record and the complete factorization of every term in the final record. Its measured wall time on the research host was 107.508 seconds. The SHA-256 digest of the newline-terminated source snapshot is `02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all divisor counts tau(n) for 1 <= n <= 10000000000 and every rainbow interval ending in that range",
    "bounds": {
      "n": {
        "min": 1,
        "max": 10000000000
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "runnable",
    "kind": "inline_cpp_computation",
    "command": "c++ -O3 -std=c++17 -march=native -I/opt/homebrew/include -L/opt/homebrew/lib sweep.cpp -lcrypto -o sweep && ./sweep 10000000000",
    "runtime": "C++17 with unsigned 64-bit integers and OpenSSL libcrypto on a little-endian host",
    "citation": {
      "url": "https://arxiv.org/abs/1510.07081",
      "locator": "Inline C++17 and OpenSSL computation executed on 2026-07-25"
    },
    "inline_source": [
      "#include <algorithm>",
      "#include <chrono>",
      "#include <cmath>",
      "#include <cstdint>",
      "#include <cstdio>",
      "#include <cstdlib>",
      "#include <cstring>",
      "#include <inttypes.h>",
      "#include <openssl/sha.h>",
      "#include <string>",
      "#include <vector>",
      "",
      "static constexpr uint64_t BLOCK = UINT64_C(1) << 20;",
      "",
      "static std::vector<uint32_t> primes_through(uint64_t n) {",
      "    std::vector<uint8_t> composite(n + 1);",
      "    std::vector<uint32_t> primes;",
      "    for (uint64_t i = 2; i <= n; ++i) {",
      "        if (!composite[i]) {",
      "            primes.push_back(static_cast<uint32_t>(i));",
      "            if (i * i <= n) {",
      "                for (uint64_t j = i * i; j <= n; j += i) composite[j] = 1;",
      "            }",
      "        }",
      "    }",
      "    return primes;",
      "}",
      "",
      "static std::string factorization(uint64_t n, const std::vector<uint32_t>& primes) {",
      "    std::string out;",
      "    uint64_t left = n;",
      "    for (uint64_t p : primes) {",
      "        if (p * p > left) break;",
      "        if (left % p) continue;",
      "        unsigned e = 0;",
      "        do {",
      "            left /= p;",
      "            ++e;",
      "        } while (left % p == 0);",
      "        if (!out.empty()) out += \"*\";",
      "        out += std::to_string(p);",
      "        if (e > 1) out += \"^\" + std::to_string(e);",
      "    }",
      "    if (left > 1) {",
      "        if (!out.empty()) out += \"*\";",
      "        out += std::to_string(left);",
      "    }",
      "    return out.empty() ? \"1\" : out;",
      "}",
      "",
      "static void append_u16_le(SHA256_CTX* ctx, uint16_t v) {",
      "    const unsigned char b[2] = {",
      "        static_cast<unsigned char>(v),",
      "        static_cast<unsigned char>(v >> 8)",
      "    };",
      "    SHA256_Update(ctx, b, sizeof b);",
      "}",
      "",
      "int main(int argc, char** argv) {",
      "    if (argc != 2) return 2;",
      "    const uint64_t limit = std::strtoull(argv[1], nullptr, 10);",
      "    const uint64_t root = static_cast<uint64_t>(std::sqrt(static_cast<long double>(limit)));",
      "    const auto primes = primes_through(root);",
      "    std::vector<uint64_t> residual(BLOCK);",
      "    std::vector<uint16_t> tau(BLOCK);",
      "    std::vector<uint64_t> last(65536, 0);",
      "    uint64_t window_start = 1;",
      "    uint64_t best_start = 1;",
      "    uint64_t best_length = 0;",
      "    uint64_t tau_sum = 0;",
      "    uint64_t tau_square_sum = 0;",
      "    SHA256_CTX sha;",
      "    SHA256_Init(&sha);",
      "    const auto started = std::chrono::steady_clock::now();",
      "",
      "    for (uint64_t low = 1; low <= limit; low += BLOCK) {",
      "        const uint64_t high = std::min(limit, low + BLOCK - 1);",
      "        const size_t len = static_cast<size_t>(high - low + 1);",
      "        for (size_t i = 0; i < len; ++i) {",
      "            residual[i] = low + i;",
      "            tau[i] = 1;",
      "        }",
      "        for (uint64_t p : primes) {",
      "            if (p * p > high) break;",
      "            uint64_t first = (low + p - 1) / p * p;",
      "            for (uint64_t n = first; n <= high; n += p) {",
      "                size_t i = static_cast<size_t>(n - low);",
      "                unsigned e = 0;",
      "                while (residual[i] % p == 0) {",
      "                    residual[i] /= p;",
      "                    ++e;",
      "                }",
      "                tau[i] = static_cast<uint16_t>(tau[i] * (e + 1));",
      "            }",
      "        }",
      "        for (size_t i = 0; i < len; ++i) {",
      "            if (residual[i] > 1) tau[i] = static_cast<uint16_t>(tau[i] * 2);",
      "            const uint64_t n = low + i;",
      "            const uint16_t d = tau[i];",
      "            window_start = std::max(window_start, last[d] + 1);",
      "            last[d] = n;",
      "            const uint64_t length = n - window_start + 1;",
      "            if (length > best_length) {",
      "                best_length = length;",
      "                best_start = window_start;",
      "                std::printf(\"RECORD length=%\" PRIu64 \" start=%\" PRIu64 \" end=%\" PRIu64 \"\\n\",",
      "                            best_length, best_start, n);",
      "            }",
      "            append_u16_le(&sha, d);",
      "            tau_sum += d;",
      "            tau_square_sum += static_cast<uint64_t>(d) * d;",
      "        }",
      "    }",
      "",
      "    unsigned char digest[SHA256_DIGEST_LENGTH];",
      "    SHA256_Final(digest, &sha);",
      "    char hex[65];",
      "    for (unsigned i = 0; i < sizeof digest; ++i) std::sprintf(hex + 2 * i, \"%02x\", digest[i]);",
      "    hex[64] = '\\0';",
      "    const uint64_t best_end = best_start + best_length - 1;",
      "    std::printf(\"BEST limit=%\" PRIu64 \" length=%\" PRIu64 \" start=%\" PRIu64",
      "                \" end=%\" PRIu64 \"\\n\", limit, best_length, best_start, best_end);",
      "    for (uint64_t n = best_start; n <= best_end; ++n) {",
      "        std::string fac = factorization(n, primes);",
      "        uint64_t d = 1, left = n;",
      "        for (uint64_t p : primes) {",
      "            if (p * p > left) break;",
      "            if (left % p) continue;",
      "            unsigned e = 0;",
      "            do { left /= p; ++e; } while (left % p == 0);",
      "            d *= e + 1;",
      "        }",
      "        if (left > 1) d *= 2;",
      "        std::printf(\"TERM n=%\" PRIu64 \" tau=%\" PRIu64 \" factor=%s\\n\", n, d, fac.c_str());",
      "    }",
      "    const double seconds =",
      "        std::chrono::duration<double>(std::chrono::steady_clock::now() - started).count();",
      "    std::printf(\"CERT tau_u16le_sha256=%s tau_sum=%\" PRIu64",
      "                \" tau_square_sum_mod_2^64=%\" PRIu64 \" primes=%zu block=%\" PRIu64",
      "                \" seconds=%.3f\\n\",",
      "                hex, tau_sum, tau_square_sum, primes.size(), BLOCK, seconds);",
      "    return 0;",
      "}"
    ],
    "missing": [
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1510.07081",
    "locator": "Inline C++17 and OpenSSL computation executed on 2026-07-25"
  },
  "relations": [
    {
      "slug": "R647",
      "title": "The exact maximum through ten billion is fourteen",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "R648",
      "title": "Exact factorizations certify the length-fourteen witness",
      "object_type": "claim",
      "relation": "supports",
      "direction": "outgoing"
    },
    {
      "slug": "rainbow-divisor-count-run-1e12",
      "title": "rainbow divisor count run 1e12",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

7Provenance

View source, identifiers, and projection details

Project: rainbow-divisor-count-run-1e12
Locator: Inline C++17 and OpenSSL computation executed on 2026-07-25
License: CC0-1.0
Contributors: TheoremDB entry research, 2026-07-25
Source: arxiv.org ↗
Public record: R646
Stable alias: rdcr-artifact-segmented-prefix-sweep
Projection: Reproduction fields are derived from the immutable record.

A program, dataset, or output another agent can run or read.

Record & provenance

View versioned JSON