

A327969


The length of a shortest path from n to zero when using the transitions x > A003415(x) and x > A276086(x), or 1 if no zero can ever be reached from n.


15



0, 1, 2, 2, 5, 2, 3, 2, 6, 4, 3, 2, 5, 2, 5, 6, 6, 2, 5, 2, 7, 4, 3, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The terms of this sequence are currently known only up to n=23, with the value of a(24) still being uncertain. For the tentative values of the later terms, see sequence A328324 which gives upper bounds for these terms, many of which are very likely also exact values for them.
As A051903(A003415(n)) >= A051903(n)1, it means that it takes always at least A051903(n) steps to a prime if iterating solely with A003415.
Some known values and upper bounds from n=24 onward:
a(24) <= 11.
a(25) = 4.
a(26) = 7.
a(27) <= 22.
a(39) = 4.
a(40) = 5.
a(42) = 3.
a(44) <= 10.
a(45) = 5.
a(46) = 5.
a(48) = 9.
a(49) = 6.
a(50) = 6.
a(55) = 7.
a(74) = 5.
a(77) = 6.
a(80) <= 18.
a(111) = 6.
a(112) = 8.
a(125) <= 9.
a(240) = 7.
a(625) <= 10.
a(875) = 8.


LINKS

Table of n, a(n) for n=0..23.


FORMULA

a(0) = 0, a(p^p) = 1 + a(A276086(p^p)) for primes p, and for other numbers, a(n) = 1+min(a(A003415(n)), a(A276086(n))).
a(p) = 2 for all primes p.
For all n, a(n) <= A328324(n).
Let A stand the transition x > A003415(x), and B stand for x > A276086(x). The following sequences give some constant upper limits, because it is guaranteed that the combination given in brackets (the leftmost A or B is applied first) will always lead to a prime:
For all n, a(A157037(n)) = 3. [A]
For n > 1, a(A002110(n)) = 3. [B]
For all n, a(A192192(n)) <= 4. [AA]
For all n, a(A327978(n)) = 4. [AB]
For all n, a(A328233(n)) <= 4. [BA]
For all n, a(A143293(n)) <= 4. [BB]
For all n, a(A328239(n)) <= 5. [AAA]
For all n, a(A328240(n)) <= 5. [BAA]
For all n, a(A328243(n)) <= 5. [ABB]
For all n, a(A328313(n)) <= 5. [BBB]
For all n, a(A328249(n)) <= 6. [BAAA]
For all k in A046099, a(k) >= 4, and if A328114(k) > 1, then certainly a(k) > 4.


EXAMPLE

Let A> stand for an application of A003415 and B> for an application of A276086, then, we have for example:
a(8) = 6 as we have 8 A> 12 B> 25 A> 10 A> 7 A> 1 A> 0, six transitions in total (and there are no shorter paths).
a(15) = 6 as we have 15 B> 150 A> 185 A> 42 A> 41 A> 1 A> 0, six transitions in total (and there are no shorter paths).
a(20) = 7, as 20 B> 375 A> 350 A> 365 A> 78 A> 71 A> 1 A> 0, and there are no shorter paths.
For n=112, we know that a(112) cannot be larger than eight, as A328099^(8)(112) = 0, so we have a path of length 8 as 112 A> 240 B> 77 A> 18 A> 21 A> 10 A> 7 A> 1 A> 0. Checking all 32 combinations of the paths of lengths of 5 starting from 112 shows that none of them or their prefixes ends with a prime, thus there cannot be any shorter path, and indeed a(112) = 8.
a(24) <= 11 as A328099^(11)(24) = 0, i.e., we have 24 A> 44 A> 48 A> 112 A> 240 B> 77 A> 18 A> 21 A> 10 A> 7 A> 1 A> 0. On the other hand, 24 B> 625 B> 17794411250 A> 41620434625 A> 58507928150 A> 86090357185 A> 54113940517 A> 19982203325 A> 12038411230 A> 8426887871 A> 1 A> 0, thus offering another path of length 11.


PROG

(PARI)
A003415(n) = if(n<=1, 0, my(f=factor(n)); n*sum(i=1, #f~, f[i, 2]/f[i, 1]));
A276086(n) = { my(m=1, p=2); while(n, m *= (p^(n%p)); n = n\p; p = nextprime(1+p)); (m); };
A327969(n, searchlim=0) = if(!n, n, my(xs=Set([n]), newxs, a, b, u); for(k=1, oo, print("n=", n, " k=", k, " xs=", xs); newxs=Set([]); for(i=1, #xs, u = xs[i]; a = A003415(u); if(0==a, return(k)); if(isprime(a), return(k+2)); b = A276086(u); if(isprime(b), return(k+1+(u>2))); newxs = setunion([a], newxs); if(!searchlim  (b<=searchlim), newxs = setunion([b], newxs))); xs = newxs));


CROSSREFS

Cf. A003415, A046099, A051674, A051903, A068346, A276086, A276087, A327859, A327860, A328099, A328112, A328114, A328116, A328307.
Cf. A328324 (a sequence giving upper bounds, computed with restricted search space).
Sequences for whose terms k, value a(k) has a guaranteed constant upper bound: A000040, A002110, A143293, A157037, A192192, A327978, A328232, A328233, A328239, A328240, A328243, A328249, A328313.
Sequences for whose terms k, it is guaranteed that a(k) has finite value > 0, even if not bound by a constant: A099308, A328116.
Cf. also A256750, A327966.
Sequence in context: A309727 A195719 A108053 * A328324 A133501 A254176
Adjacent sequences: A327966 A327967 A327968 * A327970 A327971 A327972


KEYWORD

nonn,hard,more


AUTHOR

Antti Karttunen, Oct 07 2019


STATUS

approved



