# The magic of the primes

A mathematician, a physicist, and an engineer found themselves caught in an ancient anecdote. Lacking a chemist to brew them an anecdote antidote, they fell to arguing over which of them was to be the butt of the joke ... when suddenly the physicist and the engineer disappeared! Between the spots where they'd been standing, a magician stood glaring at the mathematician.

"Long have those of thy profession sought to ridicule my kin," he said menacingly. "Wherefore then, now that thou art in my power, should I release thee? I shall trap thee in unamusing tales with thy fellow scientists for ever."

"As I see you are a magician," the mathematician began, "will a magic square enable me to avert your power?"

The magician scoffed. "What is thy field of expertise within that arid wasteland, Mathematics?"

"Number theory," the unperturbed1 mathematician replied.

"Ha! Those fools who seek to discover pattern among the prime numbers! In that case, I challenge thee to find a $2015\times2015$ magic square all of whose entries are prime. If thou canst achieve this feat, I shall release thee unharmed; otherwise, thou art my slave for ever!"

Can the mathematician succeed? Give a proof either that such a magic square exists or that it cannot exist. Unlike the unfortunate mathematician, you don't actually need to construct it!

1Well, of course he was unperturbed. Perturbation theory is a branch of analysis, not number theory!

• If the entries don't have to be unique... Aug 20, 2015 at 15:29
• I believe that unique elements is a prerequisite of a magic square. Aug 20, 2015 at 15:30
• I agree that it would be nice to mention, even if it's a safe assumption. Aug 20, 2015 at 15:38
• @Roland ... or even Dickson's? But seriously, the mathematician will probably count himself lucky to get away alive (and it'll take him long enough!) Aug 20, 2015 at 16:34
• +1 for the metahumor, because I never metahumor I didn't like! Aug 20, 2015 at 18:02

The mathematician's task is

possible.

Proof:

By the Green-Tao Theorem, there exists a sequence of $2015^2$ primes which form an arithmetic progression. This arithmetic progression can be arranged into an order 2015 magic square using the usual method. Namely, place the lowest prime in the middle of the top row. For each prime placed, the next prime will be placed one square northeast of it (wrapping around at the borders), unless this is already filled, in which case it will be placed one square south.

• By "lowest prime", you must mean "lowest prime of the $2015^2$ chosen". My answer, which assumed the lowest is required, explains why this cannot be done. Aug 20, 2015 at 16:18
• This solution ends up being remarkably simple! Aug 20, 2015 at 17:21
• Well, a solution is possible, but he is still toast if he can not find (and write down) that solution. And given that the lowest known 26 element AP is of 18 digits I would say, he should stop trying. Aug 20, 2015 at 18:24
• @randal'thor Do you know of a solution that doesn't use the Green-Tao theorem? It's solid as a solution, but I'd like the puzzle to not require such high-powered machinery.
– xnor
Aug 21, 2015 at 3:37
• @Anachor That is indeed the catch! But maybe it's the engineer and not the mathematician who's toast in the end? Aug 21, 2015 at 9:35

Assuming the mathematician must use all primes in ascending order, as I gathered from a quick magic square search:

It cannot be done. The mathematician must place the number $2$ in a square. With 2014 other primes, all odd, its row and column must add up to an even number. All columns and rows without $2$ will add up to an odd number.

• Your logic is correct, but your assumption is false. Where does it say in the OP that the first $2015^2$ primes must be used?? Aug 20, 2015 at 15:36
• Ah, it appears the definition I'm reading is what Wikipedia calls a normal magic square. My search result said that integers $1$ to $n^2$ must be used. Since the magician told us to use primes, I interpreted it as the first to $n^2th$ primes. Apologies. Aug 20, 2015 at 15:55
• I did the exact same thing @Roland. I've never heard of a magic square and the cursory google result says the numbers in a n x n square must be the set [1,n^2]. The second result down explains that this is not necessarily the case though Aug 20, 2015 at 16:00
• Shorter version: there aren't $2015^2$ primes in the first $2015^2$ numbers. ;) Once they are using primes, clearly a normal magic square is right out.
– Yakk
Aug 20, 2015 at 17:12