login
A062535
Don't be greedy! Difference between number of squares needed to sum to n using the greedy algorithm and using the best such sum.
5
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 0, 0, 2, 0, 1, 1, 0, 0, 0, 0, 0, 0
OFFSET
1,32
LINKS
FORMULA
a(n) = A053610(n) - A002828(n).
EXAMPLE
a(32)=5-2=3 since 32 can be written greedily as 25+4+1+1+1 or efficiently as 16+16.
MATHEMATICA
f[n_] := (n - Floor[Sqrt[n]]^2); a053610[n_] := (m = n; c = 1; While[a = f[m]; a != 0, c++; m = a]; c); SquareCnt[n_] := If[SquaresR[1, n] > 0, 1, If[SquaresR[2, n] > 0, 2, If[SquaresR[3, n] > 0, 3, 4]]]; (* a002828 *) Table[a053610[n] - SquareCnt[n], {n, 1, 100}] (* G. C. Greubel, Apr 18 2017 *)
PROG
(Python)
from math import isqrt
from sympy import factorint
def A062535(n):
c, k, f = 0, n, factorint(n).items()
while k:
k -= isqrt(k)**2
c += 1
if not any(e&1 for p, e in f): return c-1
if all(p&3<3 or e&1^1 for p, e in f): return c-2
return c-3-(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # Chai Wah Wu, Aug 01 2023
CROSSREFS
Sequence in context: A280051 A030121 A320659 * A063667 A171063 A308229
KEYWORD
nonn
AUTHOR
Henry Bottomley, Jun 25 2001
STATUS
approved