|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
