cp's OEIS Frontend

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.

%I A353515 #26 Apr 23 2022 18:13:22
%S A353515 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,
%T A353515 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,
%U A353515 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
%N 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.
%C A353515 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.
%C A353515 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.
%H A353515 Antti Karttunen, <a href="/A353515/b353515.txt">Table of n, a(n) for n = 1..16383</a>
%H A353515 <a href="/index/Pri#prime_indices">Index entries for sequences computed from indices in prime factorization</a>
%F A353515 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))).
%F A353515 a(p) = 1 for all primes p.
%F A353515 a(n) < A099307(n), unless A099307(n) = 0. [I.e., for all n in A099308]
%e A353515 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.
%e A353515 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.
%e A353515 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.
%e A353515 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.
%o A353515 (PARI)
%o A353515 A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
%o A353515 A003961(n) = { my(f = factor(n)); for(i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); }; \\ From A003961
%o A353515 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));
%Y A353515 Cf. A003415, A003961, A048103, A051903, A099307, A099308, A099309, A100716, A349905.
%Y A353515 Cf. also A327969 and A343221, A344027, A353484.
%K A353515 nonn
%O A353515 1,4
%A A353515 _Antti Karttunen_, Apr 23 2022