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.

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

Author

Henry Bottomley, Jun 25 2001

Keywords

• nonn

Examples

			a(32)=5-2=3 since 32 can be written greedily as 25+4+1+1+1 or efficiently as 16+16.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..5000

Crossrefs

Cf. A053610, A002828.

Programs

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

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

Formula

a(n) = A053610(n) - A002828(n).