A089819 Number of subsets of {1,2,...,n} containing no primes.

2, 2, 2, 4, 4, 8, 8, 16, 32, 64, 64, 128, 128, 256, 512, 1024, 1024, 2048, 2048, 4096, 8192, 16384, 16384, 32768, 65536, 131072, 262144, 524288, 524288, 1048576, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 33554432, 67108864

Offset: 1

Author

Reinhard Zumkeller, Nov 12 2003

Keywords

• nonn
• easy

Comments

Equivalently, the number of subsets of {1,2,...,n} such that the product of the elements is square, where the empty set is defined to have a product of 1. - Peter Kagey, Nov 18 2017

Examples

			a(6)=8 subsets of {1,2,3,4,5,6} contain no prime: {1,4,6}, {4,6}, {1,6}, {1,4}, {6}, {4}, {1} and the empty set.
a(7) = 8 as 2^(7 - PrimePi(7)) = 2^(7-4) = 8.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..3853
• Index to divisibility sequences

Crossrefs

Cf. A000079, A000720, A010051, A089818, A089820, A089821, A089822.

Programs

Maple

A089819:=n->2^(n-numtheory[pi](n)): seq(A089819(n), n=1..50); # Wesley Ivan Hurt, Nov 21 2017

Mathematica

Table[2^(n - PrimePi[n]), {n, 50}] (* Wesley Ivan Hurt, Nov 18 2017 *)

PARI

a(n)=2^(n-primepi(n)) \\ Charles R Greathouse IV, Apr 09 2012

Formula

a(n) = 2^(n-PrimePi(n)), with PrimePi = A000720.

a(n) = Product_{k=1..n} (2-A010051(k)) = A089818(n,0) = A000079(n) - A089820(n).

a(n) = 2^(1-A010051(n))*a(n-1). - Robert Israel, Nov 22 2017