OFFSET
0,6
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)
LINKS
Alois P. Heinz, Rows n = 0..21, flattened
EXAMPLE
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],
...
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 *)
PROG
(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))
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
N. J. A. Sloane, Jan 12 2022, following a suggestion from James Propp.
EXTENSIONS
Definition made more precise by Chai Wah Wu, Jan 12 2022
STATUS
approved