use std::collections::BTreeMap;
pub fn run() -> Result<(), Box<dyn std::error::Error>> {
let mut map = BTreeMap::new();
for mut x in 2..1000000u32 {
let (i, mut n) = (x, 0u32);
while x != 1 {
if x < i {
n += map.get(&x).unwrap();
break;
} else if x % 2 == 0 {
x /= 2;
n += 1
} else {
x = (3 * x + 1) / 2;
n += 2
}
}
map.insert(i, n);
}
let mut max = 0u32;
let mut num = 0u32;
for (k, v) in map {
if v > max {
max = v;
num = k;
}
}
println!("num = {num}, max = {max}");
Ok(())
}
num = 837799, max = 524
不知道链长为啥不一样……
python版本，通过字典进行加速。注意中间值也要写入字典
import time
tt=time.time()
data={}
maxnum=(1,1)
data=1
def getl(x):
if x in data:
return (data,x)
if x%2==0:
ans=getl(x//2)+1
else:
ans=getl(3*x+1)+1
data=ans
return (ans,x)
for i in range(1,10**6+1):
maxnum=max(maxnum,getl(i))
print(maxnum)
print(time.time()-tt)
(525, 837799)
1.4954357147216797s