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)
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
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
FORMULA
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}]] (* this sequence *)
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
CROSSREFS
Cf. A243571 (rows sorted).
KEYWORD
nonn,easy
AUTHOR
Clark Kimberling, Nov 26 2013
STATUS
approved