### A002313 - Primes congruent to 1 or 2 modulo 4; or, primes of form x^2+y^2

A002313 - Primes congruent to 1 or 2 modulo 4; or, primes of form x^2+y^2

2, 5, 13, 17, 29, 37, 41, 53, …

In 1632, Albert Girard observed that all primes congruent to 1 modulo 4 (meaning that when divided by 4, there is a remainder of 1) could be represented as the sum of two squares. For instance, 17 = 4^{2} + 1^{2}. He wasn’t able to prove it, but eight years later, Pierre de Fermat claimed that he had. Fermat never published his proof, and it wasn’t until more than a century later (in 1749) that ~~he~~ Euler provided a full proof in a letter to Christian Goldbach.

The Eight Queens Puzzle is a challenge proposed in the mid-19th century by chess player Max Bezzel. The puzzle is this: Is it possible the place 8 queens on an 8x8 chess board in such a way that none of them can attack each other. Queens can move any number of spaces in any of the eight orthogonal directions, so no two pieces could share the same row, column, or diagonal. The answer is yes — individual solutions are easy, but Franz Nauck later showed how to build solutions algorithmically, and expanded the puzzle to *n* queens on an *n*x*n* board.

For *n*-Queens puzzle where *n* belongs to the above sequence (*n* is prime and *n* = 4*m* + 1), the two squares can be used to generate a solution. Place a queen at the center. Place the next queen *x* spaces right and *y* spaces up, looping from top to bottom and right to left. Repeat until you have placed all of the queens.