欧拉计划：45（或更多 Python 发电机）

Question

这是来自 Project Euler 的 problem 45：

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

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

Pentagonal Pn = n x (3n−1) / 2 1, 5, 12, 22, 35, ... Hexagonal Hn = n x (2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

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

这是我的代码：

def triangle_generator():
    n = 1
    while True:
        t = n * (n + 1) // 2
        yield t
        n += 1


def pentagonal_generator():
    n = 1
    while True:
        p = n * ((3 * n) - 1) // 2
        yield p
        n += 1


def hexagonal_generator():
    n = 1
    while True:
        h = n * ((2 * n) - 1)
        yield h
        n += 1


def tph():
    tg = triangle_generator()
    pg = pentagonal_generator()
    hg = hexagonal_generator()

    tg_temp_list = []
    pg_temp_list = []
    while True:
        h = next(hg)
        t = 0
        p = 0
        while t < h:
            t = next(tg)
            tg_temp_list.append(t)
        while p < h:
            p = next(pg)
            pg_temp_list.append(p)
        if h in tg_temp_list and h in pg_temp_list:
            print("Found! {}".format(h))
        else:
            tg_temp_list = tg_temp_list[-2:]
            pg_temp_list = pg_temp_list[-2:]

因此，生成了一个六边形数字，然后填充了两个临时列表——一个来自 triangle_generator()，一个来自 pentagonal_generator()。然后，检查生成的六边形数是否在这两个列表中。如果不是，则清空临时列表，除最后一个元素外，产生另一个六边形数字，无限重复整个过程。

我的问题：（假设撇开纯数学方法）Python 是否提供更方便的（Pythonic）方法来实现 tph() 函数？

Answer 1

这个问题可以通过计算和评估下一个三角形、五边形和六边形数字来解决，就像您已经做过的那样，但欧拉计划问题的主要设计目的是巧妙地结合数学和编程。从wiki，我们有每个六角数都是一个三角形数。

所以我们只需要遍历六边形数，找到一个也是五边形数就停止！通过一些简单的数学，我们发现一个数是五角形的当且仅当 (sqrt(24 * candidate_value + 1) + 1) / 6 是整数。

那么，问题就简化为下面的代码：

import math


i = 144

while True:
    hexagonal = i * (2 * i - 1)

    if ((math.sqrt(24 * hexagonal + 1) + 1) / 6).is_integer():
        print("Found it! The next occurence is {}".format(hexagonal))
        break
    i += 1

Answer 2

也许更优雅，但不确定效率更高。但想法是，如果您可以合并迭代器，其中每次弹出时返回最低 #，即优先队列，那么您的代码可以更清晰。

import heapq

def tph():
    tg = triangle_generator()
    pg = pentagonal_generator()
    hg = hexagonal_generator()
    count = 0
    last_n = 0
    for n in heapq.merge(tg, pg, hg):
        if n == last_n:
            count += 1
        else:
            count = 1

        if count == 3:
            print(n)

        last_n = n

欧拉计划：45（或更多 Python 发电机）

Project Euler: 45 (or More Python Generators)

python

generator

python-3.x