# Numbers not Sum of Distinct Squares

## 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

This needs considerable tedious hard slog to complete it.In particular: a) Demonstration that these cannot be so expressed, b) demonstration that all others below 324 can be so expressedTo discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Finish}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

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:

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

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

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

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

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

\(\ds \) | \(>\) | \(\ds 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.

This article needs proofreading.Please check it for mathematical errors.If you believe there are none, please remove `{{Proofread}}` from the code.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Proofread}}` from the code. |

## 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$