What happens when the output of a rule becomes its next input, repeatedly? For OEIS A006165, I studied b_k(n) = n − A_k(n): the original integer n minus the result of applying the rule k times. The values form a staircase, increasing one step at a time and sometimes staying level. The questions are which values repeat, how often, and whether every input producing a given value can be identified.
I selected Peter Bala’s conjecture (vii) about this sequence and requested a proof and verification. The public manuscript gives one iteration formula valid for every k, together with complete inverse images. An inverse image is the full set of inputs producing a particular output.
Apply the same recursively defined rule again
OEIS A006165 is defined by
a(1) = a(2) = 1
a(2n) = 2a(n) [n ≥ 2]
a(2n+1) = a(n) + a(n+1) [n ≥ 1]The right-hand inputs are smaller than the left-hand one, so the values can be calculated in order. The sequence begins 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 8, ….
A₁(n) means a(n), A₂(n) means a(a(n)), and A₃(n) means a(a(a(n))). The iteration count indicates repeated function application, not raising a value to a power. For example, a(160) = 96 and a(96) = 64, so A₂(160) = 64 and b₂(160) = 96.
A piecewise formula for the original sequence was already known. Write an input as n = 2^r + s. For r ≥ 1 and 0 ≤ s ≤ 2^r,
a(2^r + s) = min(2^(r−1) + s, 2^r).
The minimum chooses the smaller of the two expressions. The value initially rises with s, then stays level on reaching 2ʳ. This base formula and the plateaus of the first-iterate case have prior OEIS sources; they are the starting point here.
One formula for every iteration count
Choose n = 2^r + s with 0 ≤ s < 2^r, so r selects the largest power of two not exceeding n. The k-th iterate is
A_k(n) = min(2^(r−k) + s, 2^(r−k+1)) [1 ≤ k ≤ r]
A_k(n) = 1 [k > r]Each application lowers the exponents by one. The proof uses the identity a(min(2h+s, 4h)) = min(h+s, 2h) for powers of two h. Applying a to the formula at one stage produces the same form at the next stage, giving an induction for every iteration count.
Eventually the value reaches 1 or 2, both of which map to 1. Precisely, A_k(n) = 1 if and only if n ≤ 2^k. This includes small inputs with very large k. The implementation checks that saturation condition before constructing unnecessarily large powers.
Which values repeat, and where?
Fix k and put q = 2ᵏ and c = q − 1. The repeated values of b_k are exactly c·2^m = (2^k−1)2^m for integers m ≥ 0. Every input producing such a value lies in the following inclusive integer interval:
q·2^m ≤ n ≤ (q+1)·2^m.
Subtracting the endpoints and adding one gives a multiplicity of 2^m + 1. The iteration count k changes the repeated value and its location, but not its multiplicity for a fixed m.
For k = 2:
| m | b₂ value | Inputs n | Count |
|---|---|---|---|
| 0 | 3 | 4 through 5 | 2 |
| 1 | 6 | 8 through 10 | 3 |
| 2 | 12 | 16 through 20 | 5 |
| 3 | 24 | 32 through 40 | 9 |
| 4 | 48 | 64 through 80 | 17 |
| 5 | 96 | 128 through 160 | 33 |
Checking only inside a plateau would not rule out the same value occurring elsewhere. The classification therefore also locates every nonrepeated value. For a nonnegative integer y < c, the sole input is y + 1. For y ≥ c, choose m with c·2^m ≤ y < c·2^(m+1). If y = c·2ᵐ, its inverse image is the full plateau above. Otherwise, its sole input is y + 2^(m+1).
These value intervals are disjoint and cover all nonnegative integers. This rules out any further occurrence beyond the stated inverse image. Adjacent values differ by zero within a plateau and by one along a rising segment or at a join. The same classification thus establishes the first-difference property, the repeated values and their multiplicities.
The example says 35; the interval contains 33 inputs
The OEIS conjecture lists multiplicities 2, 3, 5, 9, 17, 35, … while linking to A000051, whose formula is 2ᵐ + 1. That wording was still present when I checked the entry on 7 September 2026.
The complete inverse-image formula gives 33 at m = 5. For example, b₂(n) = 96 for n from 128 through 160, so the count is 160 − 128 + 1 = 33. The neighbouring outputs are 95 and 97. Checking both ends and the neighbouring values therefore does not introduce any additional occurrence.
I kept this numerical discrepancy separate from the general conjectural structure. The inverse-image interval explains why the count is 33 without repeating the displayed 35. The calculation does not establish what the original writer intended by that example.
Comparing the proof with the implementations
The public checks compare the defining recurrence with the closed iteration formula for n = 1 through 8,192 and k = 1 through 20: 163,840 pairs. A separate plateau-and-ramp construction is compared over the same pairs. The checker also examines 163,820 adjacent differences and 155,662 fibres clipped to the finite test range. The clipped-fibre count is a comparison within that range, not a claim to have tested the infinite domain.
For 48 sampled plateaus, the checks cover 552 interior values and 96 immediate exterior neighbours, plus 629 additional large-integer and boundary pairs. The largest tested n has 191 bits, and some tests use k = 2²⁰⁰. Seven corrupted certificates—including shifted endpoints and replacement of 33 by 35—are rejected. The universal conclusion comes from the induction and complete interval partition, not the number of finite tests.
I deposited the proof and code on Zenodo on 5 September 2026. The standard-library checker runs with Python 3.10 or later using python3 code/check_independent.py. The command python3 code/a006165.py 160 2 calculates the example above: second iterate 64 and difference 96. I selected the target, directed the research and requested verification. ChatGPT assisted with derivation, proof writing, code and internal checks; Codex’s replay and separate implementation review are documented in the public contribution record.
The OEIS entry checked now still marks (vii) as conjectural and does not link the public proof. What the materials make directly inspectable is the iteration formula and the complete inverse images: from noticing a repeated value to identifying its first and last positions, and proving why it cannot appear elsewhere.