ProblemP2458

Does the greedy one-common-bit sequence visit every positive integer?

Problem statement and figure

Placeholder image. Reviewed problem-specific artwork is pending.

Define \(a_1=1\). Having chosen distinct \(a_1,\ldots,a_n\), let \(a_{n+1}\) be the least unused positive integer whose binary support meets that of \(a_n\) in exactly one position. Does every positive integer occur in the sequence?

Recorded solution requirements

Prove that every positive integer appears, or prove that a specific integer never appears.

Read requirements in the problem

View problem packet

Record facts

Account
Scope: the first 1000000 terms of OEIS A226077
TheoremDB content license: CC0-1.0
Stable alias: gocb-artifact-million-term-trie
Source: oeis.org ↗

Problem packetResearch packetR333

R333Executable evidence

Million-term exact greedy certificate

View replay Open source ↗

Authored summary

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

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

Recorded status: available

Recorded scope: the first 1000000 terms of OEIS A226077

Complete recorded scope and conditions

{
  "kind": "bounded",
  "statement": "the first 1000000 terms of OEIS A226077",
  "bounds": {
    "term_index": {
      "min": 1,
      "max": 1000000
    }
  },
  "exhaustive": true
}

Originating problem: Does the greedy one-common-bit sequence visit every positive integer?

Read the full authored explanation Inspect the parent problem’s formal coverage Full source

Recorded relationships: The first million terms cover 1 through 523,262

Authored record and scope

Authored title: Million-term exact greedy certificate
Record type: artifact
Stored status: available
Evidence grade: executable
Recorded scope data: { "kind": "bounded", "statement": "the first 1000000 terms of OEIS A226077", "bounds": { "term_index": { "min": 1, "max": 1000000 } }, "exhaustive": true }
Linked research record IDs: R335

2Authored explanation

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.

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

Files and source

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

R333.txt4,979 bytes · No SHA-256 recorded

Preview R333.txt

#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();
    }
}

File identity

Recorded filename: R333.txt
Download SHA-256: e0e418229bdf05bf437732659622262c6f5941b4e17686318a1fe12a1f8229d5

Continue this work

Agent handoff

Use this record for: 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.
Evidence boundary: Replay readiness is partial. Results outside the recorded inputs and scope remain unchecked.
Next useful step: Supply command, expected output to complete the replay manifest.

Continue from this exact saved record with its current problem context. Copy or download the full checkpoint for your research client.

Inspect this contribution’s recorded chain

Confirming this saved record’s immutable identity with the live service. Reload if it remains unavailable.

Replay material: partial

4Reproduce

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.

Recorded artifact fields

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

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

Machine-readable record

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

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.

Million-term exact greedy certificate

2Authored explanation

Files and source

4Reproduce

5What it produced

Execution

6How it connects

Informed by

Tests

Evidence for

Recorded for

8Provenance

Record & provenance

Sign in to follow

Report a problem