|
%I #14 Aug 20 2017 23:20:31
%S 1,2,4,3,6,5,10,8,7,14,12,11,22,9,18,16,15,30,13,26,24,23,46,20,19,38,
%T 17,34,32,31,62,28,27,54,25,50,48,47,94,21,42,40,39,78,36,35,70,33,66,
%U 64,63,126,29,58,56,55,110,52,51,102,49,98,96,95,190,44
%N Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x + 2 are in S, and duplicates are deleted as they occur.
%C Let S be the set of numbers defined by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x + 2 are in S. Then S is the set of positive integers, which arise in generations. Deleting duplicates as they occur, the generations are given by g(1) = (1), g(2) = (2,4), g(3) = (3,6,5,10), etc. Concatenating these gives A232642, a permutation of the positive integers. For n > 1, the number of numbers in g(n) is 2*F(n+1), where F = A000045, the Fibonacci numbers. It is helpful to show the results as a tree with the terms of S as nodes, an edge from x to x + 1 if x + 1 has not already occurred, and an edge from x to 2*x + 2 if 2*x + 2 has not already occurred.
%C Seen as triangle read by rows: A082560 with duplicates removed. - _Reinhard Zumkeller_, May 14 2015
%H Clark Kimberling and Reinhard Zumkeller, <a href="/A232642/b232642.txt">Rows n = 1..17 of triangle, flattened</a>, first 13 rows from Clark Kimberling
%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%e Each x begets x + 1 and 2*x + 2, but if either has already occurred it is deleted. Thus, 1 begets 2 and 4; then 2 begets 3 and 6, and 4 begets 5 and 10, so that g(3) = (3,6,5,10).
%e First 5 generations, also showing the places where duplicates were removed:
%e . 1: 1
%e . 2: 2 4
%e . 3: 3 6 5 10
%e . 4: _ 8 7 14 _ 12 11 22
%e . 5: _ __ 9 18 _ 16 15 30 _ __ 13 26 __ 24 23 46
%e These are the corresponding complete rows of triangle A082560:
%e . 1: 1
%e . 2: 2 4
%e . 3: 3 6 5 10
%e . 4: 4 8 7 14 6 12 11 22
%e . 5: 5 10 9 18 8 16 15 30 7 14 13 26 12 24 23 46
%t z = 14; g[1] = {1}; g[2] = {2}; g[n_] := Riffle[g[n - 1] + 1, 2 g[n - 1] + 2]; j[2] = Join[g[1], g[2]]; j[n_] := Join[j[n - 1], g[n]]; g1[n_] := DeleteDuplicates[DeleteCases[g[n], Alternatives @@ j[n - 1]]]; g1[1] = g[1]; g1[2] = g[2]; t = Flatten[Table[g1[n], {n, 1, z}]] (* A232642 *)
%t Table[Length[g1[n]], {n, 1, z}] (* A000045 *)
%t Flatten[Table[Position[t, n], {n, 1, 200}]] (* A232643 *)
%o (Haskell)
%o import Data.List.Ordered (member); import Data.List (sort)
%o a232642 n k = a232642_tabf !! (n-1) !! (k-1)
%o a232642_row n = a232642_tabf !! (n-1)
%o a232642_tabf = f a082560_tabf [] where
%o f (xs:xss) zs = ys : f xss (sort (ys ++ zs)) where
%o ys = [v | v <- xs, not $ member v zs]
%o a232642_list = concat a232642_tabf
%o -- _Reinhard Zumkeller_, May 14 2015
%Y Cf. A232559, A232639, A232643, A000045.
%Y Cf. A128588 (row lengths), A033484 (right edges), A257956 (row sums), A082560.
%K nonn,easy,tabf
%O 1,2
%A _Clark Kimberling_, Nov 28 2013
%E Keyword tabf added, to bring out function g, by _Reinhard Zumkeller_, May 14 2015
|
