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

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

Offset: 0

Author

Antti Karttunen, Apr 29 2015

Keywords

• nonn

Comments

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.

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

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.

Question: Will there ever appear a term larger than 2? (Only terms 0 - 2 occur in range 0 .. 2097151).

Examples

			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.
a(2) = 0, because 2 is one of the terms of A055938.
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.
Please see also Paul Tek's illustration.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..16384
• Ela, peano
• Haskell Wiki, Peano numbers
• Paul Tek, Illustration of how natural numbers in range 0 .. 133 are organized as a binary tree in the binary beanstalk

Crossrefs

Cf. A055938 (positions of 0's), A257508 (of 1's), A257509 (of 2's).

Cf. also A000120, A011371, A079559, A213723, A213724.

Cf. also A179016, A213725, A257264.

Programs

Haskell

a257265 = length . us where
   us n = if a079559 n == 0
             then [] else () : zipWith (const $ const ())
                               (us $ a213723 n) (us $ a213724 n)
-- Reinhard Zumkeller, May 03 2015

Scheme

;; Do a breadth-first search over the descendants, which are at each step of iteration sorted by their distance from the starting node.
(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))))))))))

Formula

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