A380175 Greedy sums of distinct squares.

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,3

Comments

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

Links

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.

Example

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

Maple

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

Mathematica

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

Prog

(Python)
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

Crossrefs

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

Sequence in context: A193259 A008935 A003995 * A064473 A385609 A394621

Adjacent sequences: A380172 A380173 A380174 * A380176 A380177 A380178

Keyword

nonn

Author

Mike Sheppard, Jan 14 2025

Status

approved