A003995 -id:A003995 - cp's OEIS frontend

A192336 Sums of two or more distinct squares.

5, 10, 13, 14, 17, 20, 21, 25, 26, 29, 30, 34, 35, 37, 38, 39, 40, 41, 42, 45, 46, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 68, 69, 70, 71, 73, 74, 75, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 94, 95, 97, 98, 99, 100, 101, 102, 103, 104

Offset: 1

Charles R Greathouse IV, Jun 28 2011

			5 = 1^2 + 2^2 and 25 = 3^2 + 4^2 are members, but 2 = 1^2 + 1^2 and 36 = 6^2 are not.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (2,-1).
Index entries for sequences related to sums of squares

Complement of A028237; subset of A003995.

upto(lim)={
  my(x='x,A=prod(k=1,sqrt(lim),1+x^(k^2),1+O(x^floor(lim+1))),v=List());
  A-=sum(k=0,sqrt(lim),x^(k^2));
  for(n=5,lim,if(polcoeff(A,n),listput(v,n)));
  Vec(v)
};

from itertools import combinations
def aupto(lim):
  s = [i*i for i in range(1, int(lim**.5)+2) if i*i <= lim]
  ss = set(sum(c) for i in range(2, len(s)+1) for c in combinations(s, i))
  return sorted(filter(lambda x: x <= lim, ss))
print(aupto(104)) # Michael S. Branicky, May 10 2021

a(n) = n + 37 for n >= 92.

A242434 Number of compositions of n in which each part p has multiplicity p.

Original entry on oeis.org

1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 4, 0, 0, 10, 60, 0, 1, 5, 0, 0, 15, 105, 0, 0, 0, 36, 286, 0, 0, 1281, 12768, 0, 0, 0, 56, 504, 1, 7, 2520, 27720, 28, 378, 1260, 0, 0, 7014, 84000, 0, 0, 4621, 83168, 360360, 210, 2346, 2522880, 37837800, 13860, 180180, 120, 1320

Offset: 0

Alois P. Heinz, May 14 2014

a(n) = 0 for n in {A001422}, a(n) > 0 for n in {A003995}.

			a(0) = 1: the empty composition.
a(1) = 1: [1].
a(4) = 1: [2,2].
a(5) = 3: [1,2,2], [2,1,2], [2,2,1].
a(9) = 1: [3,3,3].
a(10) = 4: [1,3,3,3], [3,1,3,3], [3,3,1,3], [3,3,3,1].
a(13) = 10: [2,2,3,3,3], [2,3,2,3,3], [2,3,3,2,3], [2,3,3,3,2], [3,2,2,3,3], [3,2,3,2,3], [3,2,3,3,2], [3,3,2,2,3], [3,3,2,3,2], [3,3,3,2,2].

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

Cf. A033461 (the same for partitions), A336269.

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
       b(n, i-1, p) +`if`(i^2>n, 0, b(n-i^2, i-1, p+i)/i!)))
    end:
a:= n-> b(n, isqrt(n), 0):
seq(a(n), n=0..100);

b[n_, i_, p_] := b[n, i, p] = If[n==0, p!, If[i<1, 0, b[n, i-1, p] + If[i^2 >n, 0, b[n-i^2, i-1, p+i]/i!]]]; a[n_] := b[n, Floor[Sqrt[n]], 0]; Table[ a[n], {n, 0, 100}] (* Jean-François Alcover, Feb 08 2017, translated from Maple *)

A379857 Number of values of k for which n can be written as a sum of k distinct positive squares.

Original entry on oeis.org

1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 0, 2, 2, 0, 0, 2, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 1, 0, 1, 3, 3, 0, 1, 2, 2, 1, 3, 2, 1, 2

Offset: 0

Luke E. Holland, Jan 04 2025

It appears that a(n) is not bounded, but grows very slowly.

First differs from A033461 at n=62 which can be written as A033461(62) = 3 sums of squares, but among them only a(62) = 2 different numbers of squares.

			a(0) = 1, as it is the sum of 0 squares.
a(25) = 2, as 25 = 5^2 = 4^2 + 3^2, so k can be 1 or 2.
a(90) = 4, as 90 = 9^2 + 3^2 = 8^2 + 5^2 + 1^2 = 8^2 + 4^2 + 3^2 + 1^2 = 6^2 + 5^2 + 4^2 + 3^2 + 2^2, so k can be 2, 3, 4 or 5.

Luke E. Holland, Table of n, a(n) for n = 0..10000
Paul T. Bateman, Adolf J. Hildebrand, and George B. Purdy, Sums of distinct squares, Acta Arithmetica 67 (1994), pp. 349-380.

Cf. A001422 (indices of 0's), A003995 (indices of not 0).

Cf. A379831 (indices of records).

MAXSQUARE = 500
possibleSums = {i: [[], []] for i in range(MAXSQUARE ** 2 + 1)}
possibleSums[0] = [[0],[0]]
for val in range(MAXSQUARE ** 2):
    for posSquare in range(len(possibleSums[val][0])):
        newSum = possibleSums[val][0][posSquare] + 1
        curr = possibleSums[val][1][posSquare] + 1
        while val + curr ** 2 <= MAXSQUARE ** 2:
            nVal = val + curr ** 2
            if newSum not in possibleSums[nVal][0]:
                possibleSums[nVal][0].append(newSum)
                possibleSums[nVal][1].append(curr)
            else:
                index = possibleSums[nVal][0].index(newSum)
                if curr < possibleSums[nVal][1][index]:
                    possibleSums[nVal][1][index] = curr
            curr += 1
posKVals = tuple([len(possibleSums[i][0]) for i in range(MAXSQUARE ** 2 + 1)])

from itertools import count
from sympy.solvers.diophantine.diophantine import power_representation
def A379857(n):
    if n == 0: return 0
    c = 0
    for i in count(1):
        if i*(i+1)*((i<<1)+1)>6*n:
            break
        if any(len(set(t))==i for t in power_representation(n,2,i)):
            c += 1
    return c # Chai Wah Wu, Jan 28 2025

a(n) < (3n)^(1/3) for n > 0. I conjecture that a(n) ~ (3n)^(1/3). - Charles R Greathouse IV, Feb 05 2025

A380175 Greedy sums of distinct squares.

Original entry on oeis.org

0, 1, 4, 5, 9, 10, 13, 14, 16, 17, 20, 21, 25, 26, 29, 30, 34, 35, 36, 37, 40, 41, 45, 46, 49, 50, 53, 54, 58, 59, 62, 63, 64, 65, 68, 69, 73, 74, 77, 78, 80, 81, 82, 85, 86, 90, 91, 94, 95, 97, 98, 100, 101, 104, 105, 109, 110, 113, 114, 116, 117, 120, 121, 122, 125, 126, 130

Offset: 1

Mike Sheppard, Jan 14 2025

nonn

Let n be a positive integer. Suppose that s1^2 is the largest square not exceeding n, that s2^2 is the largest square not exceeding n-s1^2, and so on, so that n=s1^2+s2^2+...+sr^2 for some r. Clearly the si are weakly decreasing, but if they are strictly decreasing, s1>s2>...>sr, then we say that n is a greedy sum of distinct squares.

The set of integers for which the summands are distinct does not have a natural density, but the counting function oscillates in a predictable way (see Montgomery link).

			21 is a term since greedily taking squares is 21 = 4^2 + 2^2 + 1^2 and all are distinct.
38 is not a term since greedily 38 = 6^2 + 1^2 + 1^2 and 1^2 has repeated (it can be distinct squares 38 = 5^2 + 3^2 + 2^2 but that's not the greedy sum).

Robert Israel, Table of n, a(n) for n = 1..10000
Hugh Montgomery and Ulrike Vorhauer, Greedy sums of distinct squares, Mathematics of Computation 73.245 (2004): 493-513.

Cf. A003995 (if not taken greedily), A380177.

filter:= proc(n) local s,x;
  s:= n; x:= floor(sqrt(s));
  do
    s:= s - x^2;
    if s >= x^2 then return false fi;
    if s = 0 then return true fi;
    x:= floor(sqrt(s))
  od;
end proc:
filter(0):= true:
select(filter, [$0..1000]); # Robert Israel, Feb 14 2025

Select[Range[0,200], DuplicateFreeQ[#] &@ Differences[NestWhileList[# - Floor[Sqrt[#]]^2 &, #, # > 0 &]] &]

from math import isqrt
def ok(n):
    rprev = n+1
    while 0 < (r:=isqrt(n)) < rprev: n, rprev = n-r**2, r
    return r == 0
print([k for k in range(131) if ok(k)]) # Michael S. Branicky, Jan 15 2025

A111755 Excess of n over a greedy sum of distinct squares.

Original entry on oeis.org

0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 2, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 2, 0, 0, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0

Offset: 1

John W. Layman, Nov 21 2005

Start with the value n and subtract the largest square (not previously used) less than or equal to n to get a new value. Repeat until the value 0 is reached or the square 1 has been subtracted. The resulting value is a(n). It is not hard to prove that a(n) always lies in 0..3 inclusive.

All nonzero terms are one greater than the previous term. - Iain Fox, Oct 17 2018

			a(24)=3, since 24 -> 24 - 16 = 8 -> 8 - 4 = 4 -> 4 - 1 = 3.

Iain Fox, Table of n, a(n) for n = 1..10000

Cf. A003995.

f[n_] := Block[{s = n, k = Floor@Sqrt@n}, While[k > 0, If[s >= k^2, s -= k^2]; k-- ]; s]; Array[f, 105] (* Robert G. Wilson v, Nov 22 2005 *)

a(n) = my(s=sqrtint(n)); while(s > 0, if(n >= s^2, n -= s^2); s--); n \\ Iain Fox, Oct 17 2018

a(A003995(n)) = 0. - Iain Fox, Oct 17 2018

A289895 Numbers that are the sum of distinct square pyramidal numbers (A000330).

Original entry on oeis.org

0, 1, 5, 6, 14, 15, 19, 20, 30, 31, 35, 36, 44, 45, 49, 50, 55, 56, 60, 61, 69, 70, 74, 75, 85, 86, 90, 91, 92, 96, 97, 99, 100, 104, 105, 106, 110, 111, 121, 122, 126, 127, 135, 136, 140, 141, 145, 146, 147, 151, 152, 154, 155, 159, 160, 161, 165, 166, 170, 171, 175, 176, 177, 181, 182, 184, 185, 189, 190, 191, 195, 196, 200

Offset: 1

Ilya Gutkovskiy, Jul 14 2017

nonn

It appears that 1528 is the largest of 306 positive integers not in this sequence.

			20 is in the sequence because 20 = 1 + 5 + 14 = 1^2 + 1^2 + 2^2 + 1^2 + 2^2 + 3^2.

Cf. A000330, A003995.

max = 200; f[x_] := Product[1 + x^(k (k + 1) (2 k + 1)/6), {k, 1, 10}]; Exponent[#, x] & /@ List @@ Normal[Series[f[x], {x, 0, max}]]

Exponents in expansion of Product_{k>=1} (1 + x^(k*(k+1)*(2*k+1)/6)).

A290275 Numbers that are the sum of distinct odd positive squares.

Original entry on oeis.org

1, 9, 10, 25, 26, 34, 35, 49, 50, 58, 59, 74, 75, 81, 82, 83, 84, 90, 91, 106, 107, 115, 116, 121, 122, 130, 131, 139, 140, 146, 147, 155, 156, 164, 165, 169, 170, 171, 178, 179, 180, 194, 195, 196, 202, 203, 204, 205, 211, 212, 218, 219, 225, 226, 227, 228, 234, 235, 236, 237, 243, 244, 250, 251, 252, 253

Offset: 1

Ilya Gutkovskiy, Jul 25 2017

nonn

Complement of A167703.

1922 is the largest of positive integers not in this sequence.

			139 is in the sequence because 139 = 9 + 49 + 81 = 3^2 + 7^2 + 9^2.

Cf. A003995, A016754, A097269, A167700, A167703.

max = 253; f[x_] := Product[1 + x^(2 k + 1)^2, {k, 0, 10}]; Exponent[#, x] & /@ List @@ Normal[Series[f[x], {x, 0, max}]] // Rest

A379831 Positions of records in A379857.

Original entry on oeis.org

0, 25, 50, 90, 146, 169, 260, 289, 425, 529, 625, 900, 1156, 1521, 1681, 2025, 2500, 2704, 3434, 3600, 4225, 4624, 4900, 5625, 7146, 7225, 8281, 9409, 10404, 11236, 11881, 13225, 14400, 15129, 16900, 18769, 19600, 21316, 23409, 25281, 26896, 28561, 30625, 32400, 34969, 36100, 40000, 41209, 44944, 47524

Offset: 1

Luke E. Holland, Jan 03 2025

nonn

This sequence is infinite in length.
Not all terms are squares, meaning that sometimes k=1 is not among the k values which set a new record.
Elements of this sequence are often, but not always, records of A033461.

			25 is a member of this sequence, as 25 = 5^2 = 3^2 + 4^2, meaning that it can be expressed as a sum of k squares for two values of k, in this case 1 and 2, which is more than any smaller value.
50 is a member of this sequence, as 50 = 7^2 + 1^2 = 5^2 + 4^2 + 3^2 = 6^2 + 3^2 + 2^2 + 1^2, giving 3 possible values of k, being 2, 3 and 4, more than any smaller value.
0 begins this sequence, as it is the sum of zero squares, so it has one possible value of k, being k = 0.

Index entries for sequences related to sums of squares

Cf. A033461, A003995, A001156, A379857.

MAXSQUARE = 500
possibleSums = {i: [[], []] for i in range(MAXSQUARE ** 2 + 1)}
possibleSums[0] = [[0], [0]]
for val in range(MAXSQUARE ** 2):
    for posSquare in range(len(possibleSums[val][0])):
        newSum = possibleSums[val][0][posSquare] + 1
        curr = possibleSums[val][1][posSquare] + 1
        while val + curr ** 2 <= MAXSQUARE ** 2:
            nVal = val + curr ** 2
            if newSum not in possibleSums[nVal][0]:
                possibleSums[nVal][0].append(newSum)
                possibleSums[nVal][1].append(curr)
            else:
                index = possibleSums[nVal][0].index(newSum)
                if curr < possibleSums[nVal][1][index]:
                    possibleSums[nVal][1][index] = curr
            curr += 1
best = 0
for i in range(MAXSQUARE ** 2 + 1):
    if len(possibleSums[i][0]) > best:
        print(i)
        best = len(possibleSums[i][0])
records = ()
best = 0
for i in range(MAXSQUARE ** 2 + 1):
    sums = len(possibleSums[i][0])
    if sums > best:
        records += (i, )
        best = sums

a(n) >> n^3. - Charles R Greathouse IV, Jan 06 2025

A380177 Numbers that can be written as sum of distinct squares but not if the squares are taken greedily.

Original entry on oeis.org

38, 39, 42, 51, 52, 55, 56, 57, 61, 66, 70, 71, 75, 79, 83, 84, 87, 88, 89, 93, 99, 102, 103, 106, 107, 111, 115, 118, 119, 123, 124, 127, 129, 132, 133, 136, 139, 140, 143, 146, 147, 150, 151, 152, 155, 156, 159, 162, 163, 166, 167, 168, 171, 172, 175, 176, 177, 180

Offset: 1

Mike Sheppard, Jan 14 2025

nonn

Numbers in A003995 but not in A380175.

			38 is in the list as 38 = 5^2 + 3^2 + 2^2, all distinct; but if taken greedily 38 = 6^2 + 1^2 + 1^2, not distinct. Greedily in the sense that 6^2 < 38 < 7^2 etc.

Hugh Montgomery and Ulrike Vorhauer, Greedy sums of distinct squares, Mathematics of computation 73.245 (2004): 493-513.

Cf. A003995, A380175.

A003996 Sums of distinct nonzero squares in more than one way.

Original entry on oeis.org

25, 26, 29, 30, 41, 45, 46, 49, 50, 53, 54, 61, 62, 65, 66, 69, 70, 74, 75, 77, 78, 79, 81, 82, 84, 85, 86, 87, 89, 90, 91, 93, 94, 95, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123

Offset: 1

N. J. A. Sloane

nonn

The largest integer not in this sequence is 132. Proof based on Theorem 3 from M. J. Wiener link: All the numbers from 148+1 to 148+12^2 are the sum of distinct squares from {1^2,...,11^2} in more than one way (direct calculation). This range can be extended indefinitely by adding 12^2, 13^2, etc. Numbers between 132 and 148 confirmed from A033461. - Martin Fuller, Aug 28 2023

M. J. Wiener, The Largest Integer Not the Sum of Distinct 8th Powers, J. Integer Sequences, 26 (2023), Article 23.5.4.
Index entries for sequences related to sums of squares

Cf. A033461, A003995.

For n >= 65, a(n) = n + 68 (see comment). - Martin Fuller, Aug 28 2023

cp's OEIS Frontend

A192336 Sums of two or more distinct squares.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A242434 Number of compositions of n in which each part p has multiplicity p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A379857 Number of values of k for which n can be written as a sum of k distinct positive squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

A380175 Greedy sums of distinct squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A111755 Excess of n over a greedy sum of distinct squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A289895 Numbers that are the sum of distinct square pyramidal numbers (A000330).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A290275 Numbers that are the sum of distinct odd positive squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica