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

%I #28 Dec 26 2017 18:08:30

%S 2,2,2,4,4,8,8,16,32,64,64,128,128,256,512,1024,1024,2048,2048,4096,

%T 8192,16384,16384,32768,65536,131072,262144,524288,524288,1048576,

%U 1048576,2097152,4194304,8388608,16777216,33554432,33554432,67108864

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

%C 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

%H Robert Israel, <a href="/A089819/b089819.txt">Table of n, a(n) for n = 1..3853</a>

%H <a href="/index/Di#divseq">Index to divisibility sequences</a>

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

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

%F a(n) = 2^(1-A010051(n))*a(n-1). - _Robert Israel_, Nov 22 2017

%e 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.

%e a(7) = 8 as 2^(7 - PrimePi(7)) = 2^(7-4) = 8.

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

%t Table[2^(n - PrimePi[n]), {n, 50}] (* _Wesley Ivan Hurt_, Nov 18 2017 *)

%o (PARI) a(n)=2^(n-primepi(n)) \\ _Charles R Greathouse IV_, Apr 09 2012

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

%K nonn,easy

%O 1,1

%A _Reinhard Zumkeller_, Nov 12 2003