A276770 a(n) is the number of runs of an algorithm. Set b_0 = n, if prime, stop; else, set c_0 = largest divisor of n (!=n); set b_1 = c_0 + b_0/c_0. Run with b_1.

0, 1, 0, 2, 2, 1, 0, 3, 0, 3, 3, 2, 0, 1, 0, 4, 2, 1, 0, 4, 2, 4, 4, 3, 0, 1, 0, 2, 4, 1, 4, 5, 0, 3, 3, 2, 0, 1, 0, 5, 2, 3, 0, 5, 4, 5, 5, 4, 0, 1, 3, 2, 2, 1, 0, 3, 0, 5, 5, 2, 2, 5, 0, 6, 5, 1, 0, 4, 0, 4, 4, 3, 2, 1, 0, 2, 2, 1, 0, 6, 2, 3, 3, 4, 0, 1, 5, 6, 2, 5, 5, 6, 0, 6, 6, 5, 0, 1, 0, 2, 4

Offset

5,4

Comments

a(4) -> infinity. For any other n >= 2, a(n) is finite, however cases n = 2,3 are trivial, so the offset is 5.

For large n: Sum_{k=5..n} a(k) ~ n*log(n)/2 (conjectured).

Links

Yuriy Sibirmovsky, Table of n, a(n) for n = 5..1000

Yuriy Sibirmovsky, Plot of sum_{k=5..n} a(k) for n = 5..20000

Example

For n=14: b_0 = 14, not prime. c_0 = 7. b_1 = 7 + 2 = 9. 9 is not prime.
In short: 14 -> {7,2} -> 9 -> {3,3} -> 6 -> {3,2} -> 5. Number of runs a(14) = 3.

Mathematica

Nm=100;
a=Table[0, {n, 1, Nm}];
Do[b0=n;
j=0;
While[PrimeQ[b0]==False, c=Reverse[Divisors[b0]];
b1=c[[2]]+b0/c[[2]];
b0=b1; j++];
a[[n]]=j, {n, 5, Nm}];
Table[a[[k]], {k, 5, Nm}]

Prog

(PARI) stop(n) = (n<=1) || isprime(n);
a(n) = {b = n; nb = 0; while (! stop(b), d = divisors(b); c = d[#d-1]; b = c + b/c; nb++; ); nb; } \\ Michel Marcus, Sep 19 2016

Crossrefs

Cf. A000040, A276771.

Sequence in context: A190182 A371788 A068926 * A258291 A146527 A352556

Adjacent sequences: A276767 A276768 A276769 * A276771 A276772 A276773

Keyword

nonn

Author

Yuriy Sibirmovsky, Sep 17 2016

Status

approved