OFFSET
0,10
COMMENTS
a(n) = 0 if and only if n cannot be expressed as the sum of positive squares other than 1. The largest such n is 23. See A078134.
All terms can be expressed in the form of 2^x*3^y, with y <= 4.
Proof: (Start)
If prime p >= 5 is a factor of a(n), where n = Sum_{i=1..k} b(i)^2 and a(n) = Product_{i=1..k} (b(k)-1), there must be a number 1 <= j <= k where b(j) = q*p + 1, where q is a positive integer.
If q is odd, b(j)^2 = (q*p + 1)^2 = 4*((q*p + 1)/2)^2 results in q*p, a factor of a(n), being replaced by (q*p - 1)^4/16. Since q*p >= 5, q*p < (q*p - 1)^4/16.
If q is even, b(j)^2 = (2*(q/2)*p + 1)^2 = 4*(q*p/2)^2 + (q*p/2 - 2)*2^2 + 3^2 results in q*p being replaced by (q*p - 2)^4/8. Since q*p >=5, q*p < (q*p - 2)^4/8.
In conclusion, if prime p >= 5 is a factor of a(n), the value of a(n) can be improved, so the a(n) is invalid.
If y >= 5, since 5*4^2 = 80 = 8^3^2 + 2*2^2 results in 3^5 = 243 being replaced by 2^8 = 256 > 243, so the a(n) is invalid. (End)
LINKS
Yifan Xie, Table of n, a(n) for n = 0..1000
FORMULA
a(n) = Max_{i^2 <= n} (i-1)*a(n^2-i).
Let n = 4*k + r, 0 <= r <= 3. a(n) = max{2^(4*ceiling((k - 2*r)/9) + r)*3^(ceiling((k - 2*r - 9*ceiling((k - 2*r)/9))/4)), 2^(4*(ceiling((k - 2*r)/9) - 1) + r)*3^(ceiling((k - 2*r - 9*ceiling((k - 2*r)/9 - 1))/4))}
EXAMPLE
For n = 23, it's impossible to write 23 as the sum of positive squares other than 1, so a(23) = 0;
For n = 69, a(69) = max{0, a(65), 2*a(60), 3*a(53), 4*a(44), 5*a(33), 6*a(20), 7*a(5)} = 2*a(60) = 256.
MATHEMATICA
a[nn_] := Module[{v}, v = {1}; For[n = 2, n <= nn, n++, Module [{i=1, t=0}, While[i^2<n, t=Max[t, (i-1)v[[n-i^2]]]; i++]; v=Append[v, t]; ]]; v]; result=a[77] (* James C. McMahon, Dec 17 2023 From PARI *)
PROG
(PARI) lista(nn) = {my(v = vector(nn+1)); v[1] = 1; for(n=2, nn+1, my(i=1, t=0); for(i=1, sqrtint(n-1), t=max(t, (i-1)*v[n-i*i])); v[n] = t); v; }
CROSSREFS
KEYWORD
nonn
AUTHOR
Yifan Xie, Dec 16 2023
STATUS
approved