A126024
Number of subsets of {1,2,3,...,n} whose sum is a square integer (including the empty subset).
Original entry on oeis.org
1, 2, 2, 3, 5, 7, 12, 20, 34, 60, 106, 190, 346, 639, 1183, 2204, 4129, 7758, 14642, 27728, 52648, 100236, 191294, 365827, 700975, 1345561, 2587057, 4981567, 9605777, 18546389, 35851756, 69382558, 134414736, 260658770, 505941852, 982896850
Offset: 0
The subsets of {1,2,3,4,5} that sum to a square are {}, {1}, {1,3}, {4}, {2,3,4}, {1,3,5} and {4,5}. Thus a(5)=7.
-
import Data.List (subsequences)
a126024 = length . filter ((== 1) . a010052 . sum) .
subsequences . enumFromTo 1
-- Reinhard Zumkeller, Feb 22 2012, Oct 27 2010
-
b:= proc(n, i) option remember; (m->
`if`(n=0 or n=m, 1, `if`(n<0 or n>m, 0, b(n, i-1)+
`if`(i>n, 0, b(n-i, i-1)))))(i*(i+1)/2)
end:
a:= proc(n) option remember; `if`(n<0, 0, a(n-1)+
add(b(j^2-n, n-1), j=isqrt(n)..isqrt(n*(n+1)/2)))
end:
seq(a(n), n=0..50); # Alois P. Heinz, Feb 02 2017
-
g[n_] := Block[{p = Product[1 + z^i, {i, n}]},Sum[Boole[IntegerQ[Sqrt[k]]]*Coefficient[p, z, k], {k, 0, n*(n + 1)/2}]];Array[g, 35] (* Ray Chandler, Mar 05 2007 *)
A282516
Number T(n,k) of k-element subsets of [n] having a prime element sum; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
Original entry on oeis.org
0, 0, 0, 0, 1, 1, 0, 2, 2, 0, 0, 2, 4, 1, 0, 0, 3, 5, 2, 2, 0, 0, 3, 7, 6, 4, 2, 0, 0, 4, 9, 10, 11, 7, 1, 0, 0, 4, 11, 18, 21, 13, 7, 2, 0, 0, 4, 14, 26, 34, 31, 20, 7, 3, 0, 0, 4, 18, 37, 53, 59, 51, 32, 11, 2, 0, 0, 5, 21, 47, 82, 110, 117, 85, 35, 12, 2, 0
Offset: 0
Triangle T(n,k) begins:
0;
0, 0;
0, 1, 1;
0, 2, 2, 0;
0, 2, 4, 1, 0;
0, 3, 5, 2, 2, 0;
0, 3, 7, 6, 4, 2, 0;
0, 4, 9, 10, 11, 7, 1, 0;
0, 4, 11, 18, 21, 13, 7, 2, 0;
0, 4, 14, 26, 34, 31, 20, 7, 3, 0;
0, 4, 18, 37, 53, 59, 51, 32, 11, 2, 0;
0, 5, 21, 47, 82, 110, 117, 85, 35, 12, 2, 0;
...
Columns k=0-10 give:
A000004,
A000720,
A071917,
A320678,
A320679,
A320680,
A320681,
A320682,
A320683,
A320684,
A320685.
First lower diagonal gives
A282518.
-
b:= proc(n, s) option remember; expand(`if`(n=0,
`if`(isprime(s), 1, 0), b(n-1, s)+x*b(n-1, s+n)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..16);
-
b[n_, s_] := b[n, s] = Expand[If[n==0, If[PrimeQ[s], 1, 0], b[n-1, s] + x*b[n-1, s+n]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]];
Table[T[n], {n, 0, 16}] // Flatten (* Jean-François Alcover, Mar 21 2017, translated from Maple *)
A309160
Number of nonempty subsets of [n] whose elements have a prime average.
Original entry on oeis.org
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
a(3) = 4 because 4 of the subsets of [3], namely {2}, {3}, {1,3}, {1,2,3}, have prime averages.
-
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
-
a[n_]:=Length[Select[Subsets[Range[n]],PrimeQ[Mean[#]]&]]; a/@Range[25]
-
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
A126111
Number of subsets of {1,2,3,...,n} whose sum is a cube.
Original entry on oeis.org
2, 2, 2, 3, 5, 6, 8, 15, 29, 48, 71, 112, 216, 445, 849, 1459, 2403, 4239, 8343, 17049, 33416, 61192, 107290, 190803, 361136, 722568, 1457638, 2847209, 5322619, 9679593, 17715193, 33626815, 66430582, 133432610, 264832126, 511136916, 960634698, 1786150886
Offset: 1
There are five subsets of {1,2,3,4,5} that sum to a cube: {}, {1},{3,5}, {1,2,5} and {1,3,4}. Thus a(5)=5.
Cf. number of subsets of {1,2,3,...,n} whose sum is a square/prime in
A126024,
A127542.
-
g[n_] := Block[{p = Product[1 + z^i, {i, n}]},Sum[Boole[IntegerQ[k^(1/3)]]*Coefficient[p, z, k], {k, 0, n*(n + 1)/2}]];Array[g, 37] (* Ray Chandler, Mar 07 2007 *)
A181522
Number of subsets of {1,2,...,n} whose sum is semiprime (cf. A001358, A064911).
Original entry on oeis.org
0, 0, 2, 6, 13, 25, 47, 92, 184, 367, 721, 1416, 2769, 5407, 10662, 21135, 41866, 83220, 166617, 334852, 670725, 1334868, 2650263, 5280475, 10567613, 21145411, 42103939, 83382359, 164843079, 326791838, 650995628, 1301718424, 2605360702, 5205671338, 10369588530
Offset: 1
a(4) = #{{1,3}, {4}, {1,2,3}, {2,4}, {2,3,4}, {1,2,3,4}} = 6.
A339507
Number of subsets of {1..n} whose sum is a decimal palindrome.
Original entry on oeis.org
1, 2, 4, 8, 15, 24, 32, 41, 55, 79, 126, 220, 406, 778, 1524, 3057, 6310, 13211, 27500, 56246, 113003, 224220, 442106, 870323, 1715503, 3391092, 6726084, 13382357, 26686192, 53286329, 106469764, 212803832, 425434124, 850676115, 1701169724, 3402169203, 6804150711, 13608072837, 27215890383, 54431527170
Offset: 0
a(5) = 24 subsets: {}, {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {2, 4, 5} and {1, 2, 3, 5}.
-
from itertools import combinations
def a(n):
ans = 0
for r in range(n+1):
for s in combinations(range(1,n+1),r):
strss = str(sum(s))
ans += strss==strss[::-1]
return ans
print([a(n) for n in range(21)]) # Michael S. Branicky, Dec 07 2020
-
from functools import lru_cache
from itertools import combinations
@lru_cache(maxsize=None)
def A339507(n):
pallist = set(i for i in range(1,n*(n+1)//2+1) if str(i) == str(i)[::-1])
return 1 if n == 0 else A339507(n-1) + sum(sum(d)+n in pallist for i in range(n) for d in combinations(range(1,n),i)) # Chai Wah Wu, Dec 08 2020
-
from functools import lru_cache
def cond(s): ss = str(s); return ss == ss[::-1]
@lru_cache(maxsize=None)
def b(n, s):
if n == 0: return int(cond(s))
return b(n-1, s) + b(n-1, s+n)
a = lambda n: b(n, 0)
print([a(n) for n in range(100)]) # Michael S. Branicky, Oct 05 2022
A339485
Number of subsets of the first n primes whose elements have a prime average.
Original entry on oeis.org
1, 2, 3, 6, 9, 12, 17, 30, 51, 88, 149, 264, 439, 746, 1261, 2234, 4211, 7996, 14899, 28048, 54037, 106442, 208625, 398588, 735365, 1331590, 2421573, 4481896, 8504953, 16497150, 32595915, 64614636, 127968263, 252470776, 495388085, 962475122, 1847742473, 3504948056
Offset: 1
a(5) = 9 subsets: {2}, {3}, {5}, {7}, {11}, {3, 7}, {3, 11}, {3, 5, 7} and {3, 7, 11}.
-
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+ithprime(n))/(c+1), c+1))
end:
a:= n-> b(n, 0$2):
seq(a(n), n=1..40); # Alois P. Heinz, Dec 08 2020
-
b[n_, s_, c_] := b[n, s, c] = If[n == 0,
If[c > 0 && Denominator[s] == 1 && PrimeQ[s], 1, 0],
b[n-1, s, c] + b[n-1, (s*c + Prime[n])/(c+1), c+1]];
a[n_] := b[n, 0, 0];
Array[a, 40] (* Jean-François Alcover, Jul 09 2021, after Alois P. Heinz *)
-
from sympy import prime, isprime
from itertools import chain, combinations
def powerset(s): # skip empty set and singletons
return chain.from_iterable(combinations(s, r) for r in range(2,len(s)+1))
def a(n):
out = n # count all singletons
for s in powerset([prime(i) for i in range(1, n+1)]):
ss = sum(s)
if ss%len(s) == 0:
if isprime(ss//len(s)): out += 1
return out
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Dec 06 2020
-
from itertools import combinations
from sympy import prime
def A339485(n):
c, primeset2 = n, set(prime(i) for i in range(1,n))
primeset = primeset2 | {prime(n)}
for l in range(2,n+1):
for d in combinations(primeset,l):
a, b = divmod(sum(d),l)
if b == 0 and a in primeset2:
c += 1
return c # Chai Wah Wu, Dec 07 2020
-
from functools import lru_cache
from sympy import sieve, isprime
@lru_cache(maxsize=None)
def b(n, s, c):
if n == 0: return int(c and s%c == 0 and isprime(s//c))
return b(n-1, s, c) + b(n-1, s+sieve[n], c+1)
a = lambda n: b(n, 0, 0)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Oct 06 2022
A339613
Number of sets of distinct primes whose sum is a prime, the largest element of a set is prime(n).
Original entry on oeis.org
1, 2, 2, 2, 5, 8, 15, 30, 57, 115, 211, 398, 783, 1528, 3002, 5893, 11432, 22247, 43663, 86348, 170472, 335636, 662988, 1312816, 2595986, 5121351, 10096635, 19930303, 39469458, 78311512, 155219706, 307373610, 607613871, 1202463562, 2383024521, 4736192475, 9413441133
Offset: 1
a(6) = 8 sets: {13}, {3, 7, 13}, {5, 11, 13}, {7, 11, 13}, {2, 3, 5, 13}, {2, 3, 11, 13}, {2, 5, 11, 13} and {2, 3, 5, 7, 11, 13}.
-
from sympy import prime, isprime
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, s, c):
if n == 0:
if isprime(s): return 1
return 0
return b(n-1, s, c) + b(n-1, s+prime(n), c+1)
a = lambda n: b(n-1, prime(n), 1)
print([a(n) for n in range(1, 20)]) # Michael S. Branicky, Dec 10 2020
A339556
Number of subsets of the first n primes whose elements have a prime root-mean-square.
Original entry on oeis.org
1, 2, 3, 4, 5, 6, 11, 16, 19, 30, 41, 54, 69, 106, 177, 272, 397, 686, 1299, 2416, 4225, 7196, 11701, 20352, 36305, 70134, 132721, 248722, 473391, 894318, 1674923, 3054022, 5452067, 9626552, 16696543, 29086462, 51830095, 96887612, 192393735, 397875694
Offset: 1
a(7) = 11 subsets: {2}, {3}, {5}, {7}, {11}, {13}, {17}, {7, 17}, {5, 7, 17}, {7, 13, 17} and {5, 7, 11, 17}.
A369392
Number of subsets of {2..n} such that the product of the elements plus 1 is a prime.
Original entry on oeis.org
1, 1, 2, 3, 5, 9, 18, 32, 56, 111, 211, 386, 727, 1374, 2654, 5018, 9346, 17946, 33654, 63754, 120619, 229835, 443058, 834608, 1563645, 2999088, 5843122, 11070802, 21253933, 41347141, 79197559, 153735211, 293761934, 570421574, 1112023166, 2153293449
Offset: 0
a(5) = 9 subsets: {}, {2}, {4}, {2, 3}, {2, 5}, {3, 4}, {2, 3, 5}, {2, 4, 5} and {3, 4, 5}.
Showing 1-10 of 10 results.