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

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。便可省去很多中间计算步骤,程序执行效率自然得到提高

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

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
* @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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
'''
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