A309160 Number of nonempty subsets of [n] whose elements have a prime average.

0, 1, 4, 6, 11, 15, 22, 40, 72, 118, 199, 355, 604, 920, 1306, 1906, 3281, 6985, 16446, 38034, 82490, 168076, 325935, 604213, 1068941, 1815745, 3038319, 5246725, 9796132, 19966752, 42918987, 92984247, 197027405, 402932711, 792381923, 1499918753, 2746078246

Offset

1,3

Links

Alois P. Heinz, Table of n, a(n) for n = 1..200

Formula

a(n) < A051293(n).

Example

a(3) = 4 because 4 of the subsets of [3], namely {2}, {3}, {1,3}, {1,2,3}, have prime averages.

Maple

b:= proc(n, s, c) option remember; `if`(n=0,
      `if`(c>0 and denom(s)=1 and isprime(s), 1, 0),
       b(n-1, s, c)+b(n-1, (s*c+n)/(c+1), c+1))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=1..40);  # Alois P. Heinz, Jul 15 2019

Mathematica

a[n_]:=Length[Select[Subsets[Range[n]], PrimeQ[Mean[#]]&]]; a/@Range[25]

Prog

(Python)
from sympy import isprime
from functools import lru_cache
def cond(s, c): q, r = divmod(s, c); return r == 0 and isprime(q)
@lru_cache(maxsize=None)
def b(n, s, c):
    if n == 0: return int (c > 0 and cond(s, c))
    return b(n-1, s, c) + b(n-1, s+n, c+1)
a = lambda n: b(n, 0, 0)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Sep 25 2022

Crossrefs

Cf. A051293, A114976, A127542.

Sequence in context: A036831 A084263 A232807 * A266795 A355759 A060180

Adjacent sequences: A309157 A309158 A309159 * A309161 A309162 A309163

Keyword

nonn

Author

Ivan N. Ianakiev, Jul 15 2019

Extensions

a(26)-a(37) from Alois P. Heinz, Jul 15 2019

Status

approved