TheoremDB

Problem packetWorkR333

R333artifactStatus: availableEvidence: ReproducedReplay: partialexhaustive over its scope

[#R333] Million-term exact greedy certificate

View replayOpen source ↗

1Summary

Inline C++ uses a counted binary trie to find the least eligible unused integer at each step.

The trie has one leaf for every integer below \(2^{22}\). Each internal node stores the number of unused leaves beneath it. A query reads candidate bits from most significant to least significant, always tries 0 before 1, and carries a state saying whether the candidate and current term have shared zero or one set bits. A leaf is accepted exactly in state one. This left-first traversal returns the smallest eligible unused leaf. Deleting every chosen leaf enforces distinctness.

Every successful query returns a value below \(2^{22}\). All integers outside the trie are larger, so each returned leaf is also the global greedy minimum. The program checks the defining bit-intersection condition at every step, checks the first 20 terms, and asserts three checkpoints. It also maintains the least missing integer directly. The FNV-1a digests serialize each 32-bit term in little-endian byte order.

Reproduced evidence. Recorded scope: the first 1000000 terms of OEIS A226077.

2Reproduce

Replay package: partial

Part of the replay path is recorded. Check the missing fields before comparing a new run.

Entry point
join source_lines with newline, compile with c++ -std=c++17 -O3, and run
Runtime
C++17 standard library

Verification source: oeis.org ↗, Inline C++17 source below, compiled and executed on 2026-07-24; first 10000 terms compared with the OEIS b-file

Missing for a complete replay: command, expected output.

3Overview

The first 10,000 terms agree term by term with the OEIS b-file. Compiled with Apple clang 17.0.0 using `c++ -std=c++17 -O3 -Wall -Wextra -pedantic`, the million-term run took about one second on an Apple Silicon workstation. The stable three-line output has SHA-256 digest `ee795c4535cedea9c942244e3f4731cc2d7b70a6821ef43d6141c92c2172a96c`.

4Source code

View source code
Source code
#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <limits>
#include <vector>

class UnusedTrie {
public:
    explicit UnusedTrie(unsigned bits)
        : bits_(bits),
          leaves_(std::uint32_t{1} << bits),
          count_(2 * leaves_, 0) {
        std::fill(count_.begin() + leaves_, count_.end(), 1);
        count_[leaves_] = 0;
        for (std::uint32_t node = leaves_ - 1; node > 0; --node) {
            count_[node] = count_[2 * node] + count_[2 * node + 1];
        }
    }

    void erase(std::uint32_t value) {
        if (value >= leaves_ || count_[leaves_ + value] != 1) {
            std::abort();
        }
        std::uint32_t node = leaves_ + value;
        count_[node] = 0;
        while ((node >>= 1) != 0) {
            count_[node] = count_[2 * node] + count_[2 * node + 1];
        }
    }

    std::uint32_t least_with_one_common_bit(std::uint32_t x) const {
        const std::uint32_t result =
            search(1, static_cast<int>(bits_) - 1, 0, 0, x);
        if (result == none) {
            std::abort();
        }
        return result;
    }

private:
    static constexpr std::uint32_t none =
        std::numeric_limits<std::uint32_t>::max();
    unsigned bits_;
    std::uint32_t leaves_;
    std::vector<std::uint32_t> count_;

    std::uint32_t search(
        std::uint32_t node,
        int bit,
        unsigned common,
        std::uint32_t prefix,
        std::uint32_t x
    ) const {
        if (count_[node] == 0) {
            return none;
        }
        if (bit < 0) {
            return common == 1 ? prefix : none;
        }
        std::uint32_t result =
            search(2 * node, bit - 1, common, prefix, x);
        if (result != none) {
            return result;
        }
        const bool x_bit = ((x >> bit) & 1U) != 0;
        const std::uint32_t with_bit =
            prefix | (std::uint32_t{1} << bit);
        if (!x_bit) {
            return search(2 * node + 1, bit - 1, common, with_bit, x);
        }
        if (common == 0) {
            return search(2 * node + 1, bit - 1, 1, with_bit, x);
        }
        return none;
    }
};

static unsigned popcount(std::uint32_t value) {
    unsigned count = 0;
    while (value != 0) {
        value &= value - 1;
        ++count;
    }
    return count;
}

static void hash_term(std::uint64_t& hash, std::uint32_t value) {
    for (unsigned shift = 0; shift < 32; shift += 8) {
        hash ^= (value >> shift) & 0xffU;
        hash *= 1099511628211ULL;
    }
}

struct Checkpoint {
    std::uint32_t n;
    std::uint32_t last;
    std::uint32_t maximum;
    std::uint32_t mex;
    std::uint64_t hash;
};

int main() {
    constexpr std::uint32_t number_of_terms = 1000000;
    constexpr unsigned universe_bits = 22;
    const std::array<Checkpoint, 3> expected{{
        {10000, 10391, 16401, 7159, 0x7c9a575e357a0f0cULL},
        {100000, 90809, 147456, 64511, 0xbd5d51b14ab8ba39ULL},
        {1000000, 1109402, 1573378, 523263, 0xdc2d86aed8b5cef8ULL}
    }};
    UnusedTrie unused(universe_bits);
    std::vector<std::uint32_t> terms;
    terms.reserve(number_of_terms);
    std::vector<unsigned char> seen(
        std::uint32_t{1} << universe_bits, 0);
    terms.push_back(1);
    seen[1] = 1;
    unused.erase(1);
    std::uint32_t maximum = 1;
    std::uint32_t mex = 2;
    std::uint64_t hash = 14695981039346656037ULL;
    hash_term(hash, 1);
    std::size_t next_checkpoint = 0;

    for (std::uint32_t n = 2; n <= number_of_terms; ++n) {
        const std::uint32_t value =
            unused.least_with_one_common_bit(terms.back());
        if (popcount(terms.back() & value) != 1 || seen[value]) {
            std::abort();
        }
        terms.push_back(value);
        seen[value] = 1;
        unused.erase(value);
        maximum = std::max(maximum, value);
        hash_term(hash, value);
        while (seen[mex]) {
            ++mex;
        }
        if (next_checkpoint < expected.size()
            && n == expected[next_checkpoint].n) {
            const Checkpoint& wanted = expected[next_checkpoint];
            if (value != wanted.last || maximum != wanted.maximum
                || mex != wanted.mex || hash != wanted.hash) {
                std::abort();
            }
            std::cout
                << "n=" << n
                << " last=" << value
                << " maximum=" << maximum
                << " mex=" << mex
                << " fnv1a64_le="
                << std::hex << std::setw(16) << std::setfill('0')
                << hash << std::dec << "\n";
            ++next_checkpoint;
        }
    }

    const std::array<std::uint32_t, 20> first_twenty{
        1, 3, 2, 6, 4, 5, 9, 7, 10, 8,
        11, 12, 20, 13, 17, 15, 18, 14, 19, 16};
    if (!std::equal(first_twenty.begin(), first_twenty.end(),
                    terms.begin())
        || next_checkpoint != expected.size()) {
        std::abort();
    }
}

5What it produced

Compiler command
c++ -std=c++17 -O3 -Wall -Wextra -pedantic
Expected stdout lines
n=10000 last=10391 maximum=16401 mex=7159 fnv1a64_le=7c9a575e357a0f0c, n=100000 last=90809 maximum=147456 mex=64511 fnv1a64_le=bd5d51b14ab8ba39, n=1000000 last=1109402 maximum=1573378 mex=523263 fnv1a64_le=dc2d86aed8b5cef8
Stdout sha256
ee795c4535cedea9c942244e3f4731cc2d7b70a6821ef43d6141c92c2172a96c

Execution

date2026-07-24terms generated1,000,000universe exclusive upper bound4,194,304least missing523,263last term1,109,402maximum term1,573,378oeis terms compared10,000oeis compact json sha2569f2304a259bb7ea43816fe6a1a61e322f67ecfe4fae172219da70034905ce505stdout sha256ee795c4535cedea9c942244e3f4731cc2d7b70a6821ef43d6141c92c2172a96c

6How it connects

Informed by

Tests

Evidence for

Recorded for

7Agent packet

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

View structured packet
json
{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R333",
  "content_hash": null,
  "slug": "gocb-artifact-million-term-trie",
  "type": "artifact",
  "title": "Million-term exact greedy certificate",
  "summary": "Inline C++ uses a counted binary trie to find the least eligible unused integer at each step.",
  "relevance": "For Does the greedy one-common-bit sequence visit every positive integer?, record gocb-artifact-million-term-trie (“Million-term exact greedy certificate”) supplies evidence or a replay used to check the packet. The record states: Inline C++ uses a counted binary trie to find the least eligible unused integer at each step.",
  "relevance_source": "recorded",
  "body": "The trie has one leaf for every integer below \\(2^{22}\\). Each internal node stores the number of unused leaves beneath it. A query reads candidate bits from most significant to least significant, always tries 0 before 1, and carries a state saying whether the candidate and current term have shared zero or one set bits. A leaf is accepted exactly in state one. This left-first traversal returns the smallest eligible unused leaf. Deleting every chosen leaf enforces distinctness.\n\nEvery successful query returns a value below \\(2^{22}\\). All integers outside the trie are larger, so each returned leaf is also the global greedy minimum. The program checks the defining bit-intersection condition at every step, checks the first 20 terms, and asserts three checkpoints. It also maintains the least missing integer directly. The FNV-1a digests serialize each 32-bit term in little-endian byte order.\n\nThe first 10,000 terms agree term by term with the OEIS b-file. Compiled with Apple clang 17.0.0 using `c++ -std=c++17 -O3 -Wall -Wextra -pedantic`, the million-term run took about one second on an Apple Silicon workstation. The stable three-line output has SHA-256 digest `ee795c4535cedea9c942244e3f4731cc2d7b70a6821ef43d6141c92c2172a96c`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the first 1000000 terms of OEIS A226077",
    "bounds": {
      "term_index": {
        "min": 1,
        "max": 1000000
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_cpp17_computation",
    "entrypoint": "join source_lines with newline, compile with c++ -std=c++17 -O3, and run",
    "runtime": "C++17 standard library",
    "citation": {
      "url": "https://oeis.org/A226077/b226077.txt",
      "locator": "Inline C++17 source below, compiled and executed on 2026-07-24; first 10000 terms compared with the OEIS b-file"
    },
    "inline_source": [
      "#include <algorithm>",
      "#include <array>",
      "#include <cstdint>",
      "#include <cstdlib>",
      "#include <iomanip>",
      "#include <iostream>",
      "#include <limits>",
      "#include <vector>",
      "",
      "class UnusedTrie {",
      "public:",
      "    explicit UnusedTrie(unsigned bits)",
      "        : bits_(bits),",
      "          leaves_(std::uint32_t{1} << bits),",
      "          count_(2 * leaves_, 0) {",
      "        std::fill(count_.begin() + leaves_, count_.end(), 1);",
      "        count_[leaves_] = 0;",
      "        for (std::uint32_t node = leaves_ - 1; node > 0; --node) {",
      "            count_[node] = count_[2 * node] + count_[2 * node + 1];",
      "        }",
      "    }",
      "",
      "    void erase(std::uint32_t value) {",
      "        if (value >= leaves_ || count_[leaves_ + value] != 1) {",
      "            std::abort();",
      "        }",
      "        std::uint32_t node = leaves_ + value;",
      "        count_[node] = 0;",
      "        while ((node >>= 1) != 0) {",
      "            count_[node] = count_[2 * node] + count_[2 * node + 1];",
      "        }",
      "    }",
      "",
      "    std::uint32_t least_with_one_common_bit(std::uint32_t x) const {",
      "        const std::uint32_t result =",
      "            search(1, static_cast<int>(bits_) - 1, 0, 0, x);",
      "        if (result == none) {",
      "            std::abort();",
      "        }",
      "        return result;",
      "    }",
      "",
      "private:",
      "    static constexpr std::uint32_t none =",
      "        std::numeric_limits<std::uint32_t>::max();",
      "    unsigned bits_;",
      "    std::uint32_t leaves_;",
      "    std::vector<std::uint32_t> count_;",
      "",
      "    std::uint32_t search(",
      "        std::uint32_t node,",
      "        int bit,",
      "        unsigned common,",
      "        std::uint32_t prefix,",
      "        std::uint32_t x",
      "    ) const {",
      "        if (count_[node] == 0) {",
      "            return none;",
      "        }",
      "        if (bit < 0) {",
      "            return common == 1 ? prefix : none;",
      "        }",
      "        std::uint32_t result =",
      "            search(2 * node, bit - 1, common, prefix, x);",
      "        if (result != none) {",
      "            return result;",
      "        }",
      "        const bool x_bit = ((x >> bit) & 1U) != 0;",
      "        const std::uint32_t with_bit =",
      "            prefix | (std::uint32_t{1} << bit);",
      "        if (!x_bit) {",
      "            return search(2 * node + 1, bit - 1, common, with_bit, x);",
      "        }",
      "        if (common == 0) {",
      "            return search(2 * node + 1, bit - 1, 1, with_bit, x);",
      "        }",
      "        return none;",
      "    }",
      "};",
      "",
      "static unsigned popcount(std::uint32_t value) {",
      "    unsigned count = 0;",
      "    while (value != 0) {",
      "        value &= value - 1;",
      "        ++count;",
      "    }",
      "    return count;",
      "}",
      "",
      "static void hash_term(std::uint64_t& hash, std::uint32_t value) {",
      "    for (unsigned shift = 0; shift < 32; shift += 8) {",
      "        hash ^= (value >> shift) & 0xffU;",
      "        hash *= 1099511628211ULL;",
      "    }",
      "}",
      "",
      "struct Checkpoint {",
      "    std::uint32_t n;",
      "    std::uint32_t last;",
      "    std::uint32_t maximum;",
      "    std::uint32_t mex;",
      "    std::uint64_t hash;",
      "};",
      "",
      "int main() {",
      "    constexpr std::uint32_t number_of_terms = 1000000;",
      "    constexpr unsigned universe_bits = 22;",
      "    const std::array<Checkpoint, 3> expected{{",
      "        {10000, 10391, 16401, 7159, 0x7c9a575e357a0f0cULL},",
      "        {100000, 90809, 147456, 64511, 0xbd5d51b14ab8ba39ULL},",
      "        {1000000, 1109402, 1573378, 523263, 0xdc2d86aed8b5cef8ULL}",
      "    }};",
      "    UnusedTrie unused(universe_bits);",
      "    std::vector<std::uint32_t> terms;",
      "    terms.reserve(number_of_terms);",
      "    std::vector<unsigned char> seen(",
      "        std::uint32_t{1} << universe_bits, 0);",
      "    terms.push_back(1);",
      "    seen[1] = 1;",
      "    unused.erase(1);",
      "    std::uint32_t maximum = 1;",
      "    std::uint32_t mex = 2;",
      "    std::uint64_t hash = 14695981039346656037ULL;",
      "    hash_term(hash, 1);",
      "    std::size_t next_checkpoint = 0;",
      "",
      "    for (std::uint32_t n = 2; n <= number_of_terms; ++n) {",
      "        const std::uint32_t value =",
      "            unused.least_with_one_common_bit(terms.back());",
      "        if (popcount(terms.back() & value) != 1 || seen[value]) {",
      "            std::abort();",
      "        }",
      "        terms.push_back(value);",
      "        seen[value] = 1;",
      "        unused.erase(value);",
      "        maximum = std::max(maximum, value);",
      "        hash_term(hash, value);",
      "        while (seen[mex]) {",
      "            ++mex;",
      "        }",
      "        if (next_checkpoint < expected.size()",
      "            && n == expected[next_checkpoint].n) {",
      "            const Checkpoint& wanted = expected[next_checkpoint];",
      "            if (value != wanted.last || maximum != wanted.maximum",
      "                || mex != wanted.mex || hash != wanted.hash) {",
      "                std::abort();",
      "            }",
      "            std::cout",
      "                << \"n=\" << n",
      "                << \" last=\" << value",
      "                << \" maximum=\" << maximum",
      "                << \" mex=\" << mex",
      "                << \" fnv1a64_le=\"",
      "                << std::hex << std::setw(16) << std::setfill('0')",
      "                << hash << std::dec << \"\\n\";",
      "            ++next_checkpoint;",
      "        }",
      "    }",
      "",
      "    const std::array<std::uint32_t, 20> first_twenty{",
      "        1, 3, 2, 6, 4, 5, 9, 7, 10, 8,",
      "        11, 12, 20, 13, 17, 15, 18, 14, 19, 16};",
      "    if (!std::equal(first_twenty.begin(), first_twenty.end(),",
      "                    terms.begin())",
      "        || next_checkpoint != expected.size()) {",
      "        std::abort();",
      "    }",
      "}"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://oeis.org/A226077/b226077.txt",
    "locator": "Inline C++17 source below, compiled and executed on 2026-07-24; first 10000 terms compared with the OEIS b-file"
  },
  "models": [],
  "relations": [
    {
      "slug": "R337",
      "title": "The sequence is OEIS A226077",
      "object_type": "claim",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "R337",
      "title": "The sequence is OEIS A226077",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "R335",
      "title": "The first million terms cover 1 through 523,262",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "greedy-one-common-bit-permutation",
      "title": "greedy one common bit permutation",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}

8Provenance

View source, identifiers, and projection details
Project
greedy-one-common-bit-permutation
Locator
Inline C++17 source below, compiled and executed on 2026-07-24; first 10000 terms compared with the OEIS b-file
License
CC0-1.0
Contributors
TheoremDB entry research, 2026-07-24
Source
oeis.org ↗
Public record
R333
Stable alias
gocb-artifact-million-term-trie
Projection
Reproduction fields are derived from the immutable record.

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

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.