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

Author

Clark Kimberling, Nov 26 2013

Keywords

• nonn
• easy

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)

Definition need not invoke deletion: Tree is rooted at 1, all even nodes have x+1 as a child, all nodes have 2*x as a child, and any x+1 child precedes its sibling. - Robert Munafo, May 08 2024

Examples

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

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.
• Dimitri Zucker, I Found a Simple Pattern That Encodes Different Bases, YouTube video, 2024. (Adds 0 above the root of the tree, and shows how to reconstruct the tree backwards from child nodes)
• Robert Munafo, Sequences A232559 and A232561, Spanning Trees of N
• Index entries for sequences that are permutations of the natural numbers

Crossrefs

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

Cf. A000045, A026352, A026351, A048679.

Cf. A243571 (rows sorted).

Cf. A014701, A056792.

Programs

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}]]  (* this sequence *)
Table[Length[g1[n]], {n, 1, z}] (* Fibonacci numbers *)
t1 = Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232560 *)

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

Formula

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