A389370 - OEIS

%I #60 Dec 10 2025 16:11:23

%S 0,1,2,2,4,2,4,3,4,4,4,2,6,6,6,4,6,4,6,8,7,9,4,3,8,8,6,6,8,7,6,5,10,6,

%T 10,4,8,10,10,8,9,8,11,12,9,16,5,4,8,12,8,11,8,6,12,10,12,11,9,10,12,

%U 12,10,6,12,14,8,10,16,12,6,4,10,12,14,11,14,10,10,12,8

%N a(n) is the length of the longest path in the rooted tree T_n defined in A390207 and in the comments.

%C T_n is constructed in the following way. With k_0 = n as the root, let k_i be a vertex of depth i. For a prime divisor p_i of k_i, let d_i = k_i/p_i. If m = k_i + (-1)^i*d_i does not appear in the path from k_0 to k_i, then m = k_{i+1}. Otherwise k_i is a terminal vertex.

%C T_n is finite for n > 0, and therefore a(n) is a positive integer for every n. See the Englezou link in A390207 for a proof.

%H Miles Englezou, <a href="/A389370/b389370.txt">Table of n, a(n) for n = 1..1494</a>

%e a(2) = 1 since the longest path is {2, 3}.

%e a(3) = 2 since the longest path is {3, 4, 2}.

%e a(10) = 4 since one of its longest paths is {10, 12, 6, 8, 4}.

%e a(15) = 6 since one of its longest paths is {15, 18, 9, 12, 6, 8, 4}.

%e The tree T_15 looks like this:

%e            15

%e          /    \

%e       18       20

%e      /  \     /   \

%e     9    12  10   16

%e     |    |   |    |

%e     12   16  12   24

%e    /  \  |  /  \  |

%e   6    8 8 6    8 12

%e   |        |      |

%e   8        8      18

%e   |        |      |

%e   4        4      9

%o (PARI)

%o a(n) =

%o {

%o     if(n == 1, return(0));

%o     my(T = []);

%o     my(S = [[n, 0, [n]]]);

%o     while(#S,

%o         my(t = S[#S]);

%o         S = S[1..#S-1];

%o         my(r = t[1], m = t[2], path = t[3]);

%o         my(P = factor(r)[, 1]);

%o         my(has_child = 0);

%o         for(i = 1, #P,

%o             my(d = r/P[i]);

%o             my(s = r + (-1)^m * d);

%o             if(!setsearch(path, s),

%o                 has_child = 1;

%o                 my(newpath = setunion(path, [s]));

%o                 S = concat(S, [[s, m+1, newpath]]);

%o             );

%o         );

%o         if(!has_child,

%o             T = concat(T, #path)

%o         );

%o     );

%o     vecmax(T) - 1;

%o }

%Y Cf. A333123, A389228, A390207.

%K nonn

%O 1,3

%A _Miles Englezou_, Dec 02 2025