The OEIS is supported by the many generous donors to the OEIS Foundation.
Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #9 Nov 21 2024 08:37:36
%S 1,1,2,3,6,11,22,42,81,156,312,613,1226,2430,4818,9555,19110,38064,
%T 76128,151944,303275,605324,1210648,2418866,4832914,9656273,19293436,
%U 38548808,77097616,154119104,308238208,616324472,1232345669,2464086014,4926961380,9851503894
%N a(1) = 1, a(n) = Sum_{k=1..pi(n)} a(n-k) for n > 1, where pi(n) is the number of primes less than or equal to n.
%C Conjecture: lim_{n->infinity} a(n)/2^n > 0; appears to be about 0.1432645404.
%F a(1) = a(2) = 1, for p an odd prime, a(p) = 2a(p-1), otherwise a(n) = 2a(n-1) - a(n - pi(n) - 1).
%p a:= proc(n) option remember; `if`(n=1, 1,
%p add(a(n-k), k=1..numtheory[pi](n)))
%p end:
%p seq(a(n), n=1..36); # _Alois P. Heinz_, Nov 21 2024
%t a[1]=a[2]=1; a[n_]:=If[PrimeQ[n]&&OddQ[n],2a[n-1],2a[n-1]-a[n-PrimePi[n]-1]];Table[a[n],{n,34}] (* _James C. McMahon_, Nov 21 2024 *)
%Y Cf: A000720, A000045, A001590.
%K nonn
%O 1,3
%A _Franklin T. Adams-Watters_, Oct 11 2006