# Ulam Spiral

Standard

Some of you may know what Ulam’s spiral is (I am not describing what it is because the present Wikipedia entry is awesome, though I mentioned it earlier also). When I first read about it, I thought that it is just a coincidence and is a useless observation. But a few days ago while reading an article by Yuri Matiyasevich, I came to know about the importance of this observation. (Though just now I realised that Wikipedia article describes is clearly, so in this post I just want to re-write that idea.)

It’s an open problem in number theory to find a non-linear, non-constant polynomial which can take prime values infinitely many times. There are some conjectures about the conditions to be satisfied by such polynomials but very little progress has been made in this direction. This is a place where Ulam’s spiral raises some hope. In Ulam spiral, the prime numbers tend to create longish chain formations along the diagonals. And the numbers on some diagonals represent the values of some quadratic polynomial with integer coefficients.

Ulam spiral consists of the numbers between 1 and 400, in a square spiral. All the prime numbers are highlighted. ( Ulam Spiral by SplatBang)

Surprisingly, this pattern continues for large numbers. A point to be noted is that this pattern is a feature of spirals not necessarily begin with 1. For examples, the values of the polynomial $x^2+x+41$ form a diagonal pattern on a spiral beginning with 41.

# Popular-Lonely primes understood

Standard

While reading standup mathematician Matt Parker‘s book Things to Make and do in Fourth Dimension, I found answer (on pp. 146) to the question I raised 7 months ago.

When the grid happens to be a multiple of 6 wide, suddenly all primes snap into dead-straight lines. All primes (except 2 and 3) are one more or less than a multiple of 6. (© Matt Parker, 2014)

He also proves the following surprising theorem:

The square of every prime number greater than 3 is one more than a multiple of 24.

Let $p$ be an odd prime not equal to 3. Now we subtract one from the square of this prime number. Therefore, we wish to prove that $p^2-1=(p-1)(p+1)$ is a multiple of 24.

Note that, $p^2-1$ is a product of two even numbers. In particular, one of these two even numbers must be a multiple of 4, as they are consecutive even numbers and every other even number is divisible by 4. Hence we conclude that $p^2-1$ is divisible by 8.

Observe that exactly one of three consecutive numbers, $p-1,p,p+1$ must be divisible by 3. Since $p$ is an odd prime different from 3, one of $p-1$ or $p+1$ must be divisible by 3. Hence we conclude that $p^2-1$ is divisible by 3.

Combining both the conclusions made above, we complete proof of our statement (since 2 and 3 are coprime).

Edit[19 April 2017]: Today I discovered that this theorem is exercise 68 in “The USSR Olympiad Problem Book“.

# Primes: popular and lonely

Standard

ulam While doodling in class, I made a 10 x 10 grid and filled it with numbers from 1 to 100. The motivations behind 10 x 10 grid was human bias towards the number 10.

Then inspired by Ulam Spiral, I started creating paths (allowing diagonal, horizontal and vertical moves) starting from the smallest number. Following paths emerged:

• 2→ 3 →13 → 23
• 2 → 11
• 7 → 17
• 19 → 29
• 31 → 41
• 37 → 47
• 43 → 53
• 61 → 71
• 73 → 83
• 79 → 89

So, longest path is of length 4 and others are of length 2.

The number 2 is special one here, since it leads to two paths. I will call such primes, with more than one paths, popular primes.

Now, 5, 59, 67 and 97 don’t have any prime number neighbour. I will call such primes, with no neighbour, lonely primes.

I hope to create other $b \times b$ grids filled with 1 to $b^2$ natural numbers written in base $b$. Then will try to identify such lonely and popular primes.