这是一个创建于 1706 天前的主题，其中的信息可能已经有所发展或是发生改变。
各位大多是计算机的大佬，本人是一个数学系的弟弟，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.咱们先默认这个猜想是成立的
第 1 条附言 · 2020-03-22 21:13:30 +08:00
感觉超级有收获 hhhh
这样至少能让我进步蛮快的 比我自己一个人闭门造车好多了 看样子明天还能再开一题 谢谢所有回帖的大佬
这样至少能让我进步蛮快的 比我自己一个人闭门造车好多了 看样子明天还能再开一题 谢谢所有回帖的大佬
第 2 条附言 · 2020-03-23 16:06:16 +08:00
下一题
/t/655363
/t/655363
 |
1
litmxs 2020-03-22 15:41:59 +08:00 via Android
每一个数字的下一个数字是确定的，那么之后的长度也是确定的，记录一下就好了吧？
|
 |
3
geelaw 2020-03-22 15:56:51 +08:00 via iPhone
根据 Wikipedia，答案包括 63728127，需要 949 次。
由于这是一个未证明的猜想，所以用于枚举的机器不已知是多项式时间的。一个简单的思路是准备一个平衡树用来记录步骤数，然后枚举每个数并进行运算。 |
 |
4
crella 2020-03-22 16:37:18 +08:00 via Android
两个问题：一，研究这个有什么用？狗头保命
二、感觉这个写起来还算容易，但是要想节省内存或运算量，有点讲究。 有空研究一下，谢谢启发。 |
|
5
crella 2020-03-22 16:47:39 +08:00 via Android
有个想法。对于例子数列，其中 16 的对应数列就是 16 8 4 2 1，所以每计算一个数对应的数列，可以把其子节点对应的数列也存在总表里。
第二，先从 99999999 开始算，从覆盖尽可能多的子节点。然后再从 99999998.……逐步减一算，如果总表有这个数的序列就不用算了。 |
|
6
geelaw 2020-03-22 16:48:50 +08:00  4
@geelaw #3 https://gist.github.com/GeeLaw/16cf55d209eeed93463b07499f4e86c2
用 C++ 的 std::map 似乎就已经足够了，在我的电脑上大约需要 2 分 45 秒，吃掉了 9.5 GB 内存，并且验证了需要 949 次（最大次数）的数是惟一的。 |
|
7
crella 2020-03-22 16:58:46 +08:00 via Android
算出 n 从 1 到 33333333 之间所有奇数的 3n+1 的结果，结果是偶数 m，其上一个节点可能为 n 也可能为(3n+1)*2 的偶数，所以分支有且只有这样情况的 33333333 个。先把这 33333333 个分支对应的序列按 n 从大到小算出来，再算其他不是分支点的情况。
以上纯属猜想，没有验证过。高数不及格，溜了。 |
|
8
crella 2020-03-22 17:45:35 +08:00 via Android
由于 ruby 老大难的内存回收问题，我想用运算量换空间。这样存 9999999 个哈希，每个哈希存放当前节点值和下一节点值。检查序列长度的时候就 while 当前节点值>1; 检查下一节点值。这样可能存内存数组就行而不需要用到数据库……
|
 |
9
gwy15 2020-03-22 18:56:07 +08:00 2
@geelaw 不需要 map，map 的开销太大了，而且缓存了很多只用了一次的数据。
直接用 vector 缓存常用部分，0.52s 跑完，内存不到 1G https://gist.github.com/gwy15/3e24d7ddc460d2b4800c488b4ce610f8 |
 |
10
xiaobai1202 2020-03-22 19:06:01 +08:00
我第一反应咋能是动态规划呢
|
 |
11
cassyfar 2020-03-22 19:09:23 +08:00
从 1 开始 DFS 倒着推过去
1 只能可是 2 过来的，2 只可能是 4 过来的，4 只能可是 8 过来的，8 只可能是 16 过来的 16 可能是 32，或者 5 过来的。 另外不知道在倒推过程中能不能贪心，比如两种可能性，优先选 (n - 1)/3 的 |
 |
13
input2output 2020-03-22 20:10:37 +08:00
|
 |
14
YUX OP 我来个 python 多进程的 用服务器跑了一下 21 秒 献丑了
https://gist.github.com/YUX-IO/8668b50b69edbc97ee1fba3c6ca44a77 |
 |
17
metaquant 2020-03-22 21:16:58 +08:00
这道题在做 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 |
|
18
YUX OP |
|
19
YUX OP @metaquant #17 谢了谢了 正在学习这篇博文 我也在刷 project euler 不过原题的数太小了让我没有优化的欲望 所以尝试了一下大数
|
|
20
crella 2020-03-22 22:25:33 +08:00
@cassyfar 我正在试着倒推，发现了一个问题，比如 77031 的序列是
77031->231094->115547->346642->173321->519964... ->7311005->21933016->10966508->... ->8->4->2->1 序列出现的最大值是 21933016.请问从 1 开始反推的话，怎样限制搜索到的最大值，来求得在 100000 以内的 77031 的序列共有 350 步？ @input2output 谢谢你的代码 |
|
21
crella 2020-03-22 22:32:26 +08:00
77031 的序列图: 
最大值时 21933016，怎样限制这个值才能从后往前得出 77031 的完整序列？ 图表 excel 文件在这里 https://gitee.com/crella/rubycode/blob/master/77031_graph.xls |
|
22
litmxs 2020-03-22 22:51:28 +08:00
C++多线程, 把上面说的优化方式都用上了, i5 笔记本上耗时 900ms, 内存 80MB:
https://gist.github.com/LiTianxiong/09b1766ba60606367d1c20309c4bdaae |
 |
24
luckyrayyy 2020-03-22 23:51:53 +08:00 1
|
|
25
YUX OP @luckyrayyy 线程数一般怎么确定?
|
|
26
luckyrayyy 2020-03-23 00:38:35 +08:00 via iPhone
@YUX 跟 CPU 核数相当比较好。我这是图省事
|
 |
27
nonea 2020-03-23 10:24:50 +08:00
顶 好帖
|
|
28
input2output 2020-03-23 10:36:13 +08:00
这事感觉用不着一个一个算过去
刚刚通过模推了几个，好像发现了一个规律 要求 (0, 1ek] 内一值 n 其 CollatzRound(n) 为最大值， 则有 (n - 2^(k+1) + 1) / (2^(k + 1)) 为整数 这样完全就是瞬间出结果 |
|
29
input2output 2020-03-23 10:48:12 +08:00
|
|
30
YUX OP 1
@input2output #28 这个规律是不存在的
|
 |
31
jasonding 2020-03-23 11:04:19 +08:00
java 单线程递归
value:63728127 times:949 useTime:54665ms |
|
32
jasonding 2020-03-23 11:08:21 +08:00
代码：
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); } |
|
33
input2output 2020-03-23 11:13:31 +08:00
@YUX #30 感谢
|
|
34
YUX OP @input2output #33 hhhh 没事 数学领域需要你这种灵感 万一哪个新发现的小规律就成了证明考拉兹猜想的突破口
|
|
35
crella 2020-03-23 13:24:32 +08:00 1
@input2output
访问 https://iochen.com/2020/03/23/collatz/ 时 由不存在的页面返回站点主页，循环刷新页面，307，这个应该是个 bug?  |
|
36
crella 2020-03-23 13:29:43 +08:00 1
@input2output 在隐身模式下，第一次访问 https://iochen.com/dasda 这个错误链接，无法跳转到站点主页，循环 307.
但是如果第一次访问正确的链接成功，然后再访问错误链接，就能跳转到站点主页。 情况大概是这样吧…… |
|
37
crella 2020-03-23 13:43:14 +08:00 1
@input2output 如图，如果不是 serviceworker 获取到 iochen.com 的内容，307 循环会不断循环下去。
 纯属好奇。 |
|
38
input2output 2020-03-23 14:31:19 +08:00
@crella #37 我清了一下 CF 缓存，我这边 opera 和 chromium 都没有问题，不知道你那边有没有问题了
|
|
39
YUX OP 下一题
/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 |
|
40
YUX OP 求助, 先谢了各位
/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 |
Select Language