|
%I #8 Aug 20 2017 23:20:17
%S 1,2,3,4,5,7,6,9,8,13,11,10,17,15,14,25,12,21,19,18,33,16,29,27,26,49,
%T 23,22,41,20,37,35,34,65,31,30,57,28,53,51,50,97,24,45,43,42,81,39,38,
%U 73,36,69,67,66,129,32,61,59,58,113,55,54,105,52,101,99
%N Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x - 1 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 - 1 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), g(3) = (3), g(4) = (4,5), etc. Concatenating these gives A232638, a permutation of the positive integers. For n > 1, the number of numbers in g(n) is 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 - 1 if 2*x - 1 has not already occurred.
%H Clark Kimberling, <a href="/A232638/b232638.txt">Table of n, a(n) for n = 1..1000</a>
%e Each x begets x + 1 and 2*x - 1, but if either has already occurred it is deleted. Thus, 1 begets 2, which begets 3, which begets 4 and 5, which beget 7 and (6,8), respectively.
%t z = 14; g[1] = {1}; g[2] = {2}; g[n_] := Riffle[g[n - 1] + 1, 2 g[n - 1] - 1]; 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}]] (* A232638 *)
%t Table[Length[g1[n]], {n, 1, z}] (* A000045 *)
%t Flatten[Table[Position[t, n], {n, 1, 200}]] (* A232639 *)
%Y Cf. A000045, A232559, A232639.
%K nonn,easy
%O 1,2
%A _Clark Kimberling_, Nov 28 2013
|
