0128 六边形平铺差
* * * *
拉格朗日计划
* * * *
六边形平铺差

标有数1的六边形被另外六个六边形包围,这些地砖从12点钟方向(正上方)开始按逆时针顺序依次标记为2至7。

沿着这一图形的外侧边界继续添加新的六边形使之包围原图形,并按同样的规则依次标记数字8至19、20至37、38至61等等以此类推。下图显示了前三圈所构成的图形。



考虑标有n的六边形与其周围六个六边形数字之差的绝对值,并令$PD(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$的n从小到大排列,那么其中第10个数是271,求其中第2000个数。

本题难度:



解答

为叙述方便,称标有1的六边形为第一层,标有2到7的六边形为第二层,标有8到19的六边形为第三层,以此类推。 显然从第二层开始每层有$6(n-1)$个六边形。

可以看出前两层中唯一满足$PD(n)=3$的是$PD(1)=P(2)=3$。

从第三层开始考虑,注意到每层除了首个和最后一个六边形(即该层中数字最小和最大的两个六边形)外,其他六边形上的数n都与同一层中的n+1和n-1相邻(从而差的绝对值都为1),且可以按照其它四个相邻六边形的组成分为两组:

(1) 与一个上一层的六边形和三个下一层的、数字连续的六边形相邻。

(2) 分别与两个上一层的和两个下一层的、数字各自连续的六边形相邻。

对(1)而言, 设当前数是n,上一层中与之相邻的六边形上的数是a,下一层中与之相邻的六边形上的数分别是b-1、b、b+1。

若n-a是偶数,则b-1-n、b-n、b+1-n中至少还有一个偶数,从而$PD(n)\le 2$。

若n-a是奇数,则b-n也是奇数,从而b-1-n和b+1-n都是偶数,亦得$PD(n)\le 2$。

对(2)而言,设当前数是n,上一层中与之相邻的六边形上的数分别是a、a+1,下一层中与之相邻的六边形上的数分别是b、b+1。

那么显然n-a和n-a-1中有一个偶数,b-n、b+1-n中也有一个偶数,从而也有$PD(n)\le 2$。

因此只需考虑每层的首个和末个六边形, 设第n层首个六边形上的数是$x_n$,末个六边形上的数是$y_n=x_{n+1}-1$,则

$$x_3=8, \quad x_n=x_{n-1}+6(n-2)=2+3(n-1)(n-2), \quad y_n=x_{n+1}-1=1+3n(n-1).$$ 显然$x_{n+1}-x_n$和$x_n-x_{n-1}$都是合数,而$x_n$与其下一个数之间相差1,因此只需检查它与另外三个相邻六边形上的数之差,即 \begin{align*}y_{n+1}-x_n&=x_{n+2}-1-x_n=x_{n+2}-x_{n+1}+x_{n+1}-x_n-1=6n+6(n-1)-1=12n-7, \\ y_n-x_n&=x_{n+1}-1-x_n=6(n-1)-1=6n-7, \\ x_{n+1}+1-x_n&=6(n-1)+1=6n-5, \end{align*} 类似地,对$y_n$也只需检查 \begin{align*}y_n-x_{n-1}&=12n-19,\\ y_n-x_{n}&=6n-7, \\ y_{n+1}-1-y_n&=x_{n+2}-1-1-(x_{n+1}-1)=6n-1, \end{align*} 这些序列中存在许多重复的项,因此综合考虑可以发现只需检验出以下四个序列中的素数 \begin{align*}a_n&=y_{n+1}-x_n=12n-7 \\ b_n&=y_n-x_n=6n-7 \\ c_n&=x_{n+1}+1-x_n=6n-5 \\ d_n&=y_{n+1}-1-y_n=6n-1 \end{align*} 若$a_n$、$b_n$、$c_n$都是素数,则$PD(x_n)=3$。

若$a_{n-1}$、$b_n$、$d_n$都是素数,则$PD(y_n)=3$。

由于只需检验特定形态的数的素性,且这些数可能较大,因此先估计一个上界(以下选用的是$10^8$),用筛法生成该上界平方根以内的全部素数(以下使用的是10000),再用常规的手段作素性检验。

结果是$14516824220$。

from functools import *
target=10000
d=[0]*target
n=2

while n < target:
    for i in range(n+n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

primeList=[k for k in range(2,target) if d[k]==0]

@cache
def isPrime(n):
    i=0
    while i < len(primeList) and primeList[i]*primeList[i]<=n and n%primeList[i]:
        i+=1
    return i>=len(primeList) or n%primeList[i]>0

c=2
r=2
while c < 2000:
    r+=1
    a,b=isPrime(12*r-7) and isPrime(6*r-7) and isPrime(6*r-5),isPrime(12*r-19) and isPrime(6*r-7) and isPrime(6*r-1)
    c=c+a+b

x,y=2+3*(r-1)*(r-2),1+3*r*(r-1)  

print(x if c==2001 else x*a+y*b)