OFFSET
1,3
COMMENTS
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.
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.
LINKS
Miles Englezou, Table of n, a(n) for n = 1..1494
EXAMPLE
a(2) = 1 since the longest path is {2, 3}.
a(3) = 2 since the longest path is {3, 4, 2}.
a(10) = 4 since one of its longest paths is {10, 12, 6, 8, 4}.
a(15) = 6 since one of its longest paths is {15, 18, 9, 12, 6, 8, 4}.
The tree T_15 looks like this:
15
/ \
18 20
/ \ / \
9 12 10 16
| | | |
12 16 12 24
/ \ | / \ |
6 8 8 6 8 12
| | |
8 8 18
| | |
4 4 9
PROG
(PARI)
a(n) =
{
if(n == 1, return(0));
my(T = []);
my(S = [[n, 0, [n]]]);
while(#S,
my(t = S[#S]);
S = S[1..#S-1];
my(r = t[1], m = t[2], path = t[3]);
my(P = factor(r)[, 1]);
my(has_child = 0);
for(i = 1, #P,
my(d = r/P[i]);
my(s = r + (-1)^m * d);
if(!setsearch(path, s),
has_child = 1;
my(newpath = setunion(path, [s]));
S = concat(S, [[s, m+1, newpath]]);
);
);
if(!has_child,
T = concat(T, #path)
);
);
vecmax(T) - 1;
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Miles Englezou, Dec 02 2025
STATUS
approved