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

鉴于昨天探讨的数学题本人收获颇丰,今天再发一道有意思的数学题,感兴趣的快进来试试

  •  
  •   YUX · 2020-03-23 13:57:51 +08:00 · 3412 次点击
    这是一个创建于 1466 天前的主题,其中的信息可能已经有所发展或是发生改变。

    定义: d(n) 为 n 的所有除数之和(不包括 n 自身,最小为 1 ),例如:

    • 220 的除数是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 所以 d(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

    • 284 的除数是 1, 2, 4, 71, 142 所以 d(284) = 1 + 2 + 4 + 71 + 142 = 220

    定义: 因为 d(220) = 284, d(284) = 220 所以 220 和 284 这两个数都被称为 友好数

    Question 在小于一亿的数中,共有多少个友好数


    • 我计算的答案是 467
    • 昨天的题,欢迎继续讨论
    第 1 条附言  ·  2020-03-23 16:24:56 +08:00

    值得一提的是 如果 d(a) = b 并且 d(b) = a, 当 a ≠ b 当时候才能称 a 和 b 为 友好数

    If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

    46 条回复    2020-03-25 15:46:26 +08:00
    Xusually
        1
    Xusually  
       2020-03-23 16:17:18 +08:00
    1 万以内 10 个
    10 万以内 24 个
    100 万还在算,随手写了个伪代码,好慢。
    另外,自身的友好数是自身的,也计算在内的吧,我没有排除。比如目前看到的:28 、8128 。
    YUX
        2
    YUX  
    OP
       2020-03-23 16:21:50 +08:00
    @Xusually #1 谢谢提醒 我忘记加上这个限制了。d(a) = b 并且 d(b) = a 并且 a ≠ b 才能称 a 和 b 为 *友好数*
    > If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
    luckyrayyy
        3
    luckyrayyy  
       2020-03-23 16:34:44 +08:00
    @Xusually 你这 10 个是排除了的吧?不排除我看是 14 个啊
    YUX
        4
    YUX  
    OP
       2020-03-23 16:42:35 +08:00
    分享一些结果:
    10000 -> 10
    100000 -> 26
    1000000 -> 82
    Xusually
        5
    Xusually  
       2020-03-23 16:46:46 +08:00
    @luckyrayyy 嗯,代码有点问题,停了重新来。本来想写个流程示例代码的,结果随手写完就跑起来了。毫无优化,速度感人。
    YUX
        6
    YUX  
    OP
       2020-03-23 16:47:17 +08:00
    @luckyrayyy #3
    应该是这 10 个数
    220
    284
    1184
    1210
    2620
    2924
    5020
    6368
    6232
    5564
    YUX
        7
    YUX  
    OP
       2020-03-23 16:48:33 +08:00
    @Xusually #5 期待优化好了分享一下代码
    AAASUKA
        8
    AAASUKA  
       2020-03-23 17:02:03 +08:00
    用一个 1 亿长的数组,序号代表数字 n,值存放 d(n)怎么样?
    input2output
        9
    input2output  
       2020-03-23 17:16:56 +08:00
    第一反应先算素数,试着算了一下,结果到 1e6 就开始吃力了
    silentx
        10
    silentx  
       2020-03-23 17:23:21 +08:00
    一下是 1000w 的 感觉不优化 1y 速度感人了

    220 - 284
    284 - 220
    1184 - 1210
    1210 - 1184
    2620 - 2924
    2924 - 2620
    5020 - 5564
    5564 - 5020
    6232 - 6368
    6368 - 6232
    10744 - 10856
    10856 - 10744
    12285 - 14595
    14595 - 12285
    17296 - 18416
    18416 - 17296
    63020 - 76084
    66928 - 66992
    66992 - 66928
    67095 - 71145
    69615 - 87633
    71145 - 67095
    76084 - 63020
    79750 - 88730
    87633 - 69615
    88730 - 79750
    100485 - 124155
    122265 - 139815
    122368 - 123152
    123152 - 122368
    124155 - 100485
    139815 - 122265
    141664 - 153176
    142310 - 168730
    153176 - 141664
    168730 - 142310
    171856 - 176336
    176272 - 180848
    176336 - 171856
    180848 - 176272
    185368 - 203432
    196724 - 202444
    202444 - 196724
    203432 - 185368
    280540 - 365084
    308620 - 389924
    319550 - 430402
    356408 - 399592
    365084 - 280540
    389924 - 308620
    399592 - 356408
    430402 - 319550
    437456 - 455344
    455344 - 437456
    469028 - 486178
    486178 - 469028
    503056 - 514736
    514736 - 503056
    522405 - 525915
    525915 - 522405
    600392 - 669688
    609928 - 686072
    624184 - 691256
    635624 - 712216
    643336 - 652664
    652664 - 643336
    667964 - 783556
    669688 - 600392
    686072 - 609928
    691256 - 624184
    712216 - 635624
    726104 - 796696
    783556 - 667964
    796696 - 726104
    802725 - 863835
    863835 - 802725
    879712 - 901424
    898216 - 980984
    901424 - 879712
    947835 - 1125765
    980984 - 898216
    998104 - 1043096
    1043096 - 998104
    1077890 - 1099390
    1099390 - 1077890
    1125765 - 947835
    1154450 - 1189150
    1156870 - 1292570
    1175265 - 1438983
    1185376 - 1286744
    1189150 - 1154450
    1280565 - 1340235
    1286744 - 1185376
    1292570 - 1156870
    1328470 - 1483850
    1340235 - 1280565
    1358595 - 1486845
    1392368 - 1464592
    1438983 - 1175265
    1464592 - 1392368
    1466150 - 1747930
    1468324 - 1749212
    1483850 - 1328470
    1486845 - 1358595
    1511930 - 1598470
    1598470 - 1511930
    1669910 - 2062570
    1747930 - 1466150
    1749212 - 1468324
    1798875 - 1870245
    1870245 - 1798875
    2062570 - 1669910
    2082464 - 2090656
    2090656 - 2082464
    2236570 - 2429030
    2429030 - 2236570
    2652728 - 2941672
    2723792 - 2874064
    2728726 - 3077354
    2739704 - 2928136
    2802416 - 2947216
    2803580 - 3716164
    2874064 - 2723792
    2928136 - 2739704
    2941672 - 2652728
    2947216 - 2802416
    3077354 - 2728726
    3276856 - 3721544
    3606850 - 3892670
    3716164 - 2803580
    3721544 - 3276856
    3786904 - 4300136
    3805264 - 4006736
    3892670 - 3606850
    4006736 - 3805264
    4238984 - 4314616
    4246130 - 4488910
    4259750 - 4445050
    4300136 - 3786904
    4314616 - 4238984
    4445050 - 4259750
    4482765 - 5120595
    4488910 - 4246130
    4532710 - 6135962
    4604776 - 5162744
    5120595 - 4482765
    5123090 - 5504110
    5147032 - 5843048
    5162744 - 4604776
    5232010 - 5799542
    5357625 - 5684679
    5385310 - 5812130
    5459176 - 5495264
    5495264 - 5459176
    5504110 - 5123090
    5684679 - 5357625
    5726072 - 6369928
    5730615 - 6088905
    5799542 - 5232010
    5812130 - 5385310
    5843048 - 5147032
    5864660 - 7489324
    6088905 - 5730615
    6135962 - 4532710
    6329416 - 6371384
    6369928 - 5726072
    6371384 - 6329416
    6377175 - 6680025
    6680025 - 6377175
    6955216 - 7418864
    6993610 - 7158710
    7158710 - 6993610
    7275532 - 7471508
    7288930 - 8221598
    7418864 - 6955216
    7471508 - 7275532
    7489112 - 7674088
    7489324 - 5864660
    7577350 - 8493050
    7674088 - 7489112
    7677248 - 7684672
    7684672 - 7677248
    7800544 - 7916696
    7850512 - 8052488
    7916696 - 7800544
    8052488 - 7850512
    8221598 - 7288930
    8262136 - 8369864
    8369864 - 8262136
    8493050 - 7577350
    8619765 - 9627915
    9071685 - 9498555
    9199496 - 9592504
    9339704 - 9892936
    9363584 - 9437056
    9437056 - 9363584
    9498555 - 9071685
    9592504 - 9199496
    9627915 - 8619765
    9892936 - 9339704
    luckyrayyy
        11
    luckyrayyy  
       2020-03-23 17:32:12 +08:00
    写了个单线程的,感觉这个多线程有点麻烦,算了 16 秒,结果 462 个,跟楼主有点出入,下班再看是不是哪里错了。
    https://gist.github.com/Beritra/4e1a4440bf8203a7df1a8ba5f2f8f5ab
    luckyrayyy
        12
    luckyrayyy  
       2020-03-23 17:36:34 +08:00
    既然排除自身的话,友好数应该是偶数个吧?楼主怎么算出来是奇数?
    YUX
        13
    YUX  
    OP
       2020-03-23 17:49:10 +08:00
    @luckyrayyy #12 虽然友好数是成对出现的 但是如果一对友好数中有一个超过限制(1 亿) 那这个数就不能算作小于一亿的友好数
    luckyrayyy
        14
    luckyrayyy  
       2020-03-23 18:00:13 +08:00
    @YUX 噢噢,原来如此,那应该是我漏掉了几个你说的这种情况的。
    crella
        15
    crella  
       2020-03-23 18:18:52 +08:00
    好奇楼主为什么研究这些“数学题”。
    YUX
        16
    YUX  
    OP
       2020-03-23 18:21:05 +08:00
    @crella #15 楼主还在读数学系
    crella
        17
    crella  
       2020-03-23 18:26:47 +08:00
    个人微小的意见,某些奥数题目真的浪费时间。

    在 nga 看到的题目:15*15 的棋盘上布满黑棋和白旗,其中黑棋的数量等于白棋的数量+1 。求黑棋不存在五子相连的概率。注:相连的方向可以是水平线、竖直线、斜线。
    YUX
        18
    YUX  
    OP
       2020-03-23 18:31:35 +08:00   ❤️ 1
    python 服务器上 77.49 秒 今天研究了一下 numba,‘一行代码真的速度翻了十倍’ https://numba.pydata.org/

    https://gist.github.com/YUX-IO/426ce33562c15fe6a56a84afc6d20987
    7Sasuke7L
        19
    7Sasuke7L  
       2020-03-23 18:33:54 +08:00 via Android
    数学系是偏计算类的吧,基础数学一般不研究这种问题
    7Sasuke7L
        20
    7Sasuke7L  
       2020-03-23 18:34:30 +08:00 via Android
    简单提个建议,这叫因子,或者叫正整数因子,而不是除数。
    Ultraman
        21
    Ultraman  
       2020-03-23 18:37:52 +08:00 via iPhone
    这个问题实实在在让我认识到了电脑性能的差距。。。
    算了好久才算了不到 200 个。。。
    Ultraman
        22
    Ultraman  
       2020-03-23 18:39:12 +08:00 via iPhone
    @Ultraman 当然还有我自己的菜🐔水平。。。
    YUX
        23
    YUX  
    OP
       2020-03-23 18:42:38 +08:00
    @Ultraman #21 前 1 千万才有 208 个 已经一个亿的 1/10 了 hhhhh 我更关心你是用那个语言写的
    Ultraman
        24
    Ultraman  
       2020-03-23 19:01:25 +08:00
    @YUX #23 C 语言。376s 才跑完前 1000 个,而且才算出来 200 个结果,还不知道哪里错了。感觉 c 语言白学了 QAQ
    https://pastebin.com/embed_js/F1AiPK9F
    Ultraman
        25
    Ultraman  
       2020-03-23 19:02:36 +08:00
    @Ultraman #24 呸,是前 1kw 个
    input2output
        26
    input2output  
       2020-03-23 19:15:12 +08:00
    用 go 写了一个,速度还行,30 几秒的样子,就是不知道哪里出错了,算出来 432 个
    YUX
        27
    YUX  
    OP
       2020-03-23 19:16:38 +08:00   ❤️ 1
    @input2output #26 前一千万是 208 个么?
    shm7
        28
    shm7  
       2020-03-23 19:18:16 +08:00 via iPhone
    是不是可以把质数算出来,然后用小的非质数做 线性规划
    input2output
        29
    input2output  
       2020-03-23 19:21:10 +08:00
    @input2output #26 把 uint32 改成 uint64 就好了,就是慢了好多;算下来是 462 ?
    和 @luckyrayyy #11 一样
    如果 a 可以等于 b,那算下来就是 467 了
    Ultraman
        30
    Ultraman  
       2020-03-23 19:32:06 +08:00
    @Ultraman #24 long 改成 int 时间缩短一多半也还得 111S 。
    luckyrayyy
        31
    luckyrayyy  
       2020-03-23 19:34:56 +08:00   ❤️ 1
    @input2output 你看下楼主回复我的,不是因为相等,是因为 a 小于一亿,b 大于一亿这种情况没算。
    litmxs
        32
    litmxs  
       2020-03-23 23:49:20 +08:00   ❤️ 1
    10s, 500Mb 内存
    C++多线程, 上古 i5 笔记本
    和昨天一样的思路写的, 参照这篇文章进行了优化: https://www.xarg.org/puzzle/project-euler/problem-21/
    答案是 462 个(入伙可以相等的话那就是 467 个
    优化空间还很大, 应该还可以优化到 5s 内
    https://gist.github.com/LiTianxiong/40263593e9464a205e567b4cf1d4314b
    ksedz
        33
    ksedz  
       2020-03-24 00:12:41 +08:00   ❤️ 2
    $ time ./main
    467

    real 0m7.801s
    user 0m7.579s
    sys 0m0.228s

    先算出 1 亿以内所有质数,然后对幂次做深搜,占内存有点大,2G 多

    https://gist.github.com/shapled/e21a6d5ecd8129a6a7bccc84d1f67b9a
    123444a
        34
    123444a  
       2020-03-24 00:46:13 +08:00 via Android
    分解素因子即可,很多年前的题目了
    liyunlong41
        35
    liyunlong41  
       2020-03-24 01:03:34 +08:00 via iPhone
    @Ultraman 应该是意识到算法的差距吧
    liyunlong41
        36
    liyunlong41  
       2020-03-24 01:18:43 +08:00
    应该是有相应的算法来求解的,但是我不会~,直接暴力求的…,1 亿以内 462 个,golang,19 秒,790M 内存。
    func TestDn(t *testing.T) {
    const N = 1e8
    var dn = make([]int, N+1)
    for i := 2; i+i <= N; i++ {
    for j := i << 1; j <= N; j += i {
    //fmt.Println(j)
    dn[j] += i
    }
    }
    count := 0
    for a := 2; a <= N; a++ {
    b := dn[a] + 1
    if b != a {
    if b <= N && dn[b]+1 == a {
    //fmt.Println(a, b)
    count++
    }
    }
    }
    fmt.Println("count:", count)
    }
    123444a
        37
    123444a  
       2020-03-24 01:25:24 +08:00 via Android
    @liyunlong41 这是 acm 题,19s 通不过的
    liyunlong41
        38
    liyunlong41  
       2020-03-24 01:34:57 +08:00 via iPhone
    @123444a 思想交流而已,不用这么认真。再说能跑出数据来了,打表不随便过嘛。
    123444a
        39
    123444a  
       2020-03-24 01:36:18 +08:00 via Android
    @liyunlong41 没人告诉你止于 1 亿哦
    123444a
        40
    123444a  
       2020-03-24 01:38:14 +08:00 via Android
    最终就是要打表滴呵呵
    nomoon
        41
    nomoon  
       2020-03-24 03:16:51 +08:00
    楼主你这是在刷 project euler 么?
    YUX
        42
    YUX  
    OP
       2020-03-24 10:28:37 +08:00
    @nomoon #41 嗯
    wutiantong
        43
    wutiantong  
       2020-03-24 13:36:20 +08:00
    我不能认同把这个叫做数学题,作为算法题这也挺无趣的。
    starqoq
        44
    starqoq  
       2020-03-24 13:51:29 +08:00
    首先用线性素数筛把所有素数都找出来,对于合数,也可以记录一个因子。
    然后对于和数 d(X) = d(X/p) + p (p 是 X 的一个因子)

    然后在扫一下满足 d(X)!=X && d(d(X))=X 即可
    复杂度 O(n)
    macg0406
        45
    macg0406  
       2020-03-25 15:36:54 +08:00
    先求 X 的所有因子之和,可以用递推方式求解,f(k) = f(m) * f(n), 如果 k = m * n,并且 m, n 互质。然后减去本身就得到了本题中的 d(x)。

    time ./a.out
    462
    ./a.out 4.06s user 0.14s system 99% cpu 4.202 total

    时间复杂度不超过 O(n logn)空间复杂度是 O(n)
    macg0406
        46
    macg0406  
       2020-03-25 15:46:26 +08:00
    @macg0406 贴 github 链接需要手机认证。。。
    链接 base64: aHR0cHM6Ly9naXN0LmdpdGh1Yi5jb20vbWFjZzA0MDYvOGE1MzU0M2U0ZTQxNjkyZjEyMjYxMjEyM2Y2ZWNhZjc=
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1388 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 17:37 · PVG 01:37 · LAX 10:37 · JFK 13:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.