cp's OEIS Frontend

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.

%I A072491 #21 Aug 09 2015 14:06:15
%S A072491 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,
%T A072491 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,
%U A072491 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
%N 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.
%C A072491 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.
%C A072491 Number of noncomposites (A008578) needed to sum to n using the greedy algorithm. - _Antti Karttunen_, Aug 09 2015
%D A072491 S. S. Pillai, "An arithmetical function concerning primes", Annamalai University Journal (1930), pp. 159-167.
%H A072491 Antti Karttunen, <a href="/A072491/b072491.txt">Table of n, a(n) for n = 0..10007</a>
%F A072491 On Cramér's conjecture, a(n) = O(log* n). - _Charles R Greathouse IV_, Feb 04 2013
%e A072491 a(27)=3 as f(27)=27-23=4, f(4)=4-3=1 and f(1)=0.
%t A072491 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]
%o A072491 (PARI) a(n)=if(n<4,n>0,1+a(n-precprime(n))) \\ _Charles R Greathouse IV_, Feb 04 2013
%Y A072491 Cf. A008578, A072492. A066352(n) is the smallest k such that a(k)=n.
%Y A072491 Not the same as A051034: a(122) = 3, but A051034(122) = 2.
%K A072491 nonn,easy
%O A072491 0,5
%A A072491 _Amarnath Murthy_, Jul 14 2002
%E A072491 Edited by _Dean Hickerson_, Nov 26 2002
%E A072491 a(0) = 0 prepended by _Antti Karttunen_, Aug 09 2015