题目128：六角形结构中哪些相邻块的差是质数？
本帖最后由 永恒的蓝色梦想 于 2020-6-28 08:37 编辑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爱好者（结交同行！） 坏小子 发表于 2016-8-23 20:21
我来说下思路，用python来实现。
每个砖块有三种表示方法
你讲得太复杂了，根据我的计算，六边形的周围一圈与本身的差是质数的数，只可能是每圈开始的那个数，比如2,8,20,38等，或者是每圈结束的那个数，比如7,19,37等。
那么只要分2种情况分别统计，纯python代码，用numpy和numba加速，2秒钟可以出答案。
from numba import jit
import numpy as np
@jit
def gen_primes(limit):
primes = np.ones(limit, dtype='int8')
primes, primes = 0, 0
for i,prime in enumerate(primes):
if prime:
for j in range(i*i, limit, i):
primes = 0
return primes
@jit
def solve(num, limit=1000000):
primes = gen_primes(limit)
count = 0
m = 0
for n in range(1, limit//12):
if primes and primes and primes:
count += 1
if count == num:
m = 3 * n * n - 3*n + 2
break
if primes and primes and primes:
count += 1
if count == num:
m = 3 * n * n + 3*n + 1
break
return m
print(solve(2000))
14516824220
jerryxjr1220 发表于 2017-7-19 10:27
你讲得太复杂了，根据我的计算，六边形的周围一圈与本身的差是质数的数，只可能是每圈开始的那个数，比如 ...
{:10_257:}WOW，感谢，只是我数论比较菜不知道怎么证明这个结论，不过能得到这个规律算起来也就容易多了
页:
[1]