Project Euler #45：我的逻辑哪里错了？

Question

这是来自Project Euler的第45题：

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle T_(n)=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal P_(n)=n(3n−1)/2 1, 5, 12, 22, 35, ...

Hexagonal H_(n)=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T_(285) = P_(165) = H_(143) = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

[ http://projecteuler.net/problem=45 ]

为了找到答案，我用了三个变量，并把这些方程都设为A。

n(n + 1)/2 = a(3a - 1)/2 = b(2b - 1) = A

A是三个函数在n、a、b的值上重合的那个数字。

结果我们得到了三个包含n和A的方程。用二次公式解这些方程，我们得到了三个方程。

 (-1 + sqrt(1 + 8*A ) )/2
 ( 1 + sqrt(1 + 24*A) )/6
 ( 1 + sqrt(1 + 8*A ) )/4

我的思路是测试A的值，看这三个方程能否给出一个自然数的正值。目前为止，它在40755这个数字上是正确的，但在一千万以内找不到下一个。

(编辑)：这是我用Python写的代码

from math import *

i=10000000
while(1):
    i = i + 1
    if(((-1+sqrt(1+8*i))/2).is_integer()):
        if(((1+sqrt(1+24*i))/6).is_integer()):
            if(((1+sqrt(1+8*i))/4).is_integer()):
                print i
                break

我的逻辑哪里出错了？（抱歉涉及了一些数学内容。 :)）

Answer 1

实现这个功能最简单的方法是为每个序列创建3个生成器，然后把它们放到

heapq.merge

里。如果你发现有3个相同的连续键，那就找到了答案。最简单的方法是使用

itertools.groupby

Answer 2

给定以下几点：

• 所有的六边形数也是三角形数
• heapq.merge 对于当前的任务非常有用（高效且能减少代码量）

那么这个：

import heapq

def hexagonals():
    "Simplified generation of hexagonals"
    n= 1
    dn= 5
    while 1:
        yield n
        n+= dn
        dn+= 4

def pentagonals():
    n= 1
    dn= 4
    while 1:
        yield n
        n+= dn
        dn+= 3

def main():
    last_n= 0
    for n in heapq.merge(hexagonals(), pentagonals()):
        if n == last_n:
            print n
        last_n= n

main()

几乎瞬间就能得到1、40755和你想要的其他数字，几秒钟后还会得到一个14位的数字。当你觉得电用得差不多了，就可以停止程序。

如果你想避免使用“难懂”的库，可以使用下面的 main（基本上是同样的算法，只是写得更清楚）：

def main():
    hexagonal= hexagonals()
    pentagonal= pentagonals()
    h= next(hexagonal)
    p= next(pentagonal)
    while 1:
        while p < h:
            p= next(pentagonal)
        if p == h:
            print p
        h= next(hexagonal)

时间看起来差不多，但我没有去测量具体的时间。

Answer 3

你的逻辑没有错，只是你的程序运行得比较慢（我估计它大约需要一个小时才能给出答案）。我知道答案是什么，并且通过把i设置为稍微小一点的值来测试了你的程序。结果你的程序立刻就给出了正确的答案。

听听ypercube的建议吧。