有没有数学爱好者，讨论一道题道题。yeah

[YUX]

各位大多是计算机的大佬，本人是一个数学系的弟弟，hhhhh 想学习一下。 题目呢很简单，是和考拉兹猜想 Collatz conjecture 相关的，

对于一个正整数 n
如果 n 是偶数，下一项就是 n/2
如果 n 是奇数，下一项就是 3n + 1

这样就生成了一个数列，例如: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 虽然还未证明，但是这个数列总会到 1 (然后就开始循环了，咱们就停在 1 好了，这样就是个有限数列了)。

Question 在小于一亿的数中，以哪一个正整数开头形成的数列最长。

p.s.希望能看到代码和运算时间，感兴趣的尝试一下～ p.s.咱们先默认这个猜想是成立的

[litmxs]

每一个数字的下一个数字是确定的，那么之后的长度也是确定的，记录一下就好了吧？

[YUX]

@litmxs #1 我的思路也是这个 我觉得对于每个思路的具体实现还是会有区别 想从中学习学习

[geelaw]

根据 Wikipedia，答案包括 63728127，需要 949 次。

由于这是一个未证明的猜想，所以用于枚举的机器不已知是多项式时间的。一个简单的思路是准备一个平衡树用来记录步骤数，然后枚举每个数并进行运算。

[crella]

两个问题：一，研究这个有什么用？狗头保命

二、感觉这个写起来还算容易，但是要想节省内存或运算量，有点讲究。

有空研究一下，谢谢启发。

[crella]

有个想法。对于例子数列，其中 16 的对应数列就是 16 8 4 2 1，所以每计算一个数对应的数列，可以把其子节点对应的数列也存在总表里。

第二，先从 99999999 开始算，从覆盖尽可能多的子节点。然后再从 99999998.……逐步减一算，如果总表有这个数的序列就不用算了。

[geelaw]

@geelaw #3 https://gist.github.com/GeeLaw/16cf55d209eeed93463b07499f4e86c2

用 C++ 的 std::map 似乎就已经足够了，在我的电脑上大约需要 2 分 45 秒，吃掉了 9.5 GB 内存，并且验证了需要 949 次（最大次数）的数是惟一的。

[crella]

算出 n 从 1 到 33333333 之间所有奇数的 3n+1 的结果，结果是偶数 m，其上一个节点可能为 n 也可能为(3n+1)*2 的偶数，所以分支有且只有这样情况的 33333333 个。先把这 33333333 个分支对应的序列按 n 从大到小算出来，再算其他不是分支点的情况。

以上纯属猜想，没有验证过。高数不及格，溜了。

[crella]

由于 ruby 老大难的内存回收问题，我想用运算量换空间。这样存 9999999 个哈希，每个哈希存放当前节点值和下一节点值。检查序列长度的时候就 while 当前节点值>1; 检查下一节点值。这样可能存内存数组就行而不需要用到数据库……

[gwy15]

@geelaw 不需要 map，map 的开销太大了，而且缓存了很多只用了一次的数据。
直接用 vector 缓存常用部分，0.52s 跑完，内存不到 1G

https://gist.github.com/gwy15/3e24d7ddc460d2b4800c488b4ce610f8

[xiaobai1202]

我第一反应咋能是动态规划呢

[cassyfar]

从 1 开始 DFS 倒着推过去

1 只能可是 2 过来的，2 只可能是 4 过来的，4 只能可是 8 过来的，8 只可能是 16 过来的
16 可能是 32，或者 5 过来的。

另外不知道在倒推过程中能不能贪心，比如两种可能性，优先选 (n - 1)/3 的

[geelaw]

@gwy15 #9 的确，改成固定范围缓存（我选了 100000000 ）之后比较快。

[input2output]

最简陋的方法：
https://gist.github.com/iochen/79f15b2eb20004a7329b25bfa648b745

i7 10% CPU 利用率，花了不到 80s

[YUX]

我来个 python 多进程的 用服务器跑了一下 21 秒 献丑了
https://gist.github.com/YUX-IO/8668b50b69edbc97ee1fba3c6ca44a77

[YUX]

@gwy15 #9 学习了 谢谢

[chizuo]

@geelaw 这个 map 是红黑树啊，查询复杂度爆炸。你应该用 unordered_map 啊

[metaquant]

这道题在做 project euler 第十四题时遇到过，我用的 python，在我的 xps13 时计算一亿内的最长考拉兹序列需要 1 分 34 秒。

可以优化的地方有两个：一是一是当 n 是奇数时，3n+1 必然是偶数，则接下来必定需要除以二，则可以一步走完，也就是说当 n 是奇数时可以多算一步，直接计算(3n+1)/2，这样可以更快的到达序列的终点，但注意在计算累计步数时，应该加二而不是加一。另一个可以优化的点是在计算各个数考拉兹序列时，中间过程可能出现之前已经计算过的数字，为了避免重复计算，可以把之前数字对应的序列长度都缓存下来，之后碰到同样的数字，直接引用其值并加上之前已经走过的步数即可。

具体可以参见我的博文： https://metaquant.org/euler-project-11-20-questions.html

代码见： https://github.com/sorrowise/euler/blob/master/014.py

[YUX]

160 核暴力美学

[YUX]

@metaquant #17 谢了谢了 正在学习这篇博文 我也在刷 project euler 不过原题的数太小了让我没有优化的欲望 所以尝试了一下大数

[crella]

@cassyfar 我正在试着倒推，发现了一个问题，比如 77031 的序列是

77031->231094->115547->346642->173321->519964... ->7311005->21933016->10966508->... ->8->4->2->1

序列出现的最大值是 21933016.请问从 1 开始反推的话，怎样限制搜索到的最大值，来求得在 100000 以内的 77031 的序列共有 350 步？


@input2output 谢谢你的代码