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

- ID: `P2458`
- Reference: `greedy-one-common-bit-permutation`
- Page: https://theoremdb.org/statements/P2458
- Record maturity: Reviewed problem with recorded work

## Problem

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?

### Problem setup

- **Definition.** The binary support of an integer is the set of positions occupied by 1-bits.
- **Remark.** Equivalently, popcount(a_n AND a_(n+1))=1.

### What counts as a solution

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

## Status

The first million terms cover every positive integer through 523,262, with 523,263 the least missing value; occurrence of 523,263 and universal coverage remain unproved. [1](#reference-1)

## Work

### Evidence for the current status

**Computation 1 (The first million terms cover 1 through 523,262).** The first million terms cover every positive integer through 523,262, with 523,263 the least missing value; occurrence of 523,263 and universal coverage remain unproved.

The exact greedy computation tracks a Boolean used table and advances a least-missing pointer after every insertion. At term 1,000,000 the pointer equals 523,263. Hence every integer from 1 through 523,262 has appeared. The last term is 1,109,402, and the largest term seen is 1,573,378.

This is an exhaustive statement about the stated prefix. It supplies finite evidence for the permutation question.

### Background and intake notes

The recurrence is canonical and each failed induction has a legible state: the current term, the least missing value, and their bit intersection. That makes the proof search suitable for stored route obstructions.

- Original intake status: Novelty and status remain unverified. Greedy permutation sequences are a crowded folklore area.
- Induction on the least missing integer is the attractive route.
- The least missing value can share zero bits or several bits with the current term, so minimality supplies no immediate forcing move. Later terms may keep bypassing it while remaining smaller than other eligible choices.

- Recorded example: The sequence begins 1,3,2,6,4,5,9,7,10,8,11,12,20,13,17,15,18,14,19,16.

### Other known results

- **Computation 2** (reproduced): Every current term has infinitely many eligible neighbors, so the construction gives an infinite sequence of distinct integers. [1](#reference-1)
- **Proposition 1** (supported): Paul Tek submitted the same greedy binary-support recurrence to OEIS in 2013. [1](#reference-1)

### Open directions

- **Route 1** (supported): OEIS calls A226077 a permutation and lists an inverse, while its record supplies computation without a proof. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Inline C++ uses a counted binary trie to find the least eligible unused integer at each step. [2](#reference-2)

### Computational notes

- The first 10000 terms were generated by scanning unused integers in increasing order and checking exact bit intersections. The largest term was 16401 and the least missing positive integer was 7159.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `greedy-one-common-bit-permutation`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>OEIS A226077 and A226093, comments and tables; comparison with the proved disjoint-support analogue OEIS A109812; source audit 2026-07-24. OEIS A226077, definition, author field, program, and b226077.txt; termwise comparison rerun 2026-07-24; OEIS A226077 and A226093, comments and tables; comparison with the proved disjoint-support analogue OEIS A109812; source audit 2026-07-24 https://oeis.org/A226077
   - Also cited at Executable certificate gocb-artifact-million-term-trie, run 2026-07-24
   - Also cited at Elementary direct proof recorded and checked for this entry on 2026-07-24
   - Also cited at OEIS A226077, definition, author field, program, and b226077.txt; termwise comparison rerun 2026-07-24
   - Also cited at OEIS A226077 and A226093, comments and tables; comparison with the proved disjoint-support analogue OEIS A109812; source audit 2026-07-24
   - reference_database; primary source; web version checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - For Does the greedy one-common-bit sequence visit every positive integer?: The sequence is OEIS A226077. Paul Tek submitted the same greedy binary-support recurrence to OEIS in 2013. The universal permutation claim remains open in the sources checked. OEIS calls A226077 a permutation and lists an inverse, while its record supplies computation without a proof.
   - Source named by the research packet.
2. <a id="reference-2"></a>Inline C++17 source below, compiled and executed on 2026-07-24; first 10000 terms compared with the OEIS b-file. Inline C++17 source below, compiled and executed on 2026-07-24; first 10000 terms compared with the OEIS b-file https://oeis.org/A226077/b226077.txt
   - reference_database; primary source; web version checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - For Does the greedy one-common-bit sequence visit every positive integer?: Million-term exact greedy certificate. Inline C++ uses a counted binary trie to find the least eligible unused integer at each step.