题目128：六角形结构中哪些相邻块的差是质数？

欧拉计划

Hexagonal tile differences

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 of 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.

题目：

编号为 1 的六角形砖块被 6 个六角形砖块形成的环所环绕，从 12 点的位置开始，逆时针方向编号 2 到 7。

用同样的方法构造新的环，编号从 8 到 19，20 到 37，38 到 61，等等。下图显示了前三层环。

通过观察编号为 n 的砖块以及它周围的六个相邻砖块，我们定义 PD(n) 为编号与 n 之差为质数的砖块的个数。

例如，以 8 号砖为中心顺时针来看，差分别是：12，29，11，6，1 和 13，所以 PD(8)=3。

类似的，17 号砖的邻居与它的差是：1，17，16，1，11，10，所以 PD(17)=2。

可证明 PD(n) 的最大值可以取到 3。

如果所有 PD(n)=3 的砖块按照升序排列，我们得到一个序列，这个序列中的第 10 个的编号是 271。

找出这个序列中第 2000 个的编号。

坏小子

我来说下思路，用python来实现。

每个砖块有三种表示方法

方法一，编号

方法二，把每个环抽象成一个六边形，表示为第几环第几边上的第几个点

方法三，把每块砖与其中心点建立一一映射，取两个向量，模为1，夹角为120度（60度也可以），建立一个非直角坐标系，那么每个点都可以用一个二维整数坐标来表示。

写两个函数，实现方法一与方法二的互换。
写两个函数，实现方法三与方法二的互换。

方法二到方法一直接用公式就行了，方法一到方法二需要列个不等式间接求出公式（会用到天花板和地板函数中的某一个）

方法三到方法二，把坐标换成极坐标，由到原点的距离求出处于第几环，由角度求出位于哪条边（或者刚好在顶点），再根据与该边的某个顶点的距离，求出是第几个点。
方法二到方法三，学过高中数学向量那章的同学就不需要我多说了吧。

那么，我们已经能灵活地在任意两种表示方法之间转换了，公式自己推吧。

用方法三表示的时候，可以很方便地求出该点周围的六个点，再转为方法一表示，OK，剩下的工作就不用我多说了，人生苦短，我用python。

另，有同样在学习python的同学欢迎加我企鹅782878448一起交流学习，本人大三业余程序员兼ACG爱好者（结交同行！）

jerryxjr1220

坏小子 发表于 2016-8-23 20:21
我来说下思路，用python来实现。

每个砖块有三种表示方法

你讲得太复杂了，根据我的计算，六边形的周围一圈与本身的差是质数的数，只可能是每圈开始的那个数，比如2,8,20,38等，或者是每圈结束的那个数，比如7,19,37等。
那么只要分2种情况分别统计，纯python代码，用numpy和numba加速，2秒钟可以出答案。

1. from numba import jit
   
2. import numpy as np
   
3. @jit
   
4. def gen_primes(limit):
   
5.         primes = np.ones(limit, dtype='int8')
   
6.         primes[0], primes[1] = 0, 0
   
7.         for i,prime in enumerate(primes):
   
8.                 if prime:
   
9.                         for j in range(i*i, limit, i):
   
10.                                 primes[j] = 0
    
11.         return primes
    
12. @jit
    
13. def solve(num, limit=1000000):
    
14.         primes = gen_primes(limit)
    
15.         count = 0
    
16.         m = 0
    
17.         for n in range(1, limit//12):
    
18.                 if primes[6*n-1] and primes[6*n+1] and primes[12*n+5]:
    
19.                         count += 1
    
20.                         if count == num:
    
21.                                 m = 3 * n * n - 3*n + 2
    
22.                                 break
    
23.                 if primes[6*n-1] and primes[6*n+5] and primes[12*n-7]:
    
24.                         count += 1
    
25.                         if count == num:
    
26.                                 m = 3 * n * n + 3*n + 1
    
27.                                 break
    
28.         return m
    
29. print(solve(2000))

复制代码

14516824220
[Finished in 2.6s]

坏小子

jerryxjr1220 发表于 2017-7-19 10:27
你讲得太复杂了，根据我的计算，六边形的周围一圈与本身的差是质数的数，只可能是每圈开始的那个数，比如 ...

WOW，感谢，只是我数论比较菜不知道怎么证明这个结论，不过能得到这个规律算起来也就容易多了