login
Breadth-first traversal of the tree defined by the edge-relation A049820(child) = parent.
21

%I #48 Mar 18 2020 04:16:01

%S 0,1,2,3,4,6,5,8,9,10,12,7,11,14,18,13,15,16,20,22,17,24,25,26,28,30,

%T 19,21,32,34,23,40,38,42,27,44,48,46,29,36,50,56,60,49,52,54,31,33,72,

%U 58,35,84,62,66,37,39,96,68,70,41,45,104,108,74,76,78,80,43,47,120,81,82,90,88,51,128,132,83,85,86,94,53,55,136,140,87,92,102

%N Breadth-first traversal of the tree defined by the edge-relation A049820(child) = parent.

%C It is conjectured that the terms of A259934 trace the only infinite path in this tree.

%C After the root (0), the tree narrows next time to the width of just one node at level A262508(1) = 9236, with vertex 119143.

%H Antti Karttunen, <a href="/A263267/b263267.txt">Table of n, a(n) for n = 0..10425; levels 0 .. 1001 of the tree</a>

%H Michael De Vlieger, <a href="https://oeis.org/A263267/a263267_3.pdf">Poster illustrating A259934 and A263267</a>

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

%e Rows 0 - 21 of the table. The lines show the nodes of the tree connected by the edge-relation A049820(child) = parent:

%e 0;

%e | \

%e 1, 2;

%e | \ \

%e 3, 4, 6;____

%e | | | \ \

%e 5, 8, 9, 10, 12;

%e | | | |

%e 7, _ 11, 14, 18;

%e / | \ \ \

%e 13, 15, 16, 20, 22;____

%e | | / | \ \

%e 17, 24, 25, 26, 28, 30;

%e | \ | |

%e 19, 21, 32, 34;

%e | | | \

%e 23, 40, 38, 42;____

%e | | \ \

%e 27, 44, 48, 46;____

%e | \ | | \ | \ \

%e 29, 36, 50, 56, 60, 49, 52, 54;

%e | \ | |

%e 31, 33, 72, 58;

%e | | | \

%e 35, 84, 62, 66;

%e | \ | | \

%e 37, 39, 96, 68, 70;_______

%e | \ | \ / | \ \

%e 41, 45, 104, 108, 74, 76, 78, 80;

%e | | | | | \ \

%e 43, 47, 120, _81, 82, 90, 88;

%e | | \ / | | |

%e 51, 128, 132, 83, 85, 86, 94;

%e | \ | \ | | |

%e 53, 55 136, 140 87, 92, 102;______

%e | | \ | | \ \

%e 57,_ 89, 91, 98, 106, 110, 112;

%e / | \ / / \ | |

%e 59, 63, 64, 93, 95, 100, 114, 116;

%e | | | | \

%e 61, 99, 97, _118, 126;

%e | | | / | \

%e 65, 101, 105, 121, 122, 124;

%e (See also _Michael De Vlieger_'s poster in the Links section.)

%o (PARI)

%o uplim = 125753; \\ = A263260(10001).

%o checklimit = 1440; \\ Hard limit 1440 good for at least up to A002182(67) = 1102701600 as A002183(67) = 1440.

%o v263267 = vector(uplim);

%o A263267 = n -> if(!n,n,v263267[n]);

%o z = 0; for(n=0, uplim, t = A263267(n); write("b263267.txt", n, " ", t); for(k=t+1, t+checklimit, if((k-numdiv(k)) == t, z++; if(z <= uplim, v263267[z] = k))));

%o (Sage) # After _David Eppstein_'s Python-code for A088975.

%o def A263267():

%o '''Breadth-first reading of irregular tree defined by the edge-relation A049820(child) = parent'''

%o yield 0

%o for x in A263267():

%o for k in [x+1 .. 2*(x+1)]:

%o if ((k - sloane.A000005(k)) == x): yield k

%o def take(n,g):

%o '''Returns a list composed of the next n elements returned by generator g.'''

%o return [next(g) for _ in range(n)]

%o take(120, A263267())

%o (Scheme)

%o ;; This version creates the list of terms incrementally, using append! function that physically modifies the list at the same time as it is traversed. Otherwise the idea is essentially the same as with Python/Sage-program above:

%o (define (A263267list_up_to_n_terms_at_least n) (let ((terms-produced (list 0))) (let loop ((startp terms-produced) (endp terms-produced) (k (- n 1))) (cond ((<= k 0) terms-produced) (else (let ((children (children-of-n-in-A049820-tree (car startp)))) (cond ((null? children) (loop (cdr startp) endp k)) (else (begin (append! endp children) (loop (cdr startp) children (- k (length children))))))))))))

%o (define (children-of-n-in-A049820-tree n) (let loop ((k (A262686 n)) (children (list))) (cond ((<= k n) children) ((= (A049820 k) n) (loop (- k 1) (cons k children))) (else (loop (- k 1) children)))))

%Y Inverse permutation: A263268.

%Y Cf. A000005, A049820, A060990, A082284, A155043, A259934, A262508.

%Y Cf. A262507 (number of terms on row/level n), A263260 (total number of terms in levels 0 .. n).

%Y Cf. A264988 (the left edge), this differs from A261089 (the least term on each level) for the first time at level 69.

%Y Cf. A263269 (the right edge).

%Y Cf. A262686 (maximum term on the level n).

%Y Cf. A045765 (the leaves of the tree).

%Y Cf. also permutations A263265 (obtained from this table by sorting each row into ascending order), A263266.

%Y Cf. also arrays A265751 and A263271.

%Y Differs from A263265 for the first time at n=31, where a(31) = 40, while A263265(31) = 38.

%Y Cf. also A088975.

%K nonn,tabf

%O 0,3

%A _Antti Karttunen_, Nov 27 2015