A072491 Define f(1) = 0. For n>=2, let f(n) = n - p where p is the largest prime <= n. a(n) = number of iterations of f to reach 0, starting from n.

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

Offset: 0

Author

Amarnath Murthy, Jul 14 2002

Keywords

• nonn
• easy

Comments

a(p)=1, a(p+1)=2 and a(p+4)=3 if p is an odd prime but p+2 and p+4 are composite.

Number of noncomposites (A008578) needed to sum to n using the greedy algorithm. - Antti Karttunen, Aug 09 2015

Examples

			a(27)=3 as f(27)=27-23=4, f(4)=4-3=1 and f(1)=0.
		

References

• S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159-167.

Links

• Antti Karttunen, Table of n, a(n) for n = 0..10007

Crossrefs

Cf. A008578, A072492. A066352(n) is the smallest k such that a(k)=n.

Not the same as A051034: a(122) = 3, but A051034(122) = 2.

Programs

Mathematica

f[1]=0; f[n_] := n-Prime[PrimePi[n]]; a[n_] := Module[{k, x}, For[k=0; x=n, x>0, k++; x=f[x], Null]; k]

PARI

a(n)=if(n<4,n>0,1+a(n-precprime(n))) \\ Charles R Greathouse IV, Feb 04 2013

Formula

On Cramér's conjecture, a(n) = O(log* n). - Charles R Greathouse IV, Feb 04 2013

Extensions

Edited by Dean Hickerson, Nov 26 2002

a(0) = 0 prepended by Antti Karttunen, Aug 09 2015