login
a(n)=0 if n is in A259934, otherwise 1 + number of steps to reach the farthest leaf in that finite branch of the tree defined by edge-relation A049820(child) = parent.
9

%I #12 Oct 04 2015 13:11:17

%S 0,4,0,3,2,2,0,1,1,24,3,23,0,1,2,22,2,21,0,1,1,20,0,19,1,1,3,18,1,17,

%T 0,16,2,1,0,15,1,1,10,14,1,2,0,1,2,13,0,12,9,1,1,11,1,10,0,1,1,9,0,8,

%U 8,7,0,1,1,6,1,1,1,5,0,4,7,3,1,1,13,2,0,1,2,12,4,11,6,1,3,10,1,5,0,9,2,4,0,8,5,7,1,3,1,2,0,1,4,6,0,5,1,1,2,4,1,1,0,3,1,1,0,2,3

%N a(n)=0 if n is in A259934, otherwise 1 + number of steps to reach the farthest leaf in that finite branch of the tree defined by edge-relation A049820(child) = parent.

%H Antti Karttunen, <a href="/A262695/b262695.txt">Table of n, a(n) for n = 0..17724</a>

%F If A262693(n) = 1 [when n is in A259934],

%F then a(n) = 0,

%F otherwise, if A060990(n) = 0 [when n is one of the leaves, A045765],

%F then a(n) = 1,

%F otherwise:

%F a(n) = 1 + Max_{k = A082284(n) .. A262686(n)} [A049820(k) = n] * a(k).

%F (In the last clause [ ] stands for Iverson bracket, giving as its result 1 only when A049820(k) = n, and 0 otherwise).

%e For n=1, its transitive closure (as defined by edge-relation A049820(child) = parent) is the union of {1} itself together with all its descendants: {1, 3, 4, 5, 7, 8}. We see that there are no other nodes in this subtree whose root is 1, because A049820(3) = 3 - d(3) = 1, A049820(4) = 1, A049820(5) = 3, A049820(7) = 5, A049820(8) = 4 and of these only 7 and 8 are terms of A045765 (leaves). Starting iterating from 7 with A049820, we get 7 -> 5, 5 -> 3, 3 -> 1, and starting from 8 we get 8 -> 4, 4 -> 1, of which the former path is longer (3 steps), thus a(1) = 3+1 = 4.

%e For n=9, its transitive closure is {9, 11, 13, 15, 16, 17, 19, 21, 23, 24, 27, 29, 31, 33, 35, 36, 37, 39, 41, 43, 45, 47, 51, 53, 55, 57, 59, 61, 63, 64, 65, 67, 69, 71, 73, 75, 77, 79}. In this case the longest path is obtained by starting iterating from the largest of these: 79 -> 77 -> 73 -> 71 -> 69 -> 65 -> 61 -> 59 -> 57 -> 53 -> 51 -> 47 -> 45 -> 39 -> 35 -> 31 -> 29 -> 27 -> 23 -> 21 -> 17 -> 15 -> 11 -> 9, which is 23 steps long, thus a(9) = 23+1 = 24.

%o (Scheme, with memoization-macro definec)

%o (definec (A262695 n) (cond ((= 1 (A262693 n)) 0) (else (let loop ((s 0) (k (A262686 n))) (cond ((<= k n) (+ 1 s)) ((= n (A049820 k)) (loop (max s (A262695 k)) (- k 1))) (else (loop s (- k 1))))))))

%Y Cf. A000005, A045765, A049820, A060990, A082284, A259934, A262686, A262693.

%Y Cf. A262522, A262696, A262697.

%Y Cf. also A213725.

%K nonn

%O 0,2

%A _Antti Karttunen_, Oct 04 2015