A121497 Binomial transform of the characteristic function of the prime numbers (A010051).

0, 0, 1, 4, 10, 21, 41, 78, 148, 282, 537, 1013, 1882, 3446, 6267, 11468, 21416, 41209, 81771, 166042, 340994, 700570, 1429375, 2886777, 5771828, 11453105, 22638215, 44742141, 88681674, 176545766, 352992931, 707922077, 1421120880, 2849433326

Offset: 0

Author

T. D. Noe, Aug 03 2006

Keywords

• nonn

Comments

This is the binomial transform of the sequence {0,0,1,1,0,1,0,1,...}. Sequence A052467, the binomial transform of the sequence {0,1,1,0,1,0,1,...} is very similar. In fact, the first differences of this sequence yields A052467.

The number of pernicious numbers (A052294) less than 2^n. Although the graph looks almost like 2^n, the graph of a(n)/2^n has quite a bit of variation. - T. D. Noe, Mar 14 2009

a(n)/2^n is the probability that a series of Bernoulli trials with probability of success equal to 1/2 will result in a prime number of successes. Cf. A178851. - Eric M. Schmidt, Jul 13 2012

a(n) equals the number of subsets of [n] whose cardinalities are prime. - Ivan N. Ianakiev, Jul 14 2019

Upper and lower bounds are provided by Kim and Sinha (see links). - Jeffrey Shallit, Nov 14 2024

Links

• T. D. Noe and Charles R Greathouse IV, Table of n, a(n) for n = 0..3324 (terms up to 1000 from Noe)
• Sungjin Kim and Nilotpal Kanti Sinha, Binomial probability of prime number of successes, INTEGERS 20 (2020), #A99.
• Vaclav Kotesovec, Plot of a(n) / (2^n/log(n/2)) for n = 2..10000

Crossrefs

Cf. A000720, A010051, A052294, A052467, A178851

Programs

Maple

Primes:= select(isprime, [2,seq(i,i=3..100,2)]):
G:= add((z/(1-z))^p/(1-z),p=Primes):
S:= series(G,z,101):
seq(coeff(S,z,i),i=0..100); # Robert Israel, Sep 27 2018

Mathematica

Table[Sum[Binomial[n,Prime[i]], {i,PrimePi[n]}], {n,40}]

PARI

a(n)=my(s);forprime(p=2,n,s+=binomial(n,p));s \\ Charles R Greathouse IV, Mar 22 2013

Formula

a(n) = Sum_{i=1..pi(n)} binomial(n,prime(i)), where pi(n) is A000720(n), the number of primes <= n.

E.g.f.: exp(x) * (x^2/2! + x^3/3! + x^5/5! + ...) - Eric M. Schmidt, Jul 14 2012

G.f.: Sum_{p prime} x^p/(1-x)^(p+1). - Robert Israel, Sep 27 2018

Extensions

a(0) inserted by Franklin T. Adams-Watters, Jul 13 2012