题目14：找出100万以下最长的考拉兹序列

欧拉计划

题目14：找出100万以下最长的考拉兹序列

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 结束。

以哪个不超过 100 万的数字开始，能给得到最长的序列？

注意: 一旦序列开始之后，也就是从第二项开始，项是可以超过 100 万的。


视频讲解：




思路解析及源码参考（C & Python）：

游客，如果您要查看本帖隐藏内容请回复

歌者文明清理员

首楼

欧拉计划

歌者文明清理员 发表于 2023-7-5 18:37
首楼

不要光占楼不回答问题~

让我们一起享受思考带来的快乐吧！

歌者文明清理员

欧拉计划 发表于 2023-7-5 18:40
不要光占楼不回答问题~

让我们一起享受思考带来的快乐吧！

1. def get_length(n):
   
2.     length = 0
   
3.     while n != 1:
   
4.         n = (3 * n + 1) if n % 2 else (n // 2)
   
5.         length += 1
   
6.     return length
   
7. 
   
8. longest_length = 0
   
9. longest_n = 0
   
10. for i in range(1, 100_0000):
    
11.     length = get_length(i)
    
12.     if length > longest_length:
    
13.         longest_length = length
    
14.         longest_n = i
    
15. print(longest_n)
    

复制代码

837799

zhangjinxuan

记忆化搜索好像会爆掉，数字最大可以达到 56991483520

只能暴力查找好像

欧拉计划

zhangjinxuan 发表于 2023-7-6 17:04
记忆化搜索好像会爆掉，数字最大可以达到 56991483520

只能暴力查找好像

可以优化，因为有非常多的冗余计算。

zhangjinxuan

欧拉计划 发表于 2023-7-7 15:51
可以优化，因为有非常多的冗余计算。

如果不能全部记下来就很……恼）

鱼C-小师妹

pixie99

def Kolaz(n):
    count = 1
    while n != 1:
        if n % 2 == 0:
            n = n // 2
            count += 1
        elif n % 2 == 1:
            n = 3*n + 1
            count += 1
    return count

max_count = 1
for i in range(1000000,1,-1):
    count = Kolaz(i)
    if count > max_count:
        max_count = count
        t = i

print(t)
print(max_count)

Fxcjcj

学习

Ly_悠然天下

^_^

VPython999

1. A={1:1}
   
2. def B():
   
3.     a=1
   
4.     m=1
   
5.     for i in range(2,1000001):
   
6.         count=0
   
7.         b=i
   
8.         while b!=1:
   
9.             if b in A:
   
10.                 break
    
11.             elif b%2==0:
    
12.                 b=b//2
    
13.             else:
    
14.                 b=3*b+1
    
15.             count+=1
    
16.         A[i]=count+A[b]
    
17.         if m<A[i]:
    
18.             a=i
    
19.             m=A[i]
    
20.     return a,m
    
21. 
    
22. 
    
23. print(B())
    
24. (837799, 525)

复制代码

鱼彧泽

学习一下

auend

这个是经典题

hone404

学习

nkysp

好

sharp46

hejiage

刷到第十四提了

1Asdusdhjssd

学习了

kalendd