A367116 a(0) = 1; for n >= 1, a(n) is the largest number m = Product_{j=1..k} (b(j)-1) where {b(1), ..., b(k)} is a vector of positive integers such that Sum_{i=1..k} b(i)^2 = n.

1, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 2, 0, 0, 3, 2, 4, 0, 3, 2, 4, 0, 3, 6, 4, 8, 3, 6, 4, 8, 9, 6, 12, 8, 16, 6, 12, 8, 16, 18, 12, 24, 16, 32, 12, 24, 27, 32, 36, 24, 48, 32, 64, 24, 48, 54, 64, 72, 48, 96, 64, 128, 81, 96, 108, 128, 144, 96, 192, 128, 256

Offset: 0

Author

Yifan Xie, Dec 16 2023

Keywords

• nonn

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)

Examples

			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.
		

Links

• Yifan Xie, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A000290, A000792, A078134

Programs

Mathematica

a[nn_] := Module[{v},v = {1};For[n = 2, n <= nn, n++,Module [{i=1,t=0},While[i^2James C. McMahon, Dec 17 2023 From PARI *)

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;}

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