A089822 -id:A089822 - cp's OEIS frontend

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

Reinhard Zumkeller, Nov 12 2003

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

			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.

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

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

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

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

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

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

A089818 T(n,k) = number of subsets of {1,..., n} containing exactly k primes, triangle read by rows, 0<=k

Original entry on oeis.org

2, 2, 2, 2, 4, 2, 4, 8, 4, 0, 4, 12, 12, 4, 0, 8, 24, 24, 8, 0, 0, 8, 32, 48, 32, 8, 0, 0, 16, 64, 96, 64, 16, 0, 0, 0, 32, 128, 192, 128, 32, 0, 0, 0, 0, 64, 256, 384, 256, 64, 0, 0, 0, 0, 0, 64, 320, 640, 640, 320, 64, 0, 0, 0, 0, 0, 128, 640, 1280, 1280, 640, 128, 0, 0, 0, 0, 0

Offset: 1

Reinhard Zumkeller, Nov 12 2003

T(n,k) = T(n, A000720(n)-k) for 0<=k<=A000720(n);
T(n,k) = 0 iff k > A000720(n);
A089819(n) = T(n,0); A089821(n) = T(n,1) for n>1; A089822(n) = T(n,2) for n>2;
A089820(n) = Sum(T(n,k): 1<=k<=A000720(n));
T(n,k) = A007318(A000720(n),k) * A000079(n-A000720(n)).

Cf. A000040.

T[n_, k_] := Binomial[PrimePi[n], k] 2^(n - PrimePi[n]);
Table[T[n, k], {n, 1, 12}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Nov 04 2020 *)

T(n, k) = binomial(pi(n), k)*2^(n-pi(n)), with pi = A000720.

A330592 a(n) is the number of subsets of {1,2,...,n} that contain exactly two odd numbers.

Original entry on oeis.org

0, 0, 2, 4, 12, 24, 48, 96, 160, 320, 480, 960, 1344, 2688, 3584, 7168, 9216, 18432, 23040, 46080, 56320, 112640, 135168, 270336, 319488, 638976, 745472, 1490944, 1720320, 3440640, 3932160, 7864320, 8912896, 17825792, 20054016, 40108032, 44826624, 89653248

Offset: 1

Enrique Navarrete, Dec 18 2019

2*a(n-1) for n>1 is the number of subsets of {1,2,...,n} that contain exactly two even numbers. For example, for n=5, 2*a(4)=8 and the 8 subsets are {2,4}, {1,2,4}, {2,3,4}, {2,4,5}, {1,2,3,4}, {1,2,4,5}, {2,3,4,5}, {1,2,3,4,5}. - Enrique Navarrete, Dec 20 2019

			For n=5, a(5)=12 and the 12 subsets are {1,3}, {1,5}, {3,5}, {1,2,3}, {1,2,5}, {1,3,4}, {1,4,5}, {2,3,5}, {3,4,5}, {1,2,3,4}, {1,2,4,5}, {2,3,4,5}.

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (0,6,0,-12,0,8).

Cf. A089822 (with exactly two primes).

[IsEven(n) select Binomial(n div 2,2)*2^(n div 2) else Binomial((n+1) div 2,2)*2^((n-1) div 2):n in [1..40]]; // Marius A. Burtea, Dec 19 2019

a[n_] := If[OddQ[n], Binomial[(n + 1)/2, 2]*2^((n - 1)/2), Binomial[n/2, 2]*2^(n/2)]; Array[a, 38] (* Amiram Eldar, Mar 24 2022 *)

concat([0,0], Vec(2*x^3*(1 + 2*x) / (1 - 2*x^2)^3 + O(x^40))) \\ Colin Barker, Dec 20 2019

a(n) = binomial((n+1)/2,2) * 2^((n-1)/2), n odd;
a(n) = binomial(n/2,2) * 2^(n/2), n even.
G.f.: 2*(2*x+1)*x^3/(1-2*x^2)^3.
a(n) = 6*a(n-2) - 12*a(n-4) + 8*a(n-6) for n>6. - Colin Barker, Dec 20 2019
From Amiram Eldar, Mar 24 2022: (Start)
Sum_{n>=3} 1/a(n) = 3*(1-log(2)).
Sum_{n>=3} (-1)^(n+1)/a(n) = 1-log(2). (End)

A089820 Number of subsets of {1,..,n} containing at least one prime.

Original entry on oeis.org

0, 2, 6, 12, 28, 56, 120, 240, 480, 960, 1984, 3968, 8064, 16128, 32256, 64512, 130048, 260096, 522240, 1044480, 2088960, 4177920, 8372224, 16744448, 33488896, 66977792, 133955584, 267911168, 536346624, 1072693248, 2146435072, 4292870144, 8585740288

Offset: 1

Reinhard Zumkeller, Nov 12 2003

a(n) = Sum(A089818(n,k): 1<=k<=A000720(n)) = A000079(n)-A089819(n) = A089819(n)*A000225(A000720(n)).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Cf. A089822.

Cf. A000079, A000225, A000720, A089818, A089819.

[2^n-2^(n-#PrimesUpTo(n)) : n in [1..30]]; // Wesley Ivan Hurt, Sep 19 2014

with(numtheory): A089820:=n->2^n - 2^(n-pi(n)): seq(A089820(n), n=1..30); # Wesley Ivan Hurt, Sep 19 2014

Table[2^n - 2^(n - PrimePi[n]), {n, 30}] (* Wesley Ivan Hurt, Sep 19 2014 *)

a(n) = 2^n - 2^(n-pi(n)) = the total number of subsets minus the number of subsets of the nonprime elements of {1,..,n}, where pi = A000720. - Greg Martin, May 13 2004

More terms from Wesley Ivan Hurt, Sep 19 2014

A089821 Number of subsets of {1,.., n} containing exactly one prime.

Original entry on oeis.org

0, 2, 4, 8, 12, 24, 32, 64, 128, 256, 320, 640, 768, 1536, 3072, 6144, 7168, 14336, 16384, 32768, 65536, 131072, 147456, 294912, 589824, 1179648, 2359296, 4718592, 5242880, 10485760, 11534336, 23068672, 46137344, 92274688, 184549376, 369098752, 402653184

Offset: 1

Reinhard Zumkeller, Nov 12 2003

nonn

			a(5)=12 subsets of {1,2,3,4,5} contain exactly one prime: {2}, {3}, {5}, {1,2}, {1,3}, {1,5}, {2,4}, {3,4}, {4,5}, {1,2,4}, {1,3,4} and {1,4,5}.

Cf. A000720, A089818, A089819, A089822.

b:= proc(n, c) option remember; `if`(n=0, `if`(c=0, 1, 0),
     `if`(c<0, 0, b(n-1, c)+b(n-1, c-`if`(isprime(n), 1, 0))))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..42);  # Alois P. Heinz, Dec 19 2019

b[n_, c_] := b[n, c] = If[n == 0, If[c == 0, 1, 0], If[c < 0, 0, b[n - 1, c] + b[n - 1, c - If[PrimeQ[n], 1, 0]]]];
a[n_] := b[n, 1];
Array[a, 42] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

a(n) = primepi(n) * 2^(n-primepi(n)); \\ Michel Marcus, Nov 07 2020

a(n) = A000720(n)*A089819(n);
for n>1: a(n) = A089818(n,1).
a(n) = pi(n) * 2^(n-pi(n)), with pi = A000720.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A089818 T(n,k) = number of subsets of {1,..., n} containing exactly k primes, triangle read by rows, 0<=k

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A330592 a(n) is the number of subsets of {1,2,...,n} that contain exactly two odd numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A089820 Number of subsets of {1,..,n} containing at least one prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A089821 Number of subsets of {1,.., n} containing exactly one prime.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula