A389228 a(n) is the length of the shortest path in the rooted tree T_n defined in A390207 and in the comments.

0, 1, 2, 2, 2, 1, 4, 3, 2, 2, 2, 2, 4, 3, 4, 4, 4, 1, 4, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 3, 6, 5, 3, 3, 4, 2, 4, 3, 4, 2, 4, 2, 4, 2, 4, 2, 2, 2, 4, 4, 4, 4, 4, 1, 4, 4, 4, 4, 4, 4, 6, 5, 4, 6, 4, 4, 5, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 2, 4, 4, 4, 2, 4, 3, 4, 2

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.

Links

Miles Englezou, Table of n, a(n) for n = 1..10000

Formula

a(n) = 1 if and only if n = 2*3^k, k >= 0.

Example

a(2) = 1 since the shortest path is {2, 3}.
a(3) = 2 since the shortest path is {3, 4, 2}.
a(8) = 3 since the shortest path is {8, 12, 6, 9}.
a(19) = 4 since the shortest path is {19, 20, 10, 12, 8}.
The tree T_19 looks like this:
             19
             |
             20
            /   \
           /     \
         10       16
        /  \      |
      12    15    24
     /  \   |     |
    6    8  12    12
   / \     /  \   |
  8   9   16  18  18
  |       |   |   |
  4       8   9   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,
            if(#T > 0 && #path >= T[#T], break);
            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);
        );
    );
    vecmin(T) - 1;
}

Crossrefs

Cf. A333123, A389370, A390207.

Sequence in context: A089400 A239209 A180824 * A105777 A014572 A071458

Adjacent sequences: A389225 A389226 A389227 * A389229 A389230 A389231

Keyword

nonn

Author

Miles Englezou, Dec 01 2025

Status

approved