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

Author

Yuriy Sibirmovsky, Sep 17 2016

Keywords

• nonn

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).

Examples

			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.
		

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

Crossrefs

Cf. A000040, A276771.

Programs

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}]

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