# Numbers not Sum of Distinct Squares

## Contents

## Theorem

The positive integers which are not the sum of $1$ or more distinct squares are:

- $2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128$

This sequence is A001422 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

## Proof

It will be proved that the largest integer which cannot be expressed as the sum of distinct squares is $128$.

The remaining integers in the sequence can be identified by inspection.

We prove this using a variant of Second Principle of Mathematical Induction.

Let $\map P n$ be the proposition:

### Basis for the induction

We verify the result up to $18^2 = 324$.

Then we conclude all $n$ with $129 \le n \le 324$ can be expressed as the sum of distinct squares.

So $\map P n$ is true for all $129 \le n \le 324$.

This is the basis for the induction.

### Induction Hypothesis

Suppose for some $k > 324$, $\map P j$ is true for all $129 \le j < k$.

That is, every integer between $129$ and $k - 1$ can be expressed as the sum of distinct squares.

This is the induction hypothesis.

### Induction Step

This is the induction step:

We find the largest integer $i$ such that $i^2 < k \le \paren {i + 1}^2$.

We show that $k - \paren {i - 4}^2$ can be expressed as the sum of distinct squares, and the sum does not involve $\paren {i - 4}^2$.

Then $k$ can be expressed as the sum of distinct squares.

Since $k > 324 = 18^2$, we must have $i \ge 18$.

Hence $k > k - \paren {i - 4}^2 > i^2 - \paren {i - 4}^2 = 4 \paren {2 i - 4} \ge 4 \times 32 = 128$.

Thus $k - \paren {i - 4}^2$ can be expressed as the sum of distinct squares by Induction Hypothesis.

A sufficient condition such that the sum does not involve $\paren {i - 4}^2$ is $\paren {i - 4}^2 > k - \paren {i - 4}^2$.

We have:

\(\displaystyle \paren {i - 4}^2 - \paren {k - \paren {i - 4}^2 }\) | \(\ge\) | \(\displaystyle 2 \paren {i - 4}^2 - \paren {i + 1}^2\) | From $k \le T_{i + 1}$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle 2 i^2 - 16 i + 32 - i^2 - 2 i - 1\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle i^2 - 18 i + 31\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle i \paren {i - 18} + 31\) | |||||||||||

\(\displaystyle \) | \(\ge\) | \(\displaystyle 31\) | From $i \ge 18$ | ||||||||||

\(\displaystyle \) | \(>\) | \(\displaystyle 0\) |

Therefore we have $\paren {i - 4}^2 > k - \paren {i - 4}^2$.

Hence $\map P k$ is true.

By the Second Principle of Mathematical Induction, $\map P n$ is true for all $n \ge 128$.

Thus every integer greater than $128$ can be expressed as the sum of distinct square numbers.

## Sources

- 1948: R. Sprague:
*Über Zerlegungen in ungleiche Quadratzahlen*(*Math. Z.***Vol. 51**: pp. 289 – 290) - 1983: François Le Lionnais and Jean Brette:
*Les Nombres Remarquables* - 1986: David Wells:
*Curious and Interesting Numbers*... (previous) ... (next): $128$ - 1997: David Wells:
*Curious and Interesting Numbers*(2nd ed.) ... (previous) ... (next): $128$