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

0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 2, 0, 1, 0, 2, 2, 2, 0, 2, 1, 1, 2, 3, 0, 1, 0, 2, 2, 2, 1, 3, 0, 1, 2, 2, 0, 1, 0, 3, 3, 3, 0, 3, 1, 1, 2, 3, 0, 2, 2, 2, 3, 3, 0, 4, 0, 1, 2, 2, 2, 1, 0, 3, 3, 3, 0, 3, 0, 2, 3, 4, 2, 1, 0, 2, 3, 3, 0, 3, 3, 1, 2, 2, 0, 1, 2, 4, 4, 4, 2, 4, 0, 1, 2, 4

Offset

1,12

Comments

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

Links

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

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

Example

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

Mathematica

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

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, A276770.

Sequence in context: A352523 A116948 A101660 * A062984 A105243 A140081

Adjacent sequences: A276768 A276769 A276770 * A276772 A276773 A276774

Keyword

nonn

Author

Yuriy Sibirmovsky, Sep 17 2016

Status

approved