cp's OEIS Frontend

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.

%I A232559 #63 May 11 2024 21:38:07
%S A232559 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 A232559 21,40,19,36,34,33,64,30,29,56,27,52,50,49,96,23,44,42,41,80,38,37,72,
%U A232559 35,68,66,65,128,31,60,58,57,112,54,53,104,51,100,98,97
%N 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.
%C A232559 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 A232559 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 A232559 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 A232559 From _Katherine E. Stange_ and _Glen Whitney_, Oct 09 2021: (Start)
%C A232559 The beginning of this tree is
%C A232559                 1
%C A232559                 |
%C A232559                 2
%C A232559                / \
%C A232559          3..../   \......4
%C A232559          |              / \
%C A232559          6         5.../   \...8
%C A232559         / \        |          / \
%C A232559       7/   \12     10       9/   \16
%C A232559 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 A232559 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 A232559 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 A232559 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 A232559 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 A232559 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 A232559 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 A232559 Robert Munafo, <a href="http://mrob.com/pub/seq/a232561.html">Sequences A232559 and A232561, Spanning Trees of N</a>
%H A232559 <a href="/index/Per#IntegerPermutation">Index entries for sequences that are permutations of the natural numbers</a>
%F A232559 Conjecture: a(n) = A059894(A348366(n)) for n > 0. - _Mikhail Kurkov_, Jun 14 2022
%e A232559 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 A232559 a:= proc() local l, s; l, s:= [1], {1}:
%p A232559       proc(n) option remember; local i, r; r:= l[1];
%p A232559         l:= subsop(1=NULL, l);
%p A232559         for i in [1+r, r+r] do if not i in s then
%p A232559           l, s:=[l[], i], s union {i} fi
%p A232559         od; r
%p A232559       end
%p A232559     end():
%p A232559 seq(a(n), n=1..100);  # _Alois P. Heinz_, Aug 06 2017
%t A232559 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 A232559 Table[Length[g1[n]], {n, 1, z}] (* Fibonacci numbers *)
%t A232559 t1 = Flatten[Table[Position[t, n], {n, 1, 200}]]  (* A232560 *)
%o A232559 (Python)
%o A232559 def aupton(terms):
%o A232559     alst, S, expand = [1, 2], {1, 2}, [2]
%o A232559     while len(alst) < terms:
%o A232559         x = expand.pop(0)
%o A232559         new_elts = [y for y in [x+1, 2*x] if y not in S]
%o A232559         alst.extend(new_elts); expand.extend(new_elts); S.update(new_elts)
%o A232559     return alst[:terms]
%o A232559 print(aupton(66)) # _Michael S. Branicky_, Sep 14 2021
%Y A232559 Cf. A232560 (inverse permutation), A232561, A232563, A226080, A226130.
%Y A232559 Cf. A000045, A026352, A026351, A048679.
%Y A232559 Cf. A243571 (rows sorted).
%Y A232559 Cf. A014701, A056792.
%K A232559 nonn,easy
%O A232559 1,2
%A A232559 _Clark Kimberling_, Nov 26 2013