cp's OEIS Frontend

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.

%I A062535 #12 Aug 02 2023 02:08:59
%S A062535 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,
%T A062535 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,
%U A062535 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
%N 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.
%H A062535 G. C. Greubel, <a href="/A062535/b062535.txt">Table of n, a(n) for n = 1..5000</a>
%F A062535 a(n) = A053610(n) - A002828(n).
%e A062535 a(32)=5-2=3 since 32 can be written greedily as 25+4+1+1+1 or efficiently as 16+16.
%t A062535 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 *)
%o A062535 (Python)
%o A062535 from math import isqrt
%o A062535 from sympy import factorint
%o A062535 def A062535(n):
%o A062535     c, k, f = 0, n, factorint(n).items()
%o A062535     while k:
%o A062535         k -= isqrt(k)**2
%o A062535         c += 1
%o A062535     if not any(e&1 for p,e in f): return c-1
%o A062535     if all(p&3<3 or e&1^1 for p,e in f): return c-2
%o A062535     return c-3-(((m:=(~n&n-1).bit_length())&1^1)&int((n>>m)&7==7)) # _Chai Wah Wu_, Aug 01 2023
%Y A062535 Cf. A053610, A002828.
%K A062535 nonn
%O A062535 1,32
%A A062535 _Henry Bottomley_, Jun 25 2001