Thought Process

Very fun problem! I worked through this problem by first trying to find the neighbours of a given number and then I was able to prove that the maximum of PD(n) is 3 and I was able to prove exactly when this will happen.

Firstly, I categorize each number by which level its on, i, then each level can be broken down into 6 compartments of size i (the sides of the hexagon), k, and then it's position in that compartment, 0 <= r < i.

Here's an example of the breakdown:

1. Level 0: [1]

2. Level 1: [2, 3, 4, 5, 6, 7]

   1. Compartments are [2], [3], [4], [5], [6], [7]

3. Level 2: [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

   1. Compartments are [8, 9], [10, 11], [12, 13], [14, 15], [16, 17], [18, 19]

4. Level 3: [20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37]

   1. Compartments are [20, 21, 22], [23, 24, 25], [26, 27, 28], [29, 30, 31], [32, 33, 34], [35, 36, 37]

Then every number can be represented by a tuple (i, k, r). For example 21 = (3, 0, 1), 37 = (3, 5, 2).

From here it is just simple to find the neighbours of any number by splitting into case work. Suppose our given number n = (i, k, r), define v = 1 + 6*(iC2) where iC2 means i choose 2, then it is clear that n = v + ik + r + 1. 

I give the final answer only as the working is simple tedious calculations. note that these are only true for level 2 onwards, but it doesn't matter since we easily check that PD(1) = PD(2) = 3 so the first 2 levels are done.

1. Any number of the form (i, 0, 0) or (i, 5, i - 1) that is the first and last element of a level have special cases

   1. n = (i, 0, 0), that is n = v + 1:

      1. It's neighbours are: [v - 6i - 5, v + 2, v + 6i, v + 6i + 1, v + 6i + 2, v + 12i + 6]

      2. Hence the differences are: [1, 6i - 6, 6i - 1, 6i, 6i + 1, 12i + 5] now it is clear that 1, 6i - 6, 6i are never prime. Hence for this case we require 6i - 1, 6i + 1, 12i + 5 to all be prime, then PD(n) = 3

   2. If n = (i, 5, i - 1), that is n = v + 5i + (i - 1) + 1 = v + 6i

      1. It's neighbours are: [v + 6i - 1, v + 1, v, v + 12i + 5, v + 12i + 6, v - 6i + 7]

      2. Hence the differences are: [1, 6i - 1, 6i, 6i + 5, 6i + 6, 12i - 7] now it is clear that 1, 6i - 6, 6i are never prime. Hence for this case we require 6i - 1, 6i + 5, 12i - 7 to all be prime, then PD(n) = 3

2. Otherwise we split into 2 cases:

   1. We are on a corner, that is (i, k, 0), that is n = v + ik + 1.

      1. It's neighbours are: [v + ik, v + ik + 2, v + 6i + (i + 1)k, v + 6i + (i + 1)k + 1, v + 6i + (i + 1)k + 2, v - 6(i - 1) + (i - 1)k + 1]

      2. Hence the differences are: [1, 1, 6i + k - 1, 6i + k, 6i + k + 1, 6(i - 1) + k]. Now if k is even then 6i + 8, 6(i - 1) + k are both even and hence non prime, but if k is odd then 6i + k - 1, 6i + k + 1 are even and hence not prime, therefore in this case PD(n) < 3. This means we don't even need to consider this case.

   2. We are not on a corner, that is (i, k, r), r is not 0, that is n = v + ik + r + 1

      1. It's neighbours are: [v + ik, v + ik + 2, v - 6(i - 1) + (i - 1)k + r, v - 6(i - 1) + (i - 1)k + r + 1, v + 6i + (i + 1)k + r + 2, v + 6i+ (i - 1)k + r + 1]

      2. Hence the differences are: [1, 1, 6(i - 1) + k + 1, 6(i - 1) + k, 6i + k + 1, 6i + k]. Now if k is even then 6(i - 1) + k, 6i + k are both even and hence non prime, but if k is odd then 6i + k + 1, 6(i - 1) + k + 1 are even and hence not prime, therefore in this case PD(n) < 3. This means we don't even need to consider this case.

This is a full proof that the maximum value of PD(n) is 3, furthermore it shows that we only need to consider the first and last elements of a row! 

Now the rest is simple, for each row just test if the required values are prime, if they all are then we have found an n such that PD(n) = 3.