Project Euler 128: Which tiles in the hexagonal arrangement have prime differences with neighbours?

Project Euler 128: Which tiles in the hexagonal arrangement have prime differences with neighbours?

Written by on 22 December 2012

Topics: Project Euler

Problem 128 is a really interesting problem about prime numbers. It reads

A hexagonal tile with number 1 is surrounded by a ring of six hexagonal tiles, starting at “12 o’clock” and numbering the tiles 2 to 7 in an anti-clockwise direction.

New rings are added in the same fashion, with the next rings being numbered 8 to 19, 20 to 37, 38 to 61, and so on. The diagram below shows the first three rings.

By finding the difference between tile n and each its six neighbours we shall define PD(n) to be the number of those differences which are prime.

For example, working clockwise around tile 8 the differences are 12, 29, 11, 6, 1, and 13. So PD(8) = 3.

In the same way, the differences around tile 17 are 1, 17, 16, 1, 11, and 10, hence PD(17) = 2.

It can be shown that the maximum value of PD(n) is 3.

If all of the tiles for which PD(n) = 3 are listed in ascending order to form a sequence, the 10th tile would be 271.

Find the 2000th tile in this sequence.

My initial thought was that it will kill me if I have to go through every number and check if they fulfill the criteria, so I started looking for patterns such that I could eliminate some numbers that I did not have to check.  Rather quickly I realized that we can split each ring into three cases.  The fist case is the sides of the hexagon. In the outmost ring of the hexagon above the sides  includes 21 and 22, 24 and  25, 27 and 28, 30 and 21,  33 and 34, and not least 36. The second case are the corners of the hexagon. So to continues with the outer ring those are 23, 26, 29, 32 and 35.

As you migth have spotted now I have not included 20 and 37. That is the last case I will deal with, since those are special.

The sides

First I looked at the sides. No matter where in the hexagon the number s, it will have 6 neighbours. Two of those are s+1 and s-1. Thus the difference will be 1, which is not a prime. So that leaves us with 4 numbers to check. If you are on a side. Two of these numbers will be consecutive numbers from the outer ring, and two of those will be consecutive numbers from the inner ring. Thus one of each pair will be even and cannot be a prime. Thus is s is on a sides of a hexagon, it can at max have two prime neighbours.

The corners

If we look at the corners in ring n, then they can be given an index where 0 is the special case.

In this case the difference to the corner tile inside is that you have to move a whole length of the ring, which is equivalent to 6n + r, and the differences to the corner in the outer ring is 6n + 6 + r. You can check in the figure. The two other tiles in the outer ring have a difference of 6n + 5 + r and 6n + 7 + r.

So if we check for each of the case of n and r odd then we get

n even, r even

6n + r = even
6n + 6 + r = even
6n + 5 + r = odd
6n + 7 + r = odd

So PD(n) is maximum 2

n even, r odd

6n + r = odd
6n + 6 + r = odd
6n + 5 + r = even
6n + 7 + r = even

So PD(n) is maximum 2

n odd, r even

6n + r = odd
6n + 6 + r = odd
6n + 5 + r = even
6n + 7 + r = even

So PD(n) is maximum 2

n odd, r odd

6n + r = odd
6n + 6 + r = odd
6n + 5 + r = even
6n + 7 + r = even

So PD(n) is maximum 2

Therefore corners cannot be candidates either. That leaves us with the last case.

Start and End of the ring

I haven’t been able to rule out the start and end of each ring, and therefore we have to code to check if these have PD(s) = 3

If we look at 8, we have to check the places with 21, 37 and 19. Since the places of 2 and 20 will always have an even difference, and the place of 9 will always have a difference of 1.

That means we have to check if 6n – 1, 6n +1 and 12n + 5 are primes. In that case 8 will be a prime.

Same thing goes for 19, where we need to check the place of 2, 8 and 36. Which in general can be written as ,  6n +5, 6n – 1 and,  12n – 7. However this does not hold for the case of 7. However, checking that by hand shows that out of 12, 5, 6, 1, 10 and 11 only 2 of them are primes. So we can disregard those. On the other hand 1 is actually fulfilling the requirements.

The number itself can be calculated based on the formula for a series of integers we want to add up. As we went through in problem 6, since the number P as a function of n can be expressed as

P(n)  = 6n + P(n-1) = 6n + 6(n-1) + P(n-2)…. = 6(n + (n-1) + (n-2)….) = 6(1 + n)n/2 = 3n2 + 3n

However, since we actually get an increase of 6 when n goes from 1 to 2, we need to change the series to use n-1 and offset it by 2. So we get P(n) = 3n2 – 3n + 2

For the series in the end of each ring, we can calculate it as the first in the next ring minus 1, so that gives us  P(n) = 3(n+1)2 – 3(n+1) +1 = 3n2  + 6n + 3- 3n – 3 + 1 + = 3n2  + 3n  + 1

With those formulas we are ready to code a loop that will give us the answer

int count = 1;
int limit = 2000;
long n = 0;
long number = 0;</pre>
while (count < limit) {
    n++;
    if (IsPrime(6 * n - 1) && IsPrime(6 * n + 1) && IsPrime(12 * n + 5)) {
        count++;
        number = (3 * n * n - 3*n + 2);
        if (count >= limit) break;
    }
    if (IsPrime(6 * n + 5) && IsPrime(6 * n - 1) && IsPrime(12 * n - 7) && n != 1) {
        count++;
        number = (3 * n * n + 3*n + 1);
    }
}

With a IsPrime implementation as you can see in the source code, this gives us the answer in 60ms. The answer is the rather large number

The 2000th number is 14516824220

I am pretty glad that I followed my intuition not to start checking from one end.

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.