cp's OEIS Frontend

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

%I A350603 #47 Jul 09 2025 04:57:48
%S A350603 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,
%T A350603 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,
%U A350603 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
%N 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}.
%C A350603 Theorem: S_n contains Fibonacci(n+2) elements.
%C A350603 Proof from _Adam P. Goucher_, Jan 12 2022 (Start)
%C A350603 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
%C A350603    0: DDDD
%C A350603    1: DDDI
%C A350603    2: DDID
%C A350603    3: DIDI
%C A350603    4: DIDD
%C A350603    5: IDDI
%C A350603    6: IDID
%C A350603    8: IDDD
%C A350603 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').
%C A350603 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).
%C A350603 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)
%C A350603 From _Rémy Sigrist_, Jan 12 2022: (Start)
%C A350603 For any m >= 0, the value m first appears on row A056792(m).
%C A350603 For any n > 0: row n minus row n-1 corresponds to row n of A243571.
%C A350603 (End)
%H A350603 Alois P. Heinz, <a href="/A350603/b350603.txt">Rows n = 0..21, flattened</a>
%e A350603 The first few sets S_n are:
%e A350603 [0],
%e A350603 [0, 1],
%e A350603 [0, 1, 2],
%e A350603 [0, 1, 2, 3, 4],
%e A350603 [0, 1, 2, 3, 4, 5, 6, 8],
%e A350603 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 16],
%e A350603 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32],
%e A350603 [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],
%e A350603 ...
%p A350603 T:= proc(n) option remember; `if`(n=0, 0,
%p A350603       sort([map(x-> [x+1, 2*x][], {T(n-1)})[]])[])
%p A350603     end:
%p A350603 seq(T(n), n=0..8);  # _Alois P. Heinz_, Jan 12 2022
%t A350603 T[n_] := T[n] = If[n==0, {0}, {#+1, 2#}& /@ T[n-1] // Flatten //
%t A350603       Union];
%t A350603 Table[T[n], {n, 0, 8}] // Flatten (* _Jean-François Alcover_, May 06 2022, after _Alois P. Heinz_ *)
%o A350603 (Python)
%o A350603 from itertools import chain, islice
%o A350603 def A350603_gen(): # generator of terms
%o A350603     s = {0}
%o A350603     while True:
%o A350603         yield from sorted(s)
%o A350603         s = set(chain.from_iterable((x+1,2*x) for x in s))
%o A350603 A350603_list = list(islice(A350603_gen(),30)) # _Chai Wah Wu_, Jan 12 2022
%Y A350603 Cf. A000045, A000126, A002977, A056792, A122554, A243571, A350604.
%K A350603 nonn,tabf
%O A350603 0,6
%A A350603 _N. J. A. Sloane_, Jan 12 2022, following a suggestion from _James Propp_
%E A350603 Definition made more precise by _Chai Wah Wu_, Jan 12 2022