

A262695


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 edgerelation A049820(child) = parent.


9



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


LINKS

Antti Karttunen, Table of n, a(n) for n = 0..17724


FORMULA

If A262693(n) = 1 [when n is in A259934],
then a(n) = 0,
otherwise, if A060990(n) = 0 [when n is one of the leaves, A045765],
then a(n) = 1,
otherwise:
a(n) = 1 + Max_{k = A082284(n) .. A262686(n)} [A049820(k) = n] * a(k).
(In the last clause [ ] stands for Iverson bracket, giving as its result 1 only when A049820(k) = n, and 0 otherwise).


EXAMPLE

For n=1, its transitive closure (as defined by edgerelation 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.
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.


PROG

(Scheme, with memoizationmacro definec)
(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))))))))


CROSSREFS

Cf. A000005, A045765, A049820, A060990, A082284, A259934, A262686, A262693.
Cf. A262522, A262696, A262697.
Cf. also A213725.
Sequence in context: A301408 A227290 A096303 * A021252 A195775 A316260
Adjacent sequences: A262692 A262693 A262694 * A262696 A262697 A262698


KEYWORD

nonn


AUTHOR

Antti Karttunen, Oct 04 2015


STATUS

approved



