cp's OEIS Frontend

A257265 Distance to n from a leaf nearest to n in the binary beanstalk.

%I A257265 #31 Jul 13 2022 20:38:13
%S A257265 2,1,0,1,1,0,0,1,2,0,1,1,0,0,0,1,2,0,1,2,0,0,1,1,0,1,1,0,0,0,0,1,2,0,
%T A257265 1,2,0,0,1,1,0,1,2,0,0,0,1,1,0,1,1,0,0,2,1,0,1,1,0,0,0,0,0,1,2,0,1,2,
%U A257265 0,0,1,1,0,1,2,0,0,0,1,1,0,1,1,0,0,2,1,0,1,2,0,0,0,0,1,1,0,1,1,0,0,2,1,0,1,1,0,0,0,2,1,0,2,1,0,0,1,1,0,1,1,0,0,0,0,0,0,1,2
%N A257265 Distance to n from a leaf nearest to n in the binary beanstalk.
%C A257265 If n is one of the terms of A055938 (that is, one of the leaves of the binary beanstalk), then a(n) is zero. Otherwise, a(n) is the least number of iterations of A011371 required to reach n, when we start from any term of A055938.
%C A257265 Compare to the definition of A213725, which gives 1 + distance to the farthest leaf in the binary beanstalk (giving 0 for the nodes which reside in A179016, the infinite stem of the beanstalk, as there the maximum distance would not have a finite value).
%C A257265 Note that although the recursive formula given here mirrors the one given at A213725, it cannot be implemented in a naive way, precisely because of that infinite stem, as it would lead to recursion without end. Instead, with ordinary eagerly evaluating programming languages we have to employ, for example, a breadth-first search, as in the given Scheme-program.
%C A257265 Question: Will there ever appear a term larger than 2? (Only terms 0 - 2 occur in range 0 .. 2097151).
%H A257265 Antti Karttunen, <a href="/A257265/b257265.txt">Table of n, a(n) for n = 0..16384</a>
%H A257265 Ela, <a href="http://elalang.net/docs/Article.aspx?p=lib%5Cpeano.htm">peano</a>
%H A257265 Haskell Wiki, <a href="https://wiki.haskell.org/Peano_numbers">Peano numbers</a>
%H A257265 Paul Tek, <a href="/A179016/a179016.png">Illustration of how natural numbers in range 0 .. 133 are organized as a binary tree in the binary beanstalk</a>
%F A257265 If A079559(n) = 0, then a(n) = 0, otherwise a(n) = 1 + min(a(A213723(n)), a(A213724(n))). [But please see the comments above.]
%e A257265 For 0, the nearest leaf is 2, as when we start from 2, and always subtract the binary weight, A000120, we have: 2 - A000120(2) = A011371(2) = 1, and A011371(1) = 0, thus it takes two steps to get to 0, and there are no other terms of A055938 from which it would take fewer steps), so a(0) = 2, and also a(1) = 1, because it's one step nearer to 2.
%e A257265 a(2) = 0, because 2 is one of the terms of A055938.
%e A257265 a(8) = 2, because 12, 13 and 14 are the three nearest leaves to 8, and A011371(12) = A011371(13) = 10, A011371(14) = 11, A011371(10) = A011371(11) = 8 (thus it takes two iterations of A011371 to reach 8 from any of those three leaves) and there are no leaves nearer.
%e A257265 Please see also Paul Tek's illustration.
%o A257265 (Scheme)
%o A257265 ;; Do a breadth-first search over the descendants, which are at each step of iteration sorted by their distance from the starting node.
%o A257265 (define (A257265 n) (let loop ((descendants (list (cons 0 n)))) (let ((dist (caar descendants)) (node (cdar descendants))) (cond ((zero? (A079559 node)) dist) (else (loop (sort (append (list (cons (+ 1 dist) (A213724 node)) (cons (+ 1 dist) (A213723 node))) (cdr descendants)) (lambda (a b) (< (car a) (car b))))))))))
%o A257265 (Haskell)
%o A257265 a257265 = length . us where
%o A257265    us n = if a079559 n == 0
%o A257265              then [] else () : zipWith (const $ const ())
%o A257265                                (us $ a213723 n) (us $ a213724 n)
%o A257265 -- _Reinhard Zumkeller_, May 03 2015
%Y A257265 Cf. A055938 (positions of 0's), A257508 (of 1's), A257509 (of 2's).
%Y A257265 Cf. also A000120, A011371, A079559, A213723, A213724.
%Y A257265 Cf. also A179016, A213725, A257264.
%K A257265 nonn
%O A257265 0,1
%A A257265 _Antti Karttunen_, Apr 29 2015