In the Algebraic Number Theory course that I am taking, we covered the problem of when a number is the sum of two squares. I wrote a short expository paper [pdf] to go with it. Here are the positive integers up to 15 which can and cannot be written as the sum of two squares:

**Examples:**

- 1 = 1² + 0²
- 2 = 1² + 1²
- 4 = 2² + 0²
- 5 = 2² + 1²
- 8 = 2² + 2²
- 9 = 3² + 0²
- 10 = 3² + 1²
- 13 = 3² + 2²

**Non-examples:**

- 3
- 6
- 7
- 11
- 12
- 14
- 15

Can you find the pattern? (Note: This is a very hard question. You may need to write down more examples to start noticing it.)

I have also posted some hints.