login
A130790
Number of nodes in the Lucas-Pratt primality tree rooted at prime(n).
0
0, 1, 1, 2, 2, 2, 1, 2, 3, 3, 3, 2, 2, 4, 4, 3, 4, 3, 4, 4, 2, 4, 3, 3, 2, 2, 3, 4, 2, 3, 4, 4, 2, 5, 3, 3, 4, 2, 4, 5, 4, 3, 4, 2, 3, 4, 5, 4, 4, 4, 4, 4, 3, 2, 1, 5, 5, 3, 5, 4, 6, 3, 3, 5, 4, 5, 5, 4, 6, 5, 3, 5, 5, 5, 4, 5, 3, 4, 2, 3, 5, 5, 6, 2, 4, 4, 3, 4, 5, 6, 5, 5, 2, 4, 5, 3, 5, 4, 5, 3
OFFSET
1,4
COMMENTS
The primality tree starts at an odd prime at the root node. The branches of each node are the odd primes that divide the value of (the node minus 1). The length of the longest branch is related to A126805. Following the branch with the largest label gives A083647.
LINKS
J. Bayless, The Lucas-Pratt primality tree, Math. Comp. vol 77 (2008) 495-502.
PROG
(PARI) LP(p) = my(f=factor(p-1)); if(p <= 2, 0, 1+vecsum(vector(#f~, k, LP(f[k, 1]))));
a(n) = LP(prime(n)); \\ Daniel Suteu, Nov 03 2019
CROSSREFS
Cf. A037231 (primes which set a new record).
Sequence in context: A056691 A262982 A205011 * A261904 A297030 A266348
KEYWORD
easy,nonn
AUTHOR
R. J. Mathar, Jul 15 2007, Mar 07 2008
STATUS
approved