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

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, 17, 34, 32, 31, 62, 28, 27, 54, 25, 50, 48, 47, 94, 21, 42, 40, 39, 78, 36, 35, 70, 33, 66, 64, 63, 126, 29, 58, 56, 55, 110, 52, 51, 102, 49, 98, 96, 95, 190, 44

Offset: 1

Author

Clark Kimberling, Nov 28 2013

Keywords

• nonn
• easy
• tabf

Comments

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.

Seen as triangle read by rows: A082560 with duplicates removed. - Reinhard Zumkeller, May 14 2015

Examples

			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).
First 5 generations, also showing the places where duplicates were removed:
.  1:                                1
.  2:                2                               4
.  3:        3              6               5                10
.  4:    _       8      7       14      _       12       11       22
.  5:  _  __   9  18  _  16  15   30  _  __  13   26  __   24  23   46
These are the corresponding complete rows of triangle A082560:
.  1:                                1
.  2:                2                               4
.  3:        3              6               5                10
.  4:    4       8      7       14      6       12       11       22
.  5:  5  10   9  18  8  16  15   30  7  14  13   26  12   24  23   46
		

Links

• Clark Kimberling and Reinhard Zumkeller, Rows n = 1..17 of triangle, flattened, first 13 rows from Clark Kimberling
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

Cf. A232559, A232639, A232643, A000045.

Cf. A128588 (row lengths), A033484 (right edges), A257956 (row sums), A082560.

Programs

Haskell

import Data.List.Ordered (member); import Data.List (sort)
a232642 n k = a232642_tabf !! (n-1) !! (k-1)
a232642_row n = a232642_tabf !! (n-1)
a232642_tabf = f a082560_tabf [] where
   f (xs:xss) zs = ys : f xss (sort (ys ++ zs)) where
     ys = [v | v <- xs, not $ member v zs]
a232642_list = concat a232642_tabf
-- Reinhard Zumkeller, May 14 2015

Mathematica

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 *)
Table[Length[g1[n]], {n, 1, z}]  (* A000045 *)
Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232643 *)

Extensions

Keyword tabf added, to bring out function g, by Reinhard Zumkeller, May 14 2015