Popular-Lonely primes understood

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 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 is a multiple of 24.

Note that, 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 is divisible by 8. 

Observe that exactly one of three consecutive numbers, must be divisible by 3. Since is an odd prime different from 3, one of or must be divisible by 3. Hence we conclude that 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“.

Cross Diagonal Cover – III

I found many counterexamples to my conjecture, like

• for Case 2 in 7 by 5 grid we have 12, 11 by 5 grid we have 19 and 15 by 5 grid we have 26 filled squares
• for Case 3 in 4 by 10 grid we have 10 filled squares

In a comment by grant93jr   following part of of my initial question, to determine the number of squares in grid that can be covered by crosses (x) by following Cross Diagonal Cover Algorithm, was proved:

Given m>n, whenever divides we have filled squares.

Examples of such grids are: 3 by 5, 4 by 7, 4 by 10, ….

Also in that comment it has been suggested that the algorithm terminates after steps where are natural numbers. It is certainly true, but I haven’t been able to use this idea for counting number of filled squares when does not divide since in that case some squares are filled twice.

There is another unexplained observation:

Why no filled square has more than 2 crosses?

Frustrated by so many unanswered questions I started colouring squares, so that number of times I visited a square is not visible. Since I really don’t care about how many times I visited  given square while counting the number of filled squares this may help in understanding the underlying symmetry.

Replacing cross (x) by any colour and applying Cross Diagonal Cover Algorithm

After observing above diagrams I suspect that my algorithm leads to a non-deterministic cellular automata.

So, the question which still remains to be answered is:

How many filled squares are there when   and does not divide ?

Examples of such grids are: 7 by 5, 11 by 5, 15 by 5 …

 

Primes: popular and lonely

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 grids filled with 1 to  natural numbers written in base . Then will try to identify such lonely and popular primes.

If you find this idea interesting, please help me to create such grids.