|
|
A353515
|
|
The length of the shortest path from n to 1 when using the transitions x -> A003415(x) and x -> A003961(x), or -1 if no 1 can ever be reached from n.
|
|
2
|
|
|
0, 1, 1, 4, 1, 2, 1, 7, 3, 2, 1, 6, 1, 4, 7, 8, 1, 4, 1, 6, 3, 2, 1, 7, 3, 6, 7, 8, 1, 2, 1, 10, 5, 2, 6, 5, 1, 4, 4, 6, 1, 2, 1, 6, 5, 4, 1, 9, 4, 5, 5, 8, 1, 6, 8, 8, 3, 2, 1, 4, 1, 6, 5, 10, 5, 2, 1, 5, 4, 2, 1, 8, 1, 5, 6, 6, 5, 2, 1, 9, 7, 2, 1, 4, 3, 5, 7, 8, 1, 5, 7, 7, 3, 5, 4, 9, 1, 6, 7, 6, 1, 3, 1, 7, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Records 0, 1, 4, 7, 8, 10, 12, 13, 14, 15, 16, 19, ... occur at 1, 2, 4, 8, 16, 32, 128, 256, 768, 1024, 2048, 4096, ..., etc.
|
|
LINKS
|
|
|
FORMULA
|
a(1) = 0, a(p^p) = 1 + a(A003961(p^p)) for primes p, and for other numbers, a(n) = 1 + min(a(A003415(n)), a(A003961(n))).
a(p) = 1 for all primes p.
|
|
EXAMPLE
|
From n = 4, we can reach 1 with just four steps as A003961(4) = 9, A003415(9) = 6, A003415(6) = 5 and A003415(5) = 1, and because there are no shorter paths we have a(4) = 4.
For n = 15, as A003415(15) = 8, we know that a(15) is at most a(8)+1, i.e., 8. But we can do better, as A003961(15) = 35, A003961(35) = 77, A003415(77) = 18, A003415(18) = 21, A003415(21) = 10, A003415(10) = 7, A003415(7) = 1, and because there are no shorter paths we have a(15) = 7.
From n = 49, we can reach 1 in four steps, as A003961(49) = 121, A003415(121) = 22, A003415(22) = 13, A003415(13) = 1. Note that this is less than A099307(49)-1, as it would take 5 steps to reach 1 if using the arithmetic derivative only, 49 -> 14 -> 9 -> 6 -> 5 -> 1.
|
|
PROG
|
(PARI)
A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); }; \\ From A003961
A353515(n) = if(1==n, 0, my(xs=Set([n]), newxs, a, b, u); for(k=1, oo, newxs=Set([]); for(i=1, #xs, u = xs[i]; a = A003415(u); if(1==a, return(k)); if(isprime(a), return(k+1)); b = A003961(u); newxs = setunion([a], newxs); newxs = setunion([b], newxs)); xs = newxs));
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|