OFFSET
1,2
COMMENTS
A hexagonal tile with number 1 is surrounded by a ring of six hexagonal tiles, starting on the right and numbering the tiles 2 to 7 in a counterclockwise direction. New rings are added in the same fashion, with the next rings being numbered 8 to 19, 20 to 37, and so on (see the illustration below). By finding the difference between tile n and each of its six neighbors we shall define PD(n) to be the number of those differences which are prime. For example, working counter-clockwise around tile 8 the differences are 12, 13, 1, 6, 11, and 29. So PD(8)=3. In the same way, the differences around tile 17 are 1, 10, 11, 1, 16, and 17, hence PD(17) = 2. It can be shown that the maximum value of PD(n) is 3. This sequence lists all tiles for which PD(n)=3 in ascending order.
It can be shown that only the first and last tile of every ring need to be considered.
LINKS
Antoine Mathys, Table of n, a(n) for n = 1..10000
Project Euler, Problem 128 - Hexagonal Tile Differences.
EXAMPLE
For tile 1, the differences are 1,2,3,4,5,6, thus PD(1)=3 and a(1)=1.
For tile 2, the differences are 6,7,1,1,5,17, thus PD(2)=3 and a(2)=2.
For tile 3, the differences are 6,7,8,1,2,1, thus PD(3)=2 and 3 is not in the list.
Similarly, we see that PD(4)=2, PD(5)=0, PD(6)=2, PD(7)=2, and PD(8)=3. Thus the next term is a(3)=8.
26--25--24--23
/ \
27 12--11--10 22
/ / \ \
28 13 4---3 9 21
/ / / \ \ \
29 14 5 1 2 8 20
\ \ \ / / /
30 15 6---7 19 37
\ \ / /
31 16--17--18 36
\ /
32---33--34--35
.
PROG
(C++)
#include <iostream>
bool is_prime (long n)
{
if (n < 2) return false;
if ((n == 2) || (n == 3)) return true;
if ((n % 6 != 1) && (n % 6 != 5)) return false;
for (long x = 1; (6 * x - 1) * (6 * x - 1) <= n; x++) {
if (n % (6 * x - 1) == 0) return false;
if ((6 * x + 1) * (6 * x + 1) > n) break;
if (n % (6 * x + 1) == 0) return false;
}
return true;
}
int main ()
{
constexpr long MAX_INDEX = 10000;
if (MAX_INDEX >= 1) std::cout << "1 1\n";
if (MAX_INDEX >= 2) std::cout << "2 2\n";
// We count the rings starting at 0 (the one containing 1)
for (long r = 2, index = 2; index < MAX_INDEX; r++) {
if (!is_prime (6 * r - 1)) continue;
// first cell
if (!is_prime (6 * r + 1)) goto LAST;
if (!is_prime (12 * r + 5)) goto LAST;
index++;
std::cout << index << " " << 3 * (r - 1) * r + 2 << '\n';
if (index == MAX_INDEX) break;
LAST:
// last cell
if (!is_prime (6 * r + 5)) continue;
if (!is_prime (12 * (r - 1) + 5)) continue;
index++;
std::cout << index << " " << 3 * r * (r + 1) + 1 << '\n';
}
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Antoine Mathys, Apr 22 2024
STATUS
approved