A126024 -id:A126024 - cp's OEIS frontend

A281871 Number T(n,k) of k-element subsets of [n] having a square element sum; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 2, 0, 0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 4, 5, 5, 2, 1, 0, 1, 2, 5, 8, 8, 6, 3, 0, 1, 1, 3, 6, 11, 14, 13, 7, 4, 1, 0, 1, 3, 7, 15, 23, 24, 19, 10, 3, 1, 0, 1, 3, 8, 20, 34, 43, 39, 25, 13, 3, 1, 0, 1, 3, 9, 26, 49, 71, 74, 60, 34, 14, 5, 0, 0

Offset: 0

Alois P. Heinz, Jan 31 2017

			T(7,0) = 1: {}.
T(7,1) = 2: {1}, {4}.
T(7,2) = 4: {1,3}, {2,7}, {3,6}, {4,5}.
T(7,3) = 5: {1,2,6}, {1,3,5}, {2,3,4}, {3,6,7}, {4,5,7}.
T(7,4) = 5: {1,2,6,7}, {1,3,5,7}, {1,4,5,6}, {2,3,4,7}, {2,3,5,6}.
T(7,5) = 2: {1,2,3,4,6}, {3,4,5,6,7}.
T(7,6) = 1: {1,2,4,5,6,7}.
T(7,7) = 0.
T(8,8) = 1: {1,2,3,4,5,6,7,8}.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 1, 0;
  1, 1, 1,  0;
  1, 2, 1,  1,  0;
  1, 2, 2,  2,  0,  0;
  1, 2, 3,  3,  2,  1,  0;
  1, 2, 4,  5,  5,  2,  1,  0;
  1, 2, 5,  8,  8,  6,  3,  0,  1;
  1, 3, 6, 11, 14, 13,  7,  4,  1,  0;
  1, 3, 7, 15, 23, 24, 19, 10,  3,  1, 0;
  1, 3, 8, 20, 34, 43, 39, 25, 13,  3, 1, 0;
  1, 3, 9, 26, 49, 71, 74, 60, 34, 14, 5, 0, 0;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Columns k=0-10 give: A000012, A000196, A176615, A281706, A281864, A281865, A281866, A281867, A281868, A281869, A281870.
Main diagonal is characteristic function of A001108.
Diagonals T(n+k,n) for k=2-10 give: A281965, A281966, A281967, A281968, A281969, A281970, A281971, A281972, A281973.
Row sums give A126024.
T(2n,n) gives A281872.
Cf. A000217, A000290, A007318, A214857, A214858, A278339, A281994, A284249, A377572.

b:= proc(n, s) option remember; expand(`if`(n=0,
      `if`(issqr(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[IntegerQ @ Sqrt[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, 10}] // Flatten (* Jean-François Alcover, Jun 03 2018, from Maple *)

T(n,n) = 1 for n in { A001108 }, T(n,n) = 0 otherwise.
T(n,n-1) = 1 for n in { A214857 }, T(n,n-1) = 0 for n in { A214858 }.
Sum_{k=0..n} k * T(n,k) = A377572(n).

A127542 Number of subsets of {1,2,3,...,n} whose sum is prime.

Original entry on oeis.org

0, 2, 4, 7, 12, 22, 42, 76, 139, 267, 516, 999, 1951, 3824, 7486, 14681, 28797, 56191, 108921, 210746, 410016, 804971, 1591352, 3153835, 6249154, 12380967, 24553237, 48731373, 96622022, 191012244, 376293782, 739671592, 1454332766, 2867413428, 5678310305

Offset: 1

Emeric Deutsch, Mar 03 2007

nonn

			The subsets of {1,2,3} that sum to a prime are {1,2}, {2}, {3}, {2,3}. Thus a(3)=4.

Charles R Greathouse IV, Table of n, a(n) for n = 1..1000 (first 100 terms from T. D. Noe)

Cf. A053632, A126024, A181522, A010051.

Row sums of A282516.

import Data.List (subsequences)
a127542 = length . filter ((== 1) . a010051 . sum) .
                          subsequences . enumFromTo 1
-- Reinhard Zumkeller, Feb 22 2012, Oct 27 2010

with(combinat): a:=proc(n) local ct, pn, j:ct:=0: pn:=powerset(n): for j from 1 to 2^n do if isprime(add(pn[j][i],i=1..nops(pn[j]))) =true then ct:=ct+1 else ct:=ct fi: od: end: seq(a(n),n=1..18);
# second Maple program:
b:= proc(n, s) option remember; `if`(n=0,
     `if`(isprime(s), 1, 0), b(n-1, s)+b(n-1, s+n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=1..44);  # Alois P. Heinz, Oct 22 2023

g[n_] := Block[{p = Product[1 + z^i, {i, n}]},Sum[Boole[PrimeQ[k]]*Coefficient[p, z, k], {k, 0, n*(n + 1)/2}]];Array[g, 34] (* Ray Chandler, Mar 05 2007 *)

a(n)=my(v=Vec(prod(i=1,n,x^i+1)),s);forprime(p=2,#v,s+=v[p]);s \\ Charles R Greathouse IV, Dec 19 2014

first(n)=my(v=vector(n),P=1,s); for(k=1,n, P*=1+'x^n; s=0; forprime(p=2,k*(k+1)/2,s+=polcoeff(P,p)); v[k]=s); v \\ Charles R Greathouse IV, Dec 19 2014

Extended by Ray Chandler, Mar 05 2007

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

Zak Seidov, Mar 05 2007

nonn

			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.

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

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 *)

Extended by Ray Chandler, Mar 07 2007

More terms from Alois P. Heinz, Jan 18 2014

A284250 Number of subsets of [n] whose sum is a triangular number.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 18, 29, 49, 85, 151, 271, 493, 904, 1674, 3118, 5835, 10966, 20698, 39187, 74413, 141684, 270386, 517110, 990889, 1902108, 3657241, 7042490, 13580079, 26220417, 50687371, 98095126, 190042856, 368539253, 715349145, 1389731960, 2702098563

Offset: 0

Alois P. Heinz, Mar 23 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..600

Row sums of A284249.

Cf. A126024.

b:= proc(n, s) option remember; `if`(n=0,
      `if`(issqr(8*s+1), 1, 0), b(n-1, s)+b(n-1, s+n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..40);

b[n_, s_] := b[n, s] = If[n == 0,
     If[IntegerQ@Sqrt[8*s + 1], 1, 0], b[n - 1, s] + b[n - 1, s + n]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 17 2022, after Alois P. Heinz *)

a(n) = Sum_{k=0..n} A284249(n,k).

A339612 Number of sets of distinct positive integers whose sum of squares is a square, the largest integer of a set is n.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 2, 5, 9, 11, 32, 51, 113, 184, 364, 605, 1175, 2077, 3749, 7108, 12214, 23871, 42474, 82212, 153738, 288842, 555593, 1041563, 2016299, 3809565, 7302893, 13914139, 26591478, 50942383, 97411030, 186943685, 358286670, 689827822, 1326042612, 2558758426

Offset: 1

Ilya Gutkovskiy, Dec 09 2020

nonn

			a(10) = 11 sets: {10}, {1, 2, 4, 10}, {1, 2, 8, 10}, {2, 4, 7, 10}, {5, 6, 8, 10}, {1, 5, 7, 9, 10}, {3, 4, 6, 8, 10}, {1, 3, 4, 7, 9, 10}, {1, 2, 3, 5, 6, 9, 10}, {1, 2, 5, 7, 8, 9, 10} and {1, 2, 3, 4, 7, 8, 9, 10}.

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

Cf. A000290, A126024, A336815.

a = lambda n: b(n-1, n*n, 1) # for b() in A336815
print([a(n) for n in range(1, 30)]) # Michael S. Branicky, Dec 10 2020

a(n) = A336815(n) - A336815(n-1).

a(24)-a(40) from Michael S. Branicky, Dec 09 2020

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

Reinhard Zumkeller, Oct 27 2010

nonn

			a(4) = #{{1,3}, {4}, {1,2,3}, {2,4}, {2,3,4}, {1,2,3,4}} = 6.

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

Cf. A127542, A126024.

Cf. A064911.

import Data.List (subsequences)
a181522 = length . filter ((== 1) . a064911 . sum) .
                          subsequences . enumFromTo 1
-- Reinhard Zumkeller, Feb 22 2012, Oct 27 2010

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

Ilya Gutkovskiy, Dec 07 2020

			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}.

Michael S. Branicky, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Palindromic Number
Index entries for sequences related to palindromes

Cf. A002113, A126024, A126111, A127542, A284250, A339508.

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

a(23)-a(36) from Michael S. Branicky, Dec 08 2020

a(37)-a(39) from Chai Wah Wu, Dec 11 2020

A336815 Number of subsets of {1..n} whose sum of squares of elements is a square.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 10, 12, 17, 26, 37, 69, 120, 233, 417, 781, 1386, 2561, 4638, 8387, 15495, 27709, 51580, 94054, 176266, 330004, 618846, 1174439, 2216002, 4232301, 8041866, 15344759, 29258898, 55850376, 106792759, 204203789, 391147474, 749434144, 1439261966

Offset: 0

Ilya Gutkovskiy, Dec 09 2020

nonn

			a(8) = 17 subsets: {}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {3, 4}, {6, 8}, {1, 4, 8}, {2, 3, 6}, {2, 4, 5, 6}, {1, 2, 4, 6, 8}, {1, 3, 4, 5, 7} and {2, 4, 6, 7, 8}.

Cf. A000290, A126024, A339612.

from sympy.ntheory.primetest import is_square
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, sos, c):
  if n == 0:
    if is_square(sos): return 1
    return 0
  return b(n-1, sos, c) + b(n-1, sos+n*n, c+1)
a = lambda n: b(n, 0, 0)
print([a(n) for n in range(40)]) # Michael S. Branicky, Dec 10 2020

a(n) = 1 + Sum_{k=1..n} A339612(k).

a(24)-a(38) from Michael S. Branicky, Dec 09 2020

A339484 Number of subsets of {1..n} whose cardinality is equal to the average of the elements.

Original entry on oeis.org

1, 1, 2, 3, 4, 7, 11, 17, 28, 47, 80, 139, 245, 436, 784, 1419, 2585, 4738, 8729, 16154, 30015, 55966, 104682, 196378, 369384, 696494, 1316252, 2492683, 4729673, 8990374, 17118020, 32644544, 62345875, 119235519, 228333179, 437790086, 840362539, 1614894770, 3106516468

Offset: 1

Ilya Gutkovskiy, Dec 06 2020

nonn

			a(6) = 7 subsets: {1}, {1, 3}, {1, 2, 6}, {1, 3, 5}, {2, 3, 4}, {1, 4, 5, 6} and {2, 3, 5, 6}.

Alois P. Heinz, Table of n, a(n) for n = 1..300
Eric W. Weisstein's World of Mathematics, Arithmetic Mean

Cf. A051293, A126024.

from itertools import combinations
def a(n):
    ss, s = 0, range(1, n+1)
    for r in range(1, n+1):
        rr = r*r
        ss += sum(sum(subs)==rr for subs in combinations(s, r))
    return ss
print([a(n) for n in range(1, 21)]) # Michael S. Branicky, Dec 06 2020

from functools import lru_cache
from itertools import combinations
@lru_cache(maxsize=None)
def A339484(n):
    return 1 if n == 1 else A339484(n-1)+sum(sum(d)+n==(i+1)**2 for i in range(1,n) for d in combinations(range(1,n),i)) # Chai Wah Wu, Dec 07 2020

from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, s, c):
    if n == 0: return c and int(s == c*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, 101)]) # Michael S. Branicky, Oct 06 2022

a(24)-a(32) from Michael S. Branicky, Dec 06 2020
a(33)-a(35) from Chai Wah Wu, Dec 07 2020
a(36)-a(39) from Michael S. Branicky, Dec 08 2020

A339554 Number of subsets of {1..n} whose sum is a perfect power.

Original entry on oeis.org

1, 1, 2, 5, 9, 15, 25, 48, 99, 187, 326, 543, 896, 1497, 2568, 4554, 8504, 17074, 36011, 75842, 153964, 298835, 561337, 1044317, 1968266, 3796589, 7448571, 14648620, 28541211, 54900185, 104612044, 198620706, 377264405, 717303565, 1363083731, 2585928327

Offset: 1

Ilya Gutkovskiy, Dec 08 2020

nonn

			a(6) = 15 subsets: {1}, {4}, {1, 3}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {1, 4, 5, 6}, {2, 3, 5, 6} and {1, 2, 3, 4, 6}.

Eric Weisstein's World of Mathematics, Perfect Power

Cf. A001597, A126024, A126111, A339555.

from sympy import perfect_power
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, s, c):
  if n == 0:
    if c > 0 and (s==1 or perfect_power(s)): return 1
    return 0
  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, 37)]) # Michael S. Branicky, Dec 10 2020

a(25)-a(36) from Alois P. Heinz, Dec 08 2020

cp's OEIS Frontend

A281871 Number T(n,k) of k-element subsets of [n] having a square element sum; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A127542 Number of subsets of {1,2,3,...,n} whose sum is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Extensions

A126111 Number of subsets of {1,2,3,...,n} whose sum is a cube.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A284250 Number of subsets of [n] whose sum is a triangular number.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A339612 Number of sets of distinct positive integers whose sum of squares is a square, the largest integer of a set is n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A181522 Number of subsets of {1,2,...,n} whose sum is semiprime (cf. A001358, A064911).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

A339507 Number of subsets of {1..n} whose sum is a decimal palindrome.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Python

Python

Extensions

A336815 Number of subsets of {1..n} whose sum of squares of elements is a square.

Views