首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
YUX
V2EX  ›  问与答

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

  •  1
     
  •   YUX · 108 天前 · 2440 次点击
    这是一个创建于 108 天前的主题,其中的信息可能已经有所发展或是发生改变。

    各位大多是计算机的大佬,本人是一个数学系的弟弟,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 条附言  ·  108 天前
    感觉超级有收获 hhhh
    这样至少能让我进步蛮快的 比我自己一个人闭门造车好多了 看样子明天还能再开一题 谢谢所有回帖的大佬
    第 2 条附言  ·  107 天前
    下一题
    /t/655363
    40 条回复    2020-04-04 12:05:20 +08:00
    litmxs
        1
    litmxs   108 天前 via Android
    每一个数字的下一个数字是确定的,那么之后的长度也是确定的,记录一下就好了吧?
    YUX
        2
    YUX   108 天前
    @litmxs #1 我的思路也是这个 我觉得对于每个思路的具体实现还是会有区别 想从中学习学习
    geelaw
        3
    geelaw   108 天前 via iPhone
    根据 Wikipedia,答案包括 63728127,需要 949 次。

    由于这是一个未证明的猜想,所以用于枚举的机器不已知是多项式时间的。一个简单的思路是准备一个平衡树用来记录步骤数,然后枚举每个数并进行运算。
    crella
        4
    crella   108 天前 via Android
    两个问题:一,研究这个有什么用?狗头保命

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

    有空研究一下,谢谢启发。
    crella
        5
    crella   108 天前 via Android
    有个想法。对于例子数列,其中 16 的对应数列就是 16 8 4 2 1,所以每计算一个数对应的数列,可以把其子节点对应的数列也存在总表里。

    第二,先从 99999999 开始算,从覆盖尽可能多的子节点。然后再从 99999998.……逐步减一算,如果总表有这个数的序列就不用算了。
    geelaw
        6
    geelaw   108 天前   ❤️ 4
    @geelaw #3

    用 C++ 的 std::map 似乎就已经足够了,在我的电脑上大约需要 2 分 45 秒,吃掉了 9.5 GB 内存,并且验证了需要 949 次(最大次数)的数是惟一的。
    crella
        7
    crella   108 天前 via Android
    算出 n 从 1 到 33333333 之间所有奇数的 3n+1 的结果,结果是偶数 m,其上一个节点可能为 n 也可能为(3n+1)*2 的偶数,所以分支有且只有这样情况的 33333333 个。先把这 33333333 个分支对应的序列按 n 从大到小算出来,再算其他不是分支点的情况。

    以上纯属猜想,没有验证过。高数不及格,溜了。
    crella
        8
    crella   108 天前 via Android
    由于 ruby 老大难的内存回收问题,我想用运算量换空间。这样存 9999999 个哈希,每个哈希存放当前节点值和下一节点值。检查序列长度的时候就 while 当前节点值>1; 检查下一节点值。这样可能存内存数组就行而不需要用到数据库……
    gwy15
        9
    gwy15   108 天前   ❤️ 2
    @geelaw 不需要 map,map 的开销太大了,而且缓存了很多只用了一次的数据。
    直接用 vector 缓存常用部分,0.52s 跑完,内存不到 1G

    xiaobai1202
        10
    xiaobai1202   108 天前
    我第一反应咋能是动态规划呢
    cassyfar
        11
    cassyfar   108 天前
    从 1 开始 DFS 倒着推过去

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

    另外不知道在倒推过程中能不能贪心,比如两种可能性,优先选 (n - 1)/3 的
    geelaw
        12
    geelaw   108 天前
    @gwy15 #9 的确,改成固定范围缓存(我选了 100000000 )之后比较快。
    input2output
        13
    input2output   108 天前
    最简陋的方法:


    i7 10% CPU 利用率,花了不到 80s
    YUX
        14
    YUX   108 天前
    我来个 python 多进程的 用服务器跑了一下 21 秒 献丑了
    YUX
        15
    YUX   108 天前
    @gwy15 #9 学习了 谢谢
    chizuo
        16
    chizuo   108 天前
    @geelaw 这个 map 是红黑树啊,查询复杂度爆炸。你应该用 unordered_map 啊
    metaquant
        17
    metaquant   108 天前
    这道题在做 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
        18
    YUX   108 天前
    YUX
        19
    YUX   108 天前
    @metaquant #17 谢了谢了 正在学习这篇博文 我也在刷 project euler 不过原题的数太小了让我没有优化的欲望 所以尝试了一下大数
    crella
        20
    crella   108 天前
    @cassyfar 我正在试着倒推,发现了一个问题,比如 77031 的序列是

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

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


    @input2output 谢谢你的代码
    crella
        21
    crella   108 天前
    77031 的序列图: ![scr007.jpg]( https://i.loli.net/2020/03/22/pTwkaqBlz1ruLAV.jpg)
    最大值时 21933016,怎样限制这个值才能从后往前得出 77031 的完整序列?

    图表 excel 文件在这里 https://gitee.com/crella/rubycode/blob/master/77031_graph.xls
    litmxs
        22
    litmxs   108 天前
    C++多线程, 把上面说的优化方式都用上了, i5 笔记本上耗时 900ms, 内存 80MB:

    YUX
        23
    YUX   108 天前
    @litmxs #22 太快了 我写的第一个版本跑了 10 分钟
    luckyrayyy
        24
    luckyrayyy   108 天前   ❤️ 1


    写了个 Java 10 线程版本,2.7 秒...
    YUX
        25
    YUX   108 天前 via iPhone
    @luckyrayyy 线程数一般怎么确定?
    luckyrayyy
        26
    luckyrayyy   108 天前 via iPhone
    @YUX 跟 CPU 核数相当比较好。我这是图省事
    nonea
        27
    nonea   108 天前
    顶 好帖
    input2output
        28
    input2output   108 天前
    这事感觉用不着一个一个算过去
    刚刚通过模推了几个,好像发现了一个规律

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

    这样完全就是瞬间出结果
    input2output
        29
    input2output   108 天前
    @input2output #28 觉得符号太难看的可以到我的博客

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

    我只用了几个例子,如有错误,还请指正
    YUX
        30
    YUX   108 天前   ❤️ 1
    @input2output #28 这个规律是不存在的
    jasonding
        31
    jasonding   108 天前
    java 单线程递归
    value:63728127
    times:949
    useTime:54665ms
    jasonding
        32
    jasonding   108 天前
    代码:
    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
        33
    input2output   108 天前
    @YUX #30 感谢
    YUX
        34
    YUX   108 天前
    @input2output #33 hhhh 没事 数学领域需要你这种灵感 万一哪个新发现的小规律就成了证明考拉兹猜想的突破口
    crella
        35
    crella   107 天前   ❤️ 1
    @input2output

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

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

    ![scr007.jpg]( https://i.loli.net/2020/03/23/uLdktpZhTO8N3x2.jpg)
    crella
        36
    crella   107 天前   ❤️ 1
    @input2output 在隐身模式下,第一次访问 https://iochen.com/dasda 这个错误链接,无法跳转到站点主页,循环 307.

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

    情况大概是这样吧……
    crella
        37
    crella   107 天前   ❤️ 1
    @input2output 如图,如果不是 serviceworker 获取到 iochen.com 的内容,307 循环会不断循环下去。

    ![process-02.jpg]( https://i.loli.net/2020/03/23/PDEr9izdTp5bgsv.jpg)

    纯属好奇。
    input2output
        38
    input2output   107 天前
    @crella #37 我清了一下 CF 缓存,我这边 opera 和 chromium 都没有问题,不知道你那边有没有问题了
    YUX
        39
    YUX   107 天前
    下一题
    /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
        40
    YUX   96 天前
    求助, 先谢了各位
    /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
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3666 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 04:39 · PVG 12:39 · LAX 21:39 · JFK 00:39
    ♥ Do have faith in what you're doing.