A232559 Sequence (or tree) generated by these rules: 1 is in S, and if x is in S, then x + 1 and 2*x are in S, and duplicates are deleted as they occur.

1, 2, 3, 4, 6, 5, 8, 7, 12, 10, 9, 16, 14, 13, 24, 11, 20, 18, 17, 32, 15, 28, 26, 25, 48, 22, 21, 40, 19, 36, 34, 33, 64, 30, 29, 56, 27, 52, 50, 49, 96, 23, 44, 42, 41, 80, 38, 37, 72, 35, 68, 66, 65, 128, 31, 60, 58, 57, 112, 54, 53, 104, 51, 100, 98, 97

Offset

1,2

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 are in S. Then S is the set of all 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,4), g(4) = (6,5,8), g(5) = (7,12,10,9,16), etc. Concatenating these gives A232559, a permutation of the positive integers. The number of numbers in g(n) is A000045(n), the n-th Fibonacci number. It is helpful to show the results as a tree with the terms of S as nodes and edges from x to x + 1 if x + 1 has not already occurred, and an edge from x to 2*x if 2*x has not already occurred. The positions of the odd numbers are given by A026352, and of the evens, by A026351.

The previously mentioned tree is an example of a fractal tree; that is, an infinite rooted tree T such that every complete subtree of T contains a subtree isomorphic to T. - Clark Kimberling, Jun 11 2016

The similar sequence S', generated by these rules: 0 is in S', and if x is in S', then 2*x and x+1 are in S', and duplicates are deleted as they occur, appears to equal A048679. - Rémy Sigrist, Aug 05 2017

From Katherine E. Stange and Glen Whitney, Oct 09 2021: (Start)

The beginning of this tree is

1

|

2

/ \

3..../ \......4

| / \

6 5.../ \...8

/ \ | / \

7/ \12 10 9/ \16

This tree contains every positive integer, and one can show that the path from 1 to the integer n is exactly the sequence of intermediate values observed during the Double-And-Add Algorithm AKA Chandra Sutra Method (namely, the algorithm which begins with m = 0, reads the binary representation of n from left to right, and, for each digit 0 read, doubles m, and for each digit 1 read, doubles m and then adds 1 to m; when the algorithm terminates, m = n).

As such, the path between 1 and n is a function of the binary expansion of n. The elements of the k-th row of the tree (generation g(k)) are all those elements whose binary expansion has k_1 digits and Hamming weight k_2, for some k_1 and k_2 such that k_1 + k_2 = k + 1.

The depth at which integer n appears in this tree is given by A014701(n) = A056792(n)-1. For example, the depth of 1 is 0, the depth of 2 is 1, and the depths of 3 and 4 are both 2. (End)

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Clark Kimberling)

Katherine E. Stange, The Intuition behind the Double-And-Add / Square-And-Multiply Algorithm, YouTube video, 2021.

Index entries for sequences that are permutations of the natural numbers

Formula

a(n) = A059894(A348366(n)) for n > 0. - Mikhail Kurkov, Jun 14 2022

Example

Each x begets x + 1 and 2*x, but if either has already occurred it is deleted.  Thus, 1 begets 2, which begets (3,4); from which 3 begets only 6, and 4 begets (5,8).

Maple

a:= proc() local l, s; l, s:= [1], {1}:
      proc(n) option remember; local i, r; r:= l[1];
        l:= subsop(1=NULL, l);
        for i in [1+r, r+r] do if not i in s then
          l, s:=[l[], i], s union {i} fi
        od; r
      end
    end():
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 06 2017

Mathematica

z = 12; g[1] = {1}; g[2] = {2}; g[n_] := Riffle[g[n - 1] + 1, 2 g[n - 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}]]  (* A232559 *)
Table[Length[g1[n]], {n, 1, z}] (* Fibonacci numbers *)
t1 = Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232560 *)

Prog

(Python)
def aupton(terms):
    alst, S, expand = [1, 2], {1, 2}, [2]
    while len(alst) < terms:
        x = expand.pop(0)
        new_elts = [y for y in [x+1, 2*x] if y not in S]
        alst.extend(new_elts); expand.extend(new_elts); S.update(new_elts)
    return alst[:terms]
print(aupton(66)) # Michael S. Branicky, Sep 14 2021
(PARI) b(n) = (3<<logint(n, 2) - n) >> (valuation(n, 2) + 1); \\ here b(n) = A059894(A030109(n)) with A059894(0) = 1
my(z=2); for(k=1, 299, while(!(logint(z-1, 2) - hammingweight(z-1)==valuation(z, 2)), z++); print1(b(z), ", "); z++); \\ Mikhail Kurkov, Jun 14 2022

Crossrefs

Cf. A232560 (inverse permutation), A232561, A232563, A226080, A226130.

Cf. A000045, A026352, A026351, A048679.

Cf. A243571 (rows sorted).

Cf. A014701, A056792.

Sequence in context: A299759 A232560 A183090 * A094138 A116538 A084287

Adjacent sequences: A232556 A232557 A232558 * A232560 A232561 A232562

Keyword

nonn,easy

Author

Clark Kimberling, Nov 26 2013

Status

approved