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
Keywords
Examples
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).
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.
Programs
-
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 &]] &]
-
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
Comments