Solution:  1681. Which, as it turns out, is equal to 41².

This problem involves a diagram, so you might be wondering why a diagram isn’t included with this solution. It’s because the diagonal prime sequence gets ridiculously long, and the diagram would need to be very large. But there is a logical way of getting at the solution.

The sequence of numbers along the diagonal is 41, 43, 47, 53, 61, 71, 83, …, and the differences between consecutive numbers in this sequence are 2, 4, 6, 8, 10, 12, …. The pattern continues in this manner, each time adding two more than was added previously. The list below shows all the numbers along the diagonal up to 1681, the first number in the list that is not prime.

Proving that all the numbers in the list less than 1681 are prime requires showing that each number has no factors other than 1 and itself. In other words, we have to show that no integer less than the square root of the number divides evenly into the number. Doing this requires a lot of calculation, but a spreadsheet can be used to perform the calculations.

Alternatively, if you remember that the differences between successive square numbers, starting with 1, are 3, 5, 7, 9, and so on, it is not surprising that the diagonal elements of our sequence can also be described using squares — that is, with a quadratic expression. Specifically, the values along the diagonal are the values of the expression x² – x + 41, for integer values of x. This expression goes all the way back to Leonhard Euler and has the remarkable property that it produces primes for the first 40 positive integers. Obviously, the expression yields a composite number when x = 41, because each of the individual terms is divisible by 41. So 41² = 1681 is the answer we are looking for.