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

Links

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

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

Cf. A053610, A002828.

Sequence in context: A280051 A030121 A320659 * A063667 A171063 A308229

Adjacent sequences: A062532 A062533 A062534 * A062536 A062537 A062538

Keyword

nonn

Author

Henry Bottomley, Jun 25 2001

Status

approved