Project Euler p14增强性能

Question

我已经用以下代码完成了项目欧拉问题14：

def longest_Collatz_sequence():
    """
    returns longest Collatz
    sequence based on formula:
    n --> n/2 (n is even)
    n --> 3n + 1 (n is odd)
    """
    bestSequence = []
    lengthOfLongest = 0
    longestSequence = []
    for n in range(999999,1,-1):
        while n != 1:
            l = len(longestSequence)
            if n % 2 == 0:
                longestSequence.append(n)
                n /= 2
            elif n % 2 != 0:
                longestSequence.append(n)
                n = (n * 3) + 1
            if longestSequence[-1] == 2 and lengthOfLongest < l:  
                lengthOfLongest = l
                bestSequence = longestSequence[:]
                bestSequence.append(1)       
        longestSequence = []
    return bestSequence[0] 

将最长的Collatz数字序列从1000000降到2大约需要39秒。我想知道我是否可以缓存任何值来加速我的代码，以及如何在不获得无限循环的情况下从代码中删除if longestSequence[-1]==2，以及任何其他可以改进代码的方法。

为正整数集定义以下迭代序列：

n→n/2（n为偶数）n→3n 1（n为奇数）

使用上述规则，从13开始，我们生成以下序列：

13→ 40→ 20→ 10→ 5.→ 16→ 8.→ 4.→ 2.→ 1可以看出，该序列（从13开始，到1结束）包含10个术语。虽然这还没有被证明（科拉兹问题），但人们认为所有的起始数字都以1结束。

100万以下的哪个起始数字产生的链条最长？

注：一旦链开始，条款允许超过一百万。

Answer 1

每次在序列中生成一个项目时，也会生成该项目的项目。例如，对于13，您发现它生成10个项目。但在这个过程中，你还会发现40产生9个项目，20产生8个项目，10产生7个项目，等等。你可以在列表或字典中记住这些信息，这样在做13之后，你就不必再看40、20、10、5、16、4或2。

此外，当您生成以前从未见过的序列时，您可以查看此信息并将其用作快捷方式。对于13，你在看到13之前就已经看到了10，所以你只需计算40，20，10，然后你就知道10产生了7个项目，所以你只需将其添加到你已经看到的3个项目中，而不用计算其余的。

这将使用相当多的内存，但对于您必须考虑的项目数量来说，这是完全可行的。您可以使用某种截止（例如，仅存储100000或以下数字的结果），这仍然可以实现速度的极大提高，但使用的内存更少。

实现这一点的一种简单方法是重写函数，以递归方式而不是迭代方式计算序列，然后应用像这样的记忆修饰符。递归有一些开销，但记忆的好处可能会超过这一点。