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