Project Euler: Hexagonal tile differences
Go to Problem
Summary
It’s easy since I spent only 2+ hours. So try it before read my thought and you’ll have some fun.
- 1, 2, 8, 19 are the first 4 valid numbers.
- Consider each ring as 6 vertex and many other nodes in edge.
- Consider the series of vertice in direction 2, It’s 1, 2, 8, 20, ….
-
We know every number in a ring if we know it first vertex in the previous series. For example, the 3rd rind is:
-
Every node has 2 neighbors which are in the same ring. For example, 10 and 12 are neighbors of 11, their difference is always 1 (10 - 11, and 12 - 11) which are not primes. So except the first and last node in a ring, all nodes have at least 2 neighbors are not primes.
-
Consider all vertice in 3, 5, 7 directions. The series in each direction is interleave with odd and even number, for example: [3, 10, 23, 42, …] is [odd, even, odd, even, …]. Now let’s check 10, it’s next vertex neighbor is 23, which is odd, and neighbors of 23 in it’s ring is 22, 24, which are evens, then 10 has 2 more difference which are not primes (even - even). We can find the same property in odd vertex. All of them have ate least 4 non-primes neighbors (2 + property 4).
-
Consider all vertice in 4 and 6 directions. They are all even which provide 2 non-prime neighbor difference.
-
Consider all edge nodes. They all have 2 neighbors from both outer and inner rings. For example, 11 has [3, 4] and [24, 25], 2 even and 2 odd which means no matter the node is even or odd, it’s 4 neighbors give it at least 2 more non-prime neighbor difference.
-
So, all we have to do is checking vertex in direction 2 (2, 8, 20, 38, ….) and the last node in each ring (7, 19, 37, 61, …).
Code in Python
from sympy import isprime
# 1, 2, 8, 19
L = 2000
T = 4
S = [1, 2, 8, 19]
a = 8
b = 20
c = 38
d = 62
k = 3
while len(S) < L :
# first and last
if isprime(abs(b - c + 1)) :
if isprime(abs(b - c - 1)) and isprime(abs(b - d + 1)):
S.append(b)
if isprime(abs(c - 1 - a)) and isprime(abs(c - d + 1)) :
S.append(c - 1)
a, b, c, d = b, c, d, d + d - c + 6
print(S[L - 1])