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

1, 1, 2, 3, 6, 11, 22, 42, 81, 156, 312, 613, 1226, 2430, 4818, 9555, 19110, 38064, 76128, 151944, 303275, 605324, 1210648, 2418866, 4832914, 9656273, 19293436, 38548808, 77097616, 154119104, 308238208, 616324472, 1232345669, 2464086014, 4926961380, 9851503894

Offset

1,3

Comments

Conjecture: lim_{n->infinity} a(n)/2^n > 0; appears to be about 0.1432645404.

Links

Table of n, a(n) for n=1..36.

Formula

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

Maple

a:= proc(n) option remember; `if`(n=1, 1,
      add(a(n-k), k=1..numtheory[pi](n)))
    end:
seq(a(n), n=1..36);  # Alois P. Heinz, Nov 21 2024

Mathematica

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

Crossrefs

Cf: A000720, A000045, A001590.

Sequence in context: A018613 A036589 A251656 * A372989 A238351 A043328

Adjacent sequences: A123338 A123339 A123340 * A123342 A123343 A123344

Keyword

nonn

Author

Franklin T. Adams-Watters, Oct 11 2006

Status

approved