Three squares

Time limit: 3 seconds

The Waring hypothesis states that every non-negative integer may be represented as a sum of K^2 exact K-th powers of non-negative integers. Hilbert proved this fact in 1907; simplier proofs were given by Hardy, Littlewood and Vinogradov, and in 1942 Linnik found an elementary proof.

For K=2 it follows that every non-negative integer is a sum of four squares. We shall not verify this statement, but insted determine the number of integers in the range 0...n that may not be represented as a sum of three squares.

Input consists of a single positive integer n<10000.

Author:
Voroztsov Artem

<PREV | Problem set | Search related messages | NEXT>