有没有数学爱好者，讨论一道题道题。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.咱们先默认这个猜想是成立的

感觉超级有收获 hhhh
这样至少能让我进步蛮快的 比我自己一个人闭门造车好多了 看样子明天还能再开一题 谢谢所有回帖的大佬

下一题
/t/655363

[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 谢谢你的代码

[crella]

77031 的序列图: 
最大值时 21933016，怎样限制这个值才能从后往前得出 77031 的完整序列？

图表 excel 文件在这里 https://gitee.com/crella/rubycode/blob/master/77031_graph.xls

[litmxs]

C++多线程, 把上面说的优化方式都用上了, i5 笔记本上耗时 900ms, 内存 80MB:

https://gist.github.com/LiTianxiong/09b1766ba60606367d1c20309c4bdaae

[YUX]

@litmxs #22 太快了 我写的第一个版本跑了 10 分钟

[luckyrayyy]

https://gist.github.com/Beritra/50bf0d149f83885fa4e3bb89f54c1f76

写了个 Java 10 线程版本，2.7 秒...

[YUX]

@luckyrayyy 线程数一般怎么确定?

[luckyrayyy]

@YUX 跟 CPU 核数相当比较好。我这是图省事

[nonea]

顶 好帖

[input2output]

这事感觉用不着一个一个算过去
刚刚通过模推了几个，好像发现了一个规律

要求 (0, 1ek] 内一值 n 其 CollatzRound(n) 为最大值，
则有 (n - 2^(k+1) + 1) / (2^(k + 1)) 为整数

这样完全就是瞬间出结果

[input2output]

@input2output #28 觉得符号太难看的可以到我的博客

https://iochen.com/2020/03/23/collatz/

我只用了几个例子，如有错误，还请指正

[YUX]

@input2output #28 这个规律是不存在的

[jasonding]

java 单线程递归
value:63728127
times:949
useTime:54665ms

[jasonding]

代码：
public static void main(String[] args) {
long start = System.currentTimeMillis();
int maxTimes = 0;
for(Long i=99999999l; i >0 ; i --) {
Long times = test(i, 1);
if(times > maxTimes) {
maxTimes = times.intValue();
System.out.println("value:" + i);
System.out.println("times:" + maxTimes);
}
}
long end = System.currentTimeMillis();
System.out.println("useTime:" + (end - start) + "ms");
}
private static long test(Long i, int times) {
if( i == 1) {
return i;
}
Long x;
if(i % 2 == 0) {
x = i/2;
}else {
x = i*3 + 1;
}
if(x == 1) {
return times;
}
return test(x, times+1);
}

[input2output]

@YUX #30 感谢

[YUX]

@input2output #33 hhhh 没事 数学领域需要你这种灵感 万一哪个新发现的小规律就成了证明考拉兹猜想的突破口

[crella]

@input2output

访问 https://iochen.com/2020/03/23/collatz/ 时

由不存在的页面返回站点主页，循环刷新页面，307，这个应该是个 bug?


[crella]

@input2output 在隐身模式下，第一次访问 https://iochen.com/dasda 这个错误链接，无法跳转到站点主页，循环 307.

但是如果第一次访问正确的链接成功，然后再访问错误链接，就能跳转到站点主页。

情况大概是这样吧……

[crella]

@input2output 如图，如果不是 serviceworker 获取到 iochen.com 的内容，307 循环会不断循环下去。


纯属好奇。

[input2output]

@crella #37 我清了一下 CF 缓存，我这边 opera 和 chromium 都没有问题，不知道你那边有没有问题了

[YUX]

下一题
/t/655363
@input2output #38
@crella #37
@jasonding #32
@nonea #27
@luckyrayyy #26
@litmxs #22
@metaquant #17
@chizuo #16
@geelaw #12
@cassyfar #11
@xiaobai1202 #10
@gwy15 #9

[YUX]

求助, 先谢了各位
/t/659291
@input2output #38
@crella #37
@jasonding #32
@nonea #27
@luckyrayyy #26
@litmxs #22
@metaquant #17
@chizuo #16
@geelaw #12
@cassyfar #11
@xiaobai1202 #10
@gwy15 #9