A232559 - OEIS

%I #63 May 11 2024 21:38:07

%S 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,

%T 21,40,19,36,34,33,64,30,29,56,27,52,50,49,96,23,44,42,41,80,38,37,72,

%U 35,68,66,65,128,31,60,58,57,112,54,53,104,51,100,98,97

%N 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.

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

%C 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

%C 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

%C From _Katherine E. Stange_ and _Glen Whitney_, Oct 09 2021: (Start)

%C The beginning of this tree is

%C                 1

%C                 |

%C                 2

%C                / \

%C          3..../   \......4

%C          |              / \

%C          6         5.../   \...8

%C         / \        |          / \

%C       7/   \12     10       9/   \16

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

%C 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.

%C 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)

%C 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

%H Alois P. Heinz, <a href="/A232559/b232559.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Clark Kimberling)

%H Katherine E. Stange, <a href="https://www.youtube.com/watch?v=5ITRACsmCvQ">The Intuition behind the Double-And-Add / Square-And-Multiply Algorithm</a>, YouTube video, 2021.

%H Dimitri Zucker, <a href="https://www.youtube.com/watch?v=wtIoCxz-eIc">I Found a Simple Pattern That Encodes Different Bases</a>, YouTube video, 2024. (Adds 0 above the root of the tree, and shows how to reconstruct the tree backwards from child nodes)

%H Robert Munafo, <a href="http://mrob.com/pub/seq/a232561.html">Sequences A232559 and A232561, Spanning Trees of N</a>

%H <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>

%F Conjecture: a(n) = A059894(A348366(n)) for n > 0. - _Mikhail Kurkov_, Jun 14 2022

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

%p a:= proc() local l, s; l, s:= [1], {1}:

%p       proc(n) option remember; local i, r; r:= l[1];

%p         l:= subsop(1=NULL, l);

%p         for i in [1+r, r+r] do if not i in s then

%p           l, s:=[l[], i], s union {i} fi

%p         od; r

%p       end

%p     end():

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Aug 06 2017

%t 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 *)

%t Table[Length[g1[n]], {n, 1, z}] (* Fibonacci numbers *)

%t t1 = Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232560 *)

%o (Python)

%o def aupton(terms):

%o     alst, S, expand = [1, 2], {1, 2}, [2]

%o     while len(alst) < terms:

%o         x = expand.pop(0)

%o         new_elts = [y for y in [x+1, 2*x] if y not in S]

%o         alst.extend(new_elts); expand.extend(new_elts); S.update(new_elts)

%o     return alst[:terms]

%o print(aupton(66)) # _Michael S. Branicky_, Sep 14 2021

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

%Y Cf. A000045, A026352, A026351, A048679.

%Y Cf. A243571 (rows sorted).

%Y Cf. A014701, A056792.

%K nonn,easy

%O 1,2

%A _Clark Kimberling_, Nov 26 2013