A309778 a(n) is the greatest integer such that, for every positive integer k <= a(n), n^2 can be written as the sum of k positive square integers.

1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 155, 1, 211, 1, 275, 1, 1, 2, 1, 1, 1, 1, 611, 662, 1, 1, 827, 886, 1, 1, 1, 1142, 1211, 1, 1355, 1, 1507, 2, 1667, 1, 1, 1, 2011, 1, 1, 1, 1, 2486, 2587, 2690, 2795, 1, 3011, 1, 1, 3350, 1, 3586, 3707, 1, 1, 1

Offset: 1

Author

Bernard Schott, Aug 17 2019

Keywords

• nonn

Comments

The idea for this sequence comes from the 6th problem of the 2nd day of the 33rd International Mathematical Olympiad in Moscow, 1992 (see link).

There are four cases to examine and three possible values for a(n).

a(n) = 1 iff n is a nonhypotenuse number or iff n is in A004144.

a(n) >= 2 iff n is a hypotenuse number or iff n is in A009003.

a(n) = 2 iff n^2 is the sum of two positive squares but not the sum of three positive squares or iff n^2 is in A309779.

a(n) = n^2 - 14 iff n^2 is the sum of two and three positive squares or iff n^2 is in A231632.

Theorem: a square n^2 is the sum of k positive squares for all 1 <= k <= n^2 - 14 iff n^2 is the sum of 2 and 3 positive squares (proof in Kuczma). Consequently: A231632 = A018820.

Examples

			1 = 1^2, 4 = 2^2 and a(1) = a(2) = 1.
25 = 5^2 = 3^2 + 4^2 and a(5) = 2.
The first representations of 169 are 13^2 = 12^2 + 5^2 = 12^2 + 4^2 + 3^2 = 11^2 + 4^2 + 4^2 + 4^2 =  6^2 + 6^2 + 6^2 + 6^2 + 5^2  = 6^2 + 6^2 + 6^2 + 6^2 + 4^2 + 3^2 = ... and a(13) = 13^2 - 14 = 155.
		

References

• Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 76-79.

Links

• IMO, 1992, Moscow, Second day. Problem 6

Crossrefs

Cf. A018820, A004144, A009003, A231632, A309779.