显然每个筹码都需要前进$n+1$格才能到达目标位置，因此所有的筹码总共需要移动$2n(n+1)$格。
而跳跃只会发生红蓝筹码的相对位置互换时，因此一共有$n^2$次互换，从而总移动次数是$M(n)=2n(n+1)-n^2=n^2+2n$。
若该数是三角数，则存在$m\in\mathbb N$，使得
$$n^2+2n=\frac{m(m+1)}{2},$$
简单变形后即得Pell方程
$$(2m+1)^2-8(n+1)^2=-7.$$
按照例如第66题和第137题的解法，该方程的解是其基本解$(1,1)$和$(5,2)$与标准Pell方程$x^2-8y^2=1$的通解$(a_k,b_k)$按以下方式复合而成：
$$\begin{cases}x_{k}=x^*a_k+8y^*b_k, \\ y_k=y^*a_k+x^*b_k,\end{cases}$$
其中$(x^*,y^*)$是$(1,1)$或$(5,2)$。而$(a_k,b_k)$也可以类似地由
$$\begin{cases} a_{k+1}=3a_k+8b_k, \\ b_{k+1}=a_k+3b_k,\end{cases}$$
以及初值$a_1=3, b_1=1$计算而得。最终结果是$2470433131948040$。
a,b=3,1
r=[1]
while len(r) < 40:
for x,y in ((a+8*b,b+a),(5*a+16*b,5*b+2*a)):
if x%2==1:
r.append(y-1)
a,b=3*a+8*b,a+3*b
print sum(r[:40])
|
