login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 15:29 EDT 2020. Contains 337383 sequences. (Running on oeis4.)