Problem 14 Longest Collatz sequence

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

n → n 2   ( n   i s   e v e n ) , n → 3 n + 1   (   n   i s   o d d ) \large n\rightarrow \frac{n}{2}\ \left ( n\ is\ even \right ) ,n\rightarrow3n+1\ \left ( \ n\ is\ odd \right )n→2n (niseven),n→3n+1 (nisodd)

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

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 \large 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow113→40→20→10→5→16→8→4→2→1

It can be seen that this sequence (starting at 13 1313 and finishing at 1) contains 10 1010 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1 11.

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 最长的考拉兹序列

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

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

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

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 \large 13\rightarrow40\rightarrow20\rightarrow10\rightarrow5\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow113→40→20→10→5→16→8→4→2→1

可以看出这个序列从 13 1313 开始并到 1 11 结束总共包含 10 1010 个数。

考拉兹猜想指出使用以上迭代规则，所有正整数都会最终回到一，虽然这个猜想仍未得到证明。

求在一百万以下，哪个起始数可以产生最长的考拉兹序列？

注意：序列中包含的数的个数可以超过一百万。

解题报告

考拉兹猜想

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

f ( n ) = { n 2 i f   n ≡ 0 3 n + 1 i f   n ≡ 1 ( m o d    2 ) \large f\left ( n \right )=\left\{

n2ifn≡03n+1ifn≡1n2ifn≡03n+1ifn≡1

\right.\left .\quad( mod \,\, 2 \right )f(n)={2nifn≡03n+1ifn≡1(mod2)

思路分析

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

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

但是可以做一些优化，比如大家都知道当 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