【欧拉计划第 14 题】最长的考拉兹序列 Longest Collatz sequence

发表于 2022-05-01 分类于欧拉计划阅读次数：本文字数： 2.5k 阅读时长 ≈ 2 分钟

Problem 14 Longest Collatz sequence

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

$$
\large n\rightarrow \frac{n}{2}\ \left ( n\ is\ even \right ) ,n\rightarrow3n+1\ \left ( \ n\ is\ odd \right )
$$

Using the rule above and starting with $13$, we generate the following sequence:

$$
\large 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1
$$

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.

问题 14 最长的考拉兹序列

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

$$
\large n\rightarrow \frac{n}{2}\ \left ( n,是偶数 \right ) ,n\rightarrow3n+1\ \left ( n,是奇数 \right )
$$

使用上面的规则并从 $13$ 开始，生成以下序列：

$$
\large 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1
$$

可以看出这个序列从 $13$ 开始并到 $1$ 结束总共包含 $10$ 个数。
考拉兹猜想指出使用以上迭代规则，所有正整数都会最终回到一，虽然这个猜想仍未得到证明。
求在一百万以下，哪个起始数可以产生最长的考拉兹序列？
注意：序列中包含的数的个数可以超过一百万。

解题报告

考拉兹猜想

考拉兹猜想（Collatz conjecture），又称为奇偶归一猜想、3n+1 猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想，是指对于每一个正整数，如果它是奇数，则对它乘 3 再加 1，如果它是偶数，则对它除以 2，如此循环，最终都能够得到 1

$$
\large f\left ( n \right )=\left\{\begin{matrix}\frac{n}{2} \quad\quad\quad if \, n\equiv 0\\3n+1 \quad if \, n\equiv 1\end{matrix}\right.\left .\quad( mod \,\, 2 \right )
$$

思路分析

其实当你看到题目的时候，不知到你有没有和我想到一块儿去，那必然又是咱滴老朋友暴力算法啦

显然，我们只要求算出一到一百万之间所有数字的考拉兹序列长度，然后在所有求出的序列长度值中找出最大值就能解决本题

但是可以做一些优化，比如大家都知道当 n 是奇数时，3n+1 一定是偶数。那我们根本没必要让程序重复执行冗余步骤

换言之，当 n 是奇数的时候，在其后追加一步，继续计算 (3n+1)/2。便可省去很多中间计算步骤，程序执行效率自然得到提高

还有一点是参考其他大神写的题解意识到的，就是程序重复计算的问题。较大的数据量在计算过程中可能会产生重复数据，我们是不是可以将所有计算步骤得到的结果做下缓存。这样在下一步遇到重复值时可以直接调用，避免重复计算，提高程序执行效率

或者也可以使用递归法实现本题

代码实现

/*
 * @Author: coder-jason
 * @Date: 2022-05-1 09:00:42
 * @LastEditTime: 2022-05-01 09:13:49
 */
#include <bits/stdc++.h>
using namespace std; 

int cal(long long n) 
{
    if (n == 1)
        return 1;
    if (n % 2)
        return 1 + cal(3 * n + 1);
    else
        1 + cal(n / 2);
}

int main()
{
    int n = 0, ans = 0;
    for (int i = 1; i < 1000000; i++)
    {
        int tmp = cal(i);
        if (tmp > ans)
        {
            n = i;
            ans = tmp;
        }
    }
    cout << n << endl;
    return 0;
}

'''
Author: sorrowise
Date: 2022-05-1 08:42:30
LastEditTime: 2022-05-01 09:13:19
'''
 
N=10**6
d = {}
for x in range(2,N):
    i,n = x,0
    while x != 1:
        if x < i:
            n = n + d[x]
            break
        elif x % 2 == 0:
            x = x // 2
            n += 1
        else:
            x = (3*x+1) // 2
            n += 2
    d[i] = n
print(max(d,key=d.get))

答案：837799

参考资料：

递归算法
记忆化搜索算法优化
longest Collatz sequence