Number Theory – Algorithm for Writing a Number as a Sum of Three Squares

nt.number-theory

By Gauss's Theorem, every positive integer $n$ is a sum of three triangular numbers;
these are numbers of the form $\frac{m(m+1)}2$. Clearly
$$ n = \frac{m_1^2+m_1}2 + \frac{m_2^2+m_2}2 + \frac{m_3^2+m_3}2, $$
so multiplying through by $4$ and completing the squares gives
$$ 8n+3 = (2m_1+1)^2 + (2m_2+1)^2 + (2m_3+1)^2. $$
Thus writing $n$ as a sum of three triangular numbers is equivalent to writing $8n+3$ as a sum of three (necessarily odd) squares.

My question is;

Is there an algorithm for writing a positive integer as a sum of three squares?

Best Answer

A representation of $n$ as a sum of three triangular numbers is equivalent to representing $8n+3$ as a sum of three odd squares. The question of computing representations as a sum of three squares has been much discussed here, see Efficient computation of integer representation as a sum of three squares

Related Question