A382383 -id:A382383 - cp's OEIS frontend

A208531 Number of distinct sums of subsets of the first n squares {1,4,9,...,n^2}.

2, 4, 8, 16, 28, 52, 89, 147, 224, 324, 445, 589, 758, 954, 1179, 1435, 1724, 2048, 2409, 2809, 3250, 3734, 4263, 4839, 5464, 6140, 6869, 7653, 8494, 9394, 10355, 11379, 12468, 13624, 14849, 16145, 17514, 18958, 20479, 22079, 23760, 25524, 27373, 29309, 31334

Offset: 1

John W. Layman, Feb 27 2012

nonn

From the 9th term onward the differences of this sequence appear to again be the squares. Is there a simple explanation for this?
Similar examples are provided for the positive integers in A000124, the odd integers in A082562 and the primes in A082548.
For n > 9: a(n) - a(n-1) = n^2 up to at least n = 1785. - Zak Seidov and Jud McCranie, Feb 29 2012
To compute the terms in order, start with a list with the element 0. Add 1^2 to each term of the list and add the sum to the list, if it isn't already on the list. The cardinality of the list is a(1). Then a(n+1) is computed by adding n^2 to each member of the list and adding the sum to the list, if it isn't already there. The number of members of the list is a(2). This is much faster than considering every subset. - Jud McCranie, Mar 01 2012

			All subsets of {1,4,9,16} give distinct sums, so a(4)=16. Four pairs of subsets of {1,4,9,16,25} have the same sum, for example {9,16} and {25}, resulting in a(5)=28.

Toshitaka Suzuki, Proof of a conjectured formula for A208531, Jul 29 2019

Cf. A000124, A082548, A082562, A382383.

Table[Length[Union[Total /@ Subsets[Range[n]^2]]], {n, 17}] (* T. D. Noe, Feb 28 2012 *)

Conjectures from Colin Barker, Feb 15 2016: (Start)
a(n) = (2*n^3+3*n^2+n-366)/6 for n>8.
a(n) = 4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4) for n>12.
G.f.: x*(2-4*x+4*x^2-2*x^4+8*x^5-7*x^6+7*x^7-10*x^8+6*x^9-6*x^10+4*x^11) / (1-x)^4. (End)
For a proof of these conjectures see the Suzuki (2019) link.

a(23)-a(26) from Zak Seidov, Feb 29 2012
a(27)-a(40) from Jud McCranie, Feb 29 2012
a(41)-a(45) from Pontus von Brömssen, Mar 29 2025

A382381 Lexicographically earliest sequence of distinct positive integers such that any two subsets with at least two terms have distinct variances.

Original entry on oeis.org

1, 2, 4, 8, 16, 25, 36, 62, 136, 320, 411, 1208, 1295, 4179, 5143, 6380, 31370, 34425, 36094, 213044, 218759, 306722

Offset: 1

Pontus von Brömssen, Mar 23 2025

Numbers k such that A381856(k) = 1.
The variance of a nonempty set X is (Sum_{x in X} (x-m)^2)/|X|, where m is the average of X and |X| is the size of X.
a(20) > 100000.

Cf. A138857, A260873, A381856, A382382, A382383.

from fractions import Fraction
from itertools import chain, combinations, count, islice
def powerset(s): # skipping empty set
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))
def agen(): # generator of terms
    an, alst, vset = 1, [1], set()
    while True:
        yield an
        P = list(powerset(alst))
        Xlst, X2lst = [sum(s) for s in P], [sum(si**2 for si in s) for s in P]
        for k in count(an+1):
            ok, vnew = True, set()
            for i, s in enumerate(P):
                mu, X2 = Fraction(Xlst[i] + k, len(s)+1), X2lst[i] + k**2
                v = Fraction(X2, len(s)+1) - mu**2
                if v in vset or v in vnew:
                    ok = False
                    break
                else:
                    vnew.add(v)
            if ok:
                break
        an = k
        vset |= vnew
        alst.append(an)
print(list(islice(agen(), 13))) # Michael S. Branicky, Mar 31 2025

a(20)-a(21) from Michael S. Branicky, Mar 31 2025

a(22) from Michael S. Branicky, Apr 07 2025

A382382 Least k for which there exists an n-subset X of {0, ..., k} such that the variances of the subsets of X of size at least 2 are distinct.

Original entry on oeis.org

0, 1, 3, 6, 11, 17, 27, 48

Offset: 1

Pontus von Brömssen, Mar 23 2025

The variance of a nonempty set Y is (Sum_{y in Y} (y-m)^2)/|Y|, where m is the average of Y and |Y| is the size of Y.

0 and a(n) necessarily belong to the set X in the definition.

			    | a set X that satisfy the condition
  n | (the largest element of X is a(n))
  --+-----------------------------------
  1 | {0}
  2 | {0, 1}
  3 | {0, 1, 3}
  4 | {0, 1, 4,  6}
  5 | {0, 2, 7,  8, 11}
  6 | {0, 1, 4, 10, 12, 17}
  7 | {0, 3, 4, 14, 19, 21, 27}
  8 | {0, 1, 5, 15, 22, 40, 46, 48}

Cf. A003022, A382381, A382383.

A003022(n) <= a(n) < A382381(n) for n >= 2.

A382833 Square array read by antidiagonals: T(n,k) is the number of distinct sum-of-powers vectors (Sum_{x in X} x^m, 0 <= m <= k) for subsets X of {0, ..., n-1}; n, k >= 0.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 2, 4, 4, 1, 2, 4, 8, 5, 1, 2, 4, 8, 15, 6, 1, 2, 4, 8, 16, 26, 7, 1, 2, 4, 8, 16, 32, 42, 8, 1, 2, 4, 8, 16, 32, 64, 64, 9, 1, 2, 4, 8, 16, 32, 64, 126, 93, 10, 1, 2, 4, 8, 16, 32, 64, 128, 247, 130, 11, 1, 2, 4, 8, 16, 32, 64, 128, 256, 476, 176, 12

Offset: 0

Pontus von Brömssen, Apr 10 2025

			Array begins:
  n\k|  0   1     2     3     4
  ---+-------------------------
   0 |  1   1     1     1     1
   1 |  2   2     2     2     2
   2 |  3   4     4     4     4
   3 |  4   8     8     8     8
   4 |  5  15    16    16    16
   5 |  6  26    32    32    32
   6 |  7  42    64    64    64
   7 |  8  64   126   128   128
   8 |  9  93   247   256   256
   9 | 10 130   476   512   512
  10 | 11 176   908  1024  1024
  11 | 12 232  1682  2048  2048
  12 | 13 299  3067  4080  4096
  13 | 14 378  5364  8128  8192
  14 | 15 470  9132 16128 16384
  15 | 16 576 14948 31992 32768
  16 | 17 697 23635 63163 65520
For n = 4, k = 1, there is only one pair of subsets of {0, 1, 2, 3} for which the two subsets have the same number of elements (sum of 0th powers) and the same sum (sum of 1st powers), namely {0, 3}, {1, 2}. Hence, T(4,1) = 2^4-1 = 15.

Cf. A000027 (column k=0), A000125 (column k=1), A382383, A382832.

T(n,k) <= 2^n with equality if and only if n < A382832(k).

cp's OEIS Frontend

A208531 Number of distinct sums of subsets of the first n squares {1,4,9,...,n^2}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A382381 Lexicographically earliest sequence of distinct positive integers such that any two subsets with at least two terms have distinct variances.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Extensions

A382382 Least k for which there exists an n-subset X of {0, ..., k} such that the variances of the subsets of X of size at least 2 are distinct.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A382833 Square array read by antidiagonals: T(n,k) is the number of distinct sum-of-powers vectors (Sum_{x in X} x^m, 0 <= m <= k) for subsets X of {0, ..., n-1}; n, k >= 0.

Views

Author

Keywords

Examples

Crossrefs

Formula