By

文章目錄

原题链接 http://projecteuler.net/problem=14

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n ->n/2 (n is even)
n ->3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 -> 40 ->20 ->10 ->5 ->16 -> 8 -> 4 ->2 ->1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

最长的考拉兹数：

在正整数上定义如下迭代序列：

n -> n / 2 (n是偶数)

n -> 3n + 1 (n是奇数)
从13开始，使用上面的规则，我们将得到如下序列：
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
我们可以看到这个序列(从13开始到1结束)包含10个数。虽然这个还没有被证明(考拉兹问题),但我们可以认为所有的数都将在1结束。
求1 000 000以下的数，从哪一个数开始，产生的序列最长。
注意：一旦这个序列开始后，其中的数允许超过1 000 000。

解答：
如果将1到1000000都按照上述过程迭代，速度将会很慢，所以要保存一些计算结果，这样速度就会快很多了。
代码面前，了无秘密。直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python
# -*- coding:utf-8 -*-
'''
Created on 2013-5-24

@author: shilong
@email: long470884130@163.com
'''
col = {}
col[1] = 1
def collatz(n):
    if n in col:
        return col[n]
    else:
        if n % 2 == 0:
            col[n] = collatz(n / 2) + 1
        else:
            col[n] = collatz(3 * n + 1) + 1
        return col[n]

打赏作者

文章目錄