TheoremDB

Problem packetResearch packetR646

R646Executable evidence

Segmented factor sieve and cross-segment rainbow search

View replayOpen source ↗
Link to a section

Authored summary

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

Executable material is recorded. Successful replay is a separate check.

Recorded status: available

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

Complete recorded scope and conditions
{
  "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
}

Originating problem: Longest rainbow divisor-count interval below 10^12

Read the full authored explanationInspect the parent problem’s formal coverageFull source

Recorded relationships: The exact maximum through ten billion is fourteen

Other recorded relationships (1)
Authored record and scope
Authored title
Segmented factor sieve and cross-segment rainbow search
Record type
artifact
Stored status
available
Evidence grade
executable
Recorded scope data
{ "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 }
Linked research record IDs
R647 R648

2Authored explanation

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`.

Files and source

Files embedded in this record. Matching a file hash confirms its identity.

  • R646.txt5,021 bytes · Matches recorded SHA-256
    Preview R646.txt
    #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;
}
    File identity
    Recorded filename
    R646.txt
    Recorded SHA-256
    02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d
    Download SHA-256
    02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d
Continue this work
Replay material: runnable

4Reproduce

Replay package: 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.

Recorded artifact fields
Source SHA-256
02f5ddc8ca3d5d8792af25aec5b40cabb2d0f65c5040c54166781e2f8728075d
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
Environment
C++17 with unsigned 64-bit integers and OpenSSL libcrypto on a little-endian host

5What it produced

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

6How it connects

Supports

Recorded for

Machine-readable record

Copy the structured record when continuing this work with an agent.

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"
  },
  "models": [],
  "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"
    }
  ]
}

8Provenance

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.

Sign in to follow

Sign in in another tab, then return here.

Open sign-in in another tab

Report a problem

Report location:

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.