A350603 Irregular triangle read by rows: row n lists the elements of the set S_n in increasing order, where S_0 = {0}, and S_n is obtained by applying the operations x -> x+1 and x -> 2*x to S_{n-1}.

0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 36, 40, 48, 64

Offset: 0

Author

N. J. A. Sloane, Jan 12 2022, following a suggestion from James Propp

Keywords

• nonn
• tabf

Comments

Theorem: S_n contains Fibonacci(n+2) elements.

Proof from Adam P. Goucher, Jan 12 2022 (Start)

Let 'D' and 'I' be the 'double' and 'increment' operators, acting on 0 from the right. Then every element of S_n can be written as a length-n word over {D,I}. E.g., S_4 contains

0: DDDD

1: DDDI

2: DDID

3: DIDI

4: DIDD

5: IDDI

6: IDID

8: IDDD

We can avoid having two adjacent 'I's (because we can transform it into an equivalent word by prepending a 'D' -- which has no effect -- and then replacing the first 'DII' with 'ID').

Subject to the constraint that there are no two adjacent 'I's, these 'II'-less words all represent distinct integers (because of the uniqueness of binary expansions).

So we're left with the problem of enumerating length-n words over the alphabet {I, D} which do not contain 'II' as a substring. These are easily seen to be the Fibonacci numbers because we can check n=0 and n=1 and verify that the recurrence relation holds since a length-n word is either a length-(n-1) word followed by 'D' or a length-(n-2) word followed by 'DI'. QED (End)

From Rémy Sigrist, Jan 12 2022: (Start)

For any m >= 0, the value m first appears on row A056792(m).

For any n > 0: row n minus row n-1 corresponds to row n of A243571.

(End)

Examples

			The first few sets S_n are:
[0],
[0, 1],
[0, 1, 2],
[0, 1, 2, 3, 4],
[0, 1, 2, 3, 4, 5, 6, 8],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 28, 32, 33, 34, 36, 40, 48, 64],
...
		

Links

• Alois P. Heinz, Rows n = 0..21, flattened

Crossrefs

Cf. A000045, A000126, A002977, A056792, A122554, A243571, A350604.

Programs

Maple

T:= proc(n) option remember; `if`(n=0, 0,
      sort([map(x-> [x+1, 2*x][], {T(n-1)})[]])[])
    end:
seq(T(n), n=0..8);  # Alois P. Heinz, Jan 12 2022

Mathematica

T[n_] := T[n] = If[n==0, {0}, {#+1, 2#}& /@ T[n-1] // Flatten //
      Union];
Table[T[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, May 06 2022, after Alois P. Heinz *)

Python

from itertools import chain, islice
def A350603_gen(): # generator of terms
    s = {0}
    while True:
        yield from sorted(s)
        s = set(chain.from_iterable((x+1,2*x) for x in s))
A350603_list = list(islice(A350603_gen(),30)) # Chai Wah Wu, Jan 12 2022

Extensions

Definition made more precise by Chai Wah Wu, Jan 12 2022