login
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
OFFSET
1,4
COMMENTS
This is a variant of A327969 that seems to be less in need of an escape clause. Note that enough prime shifts with A003961 will eventually transform every term of A100716 (which is a subsequence of A099309) to a term of A048103, and that A051903(A003961(n)) = A051903(n). See also the array A344027.
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.
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.
a(n) < A099307(n), unless A099307(n) = 0. [I.e., for all n in A099308]
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.
From n = 8, we can reach 1 with seven steps, as A003415(8) = 12, A003961(12) = 45, A003415(45) = 39, A003961(39) = 85, A003415(85) = 22, A003415(22) = 13, A003415(13) = 1, and because there are no shorter paths we have a(8) = 7.
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));
KEYWORD
nonn
AUTHOR
Antti Karttunen, Apr 23 2022
STATUS
approved