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

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

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

    定义: 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 条附言  ·  113 天前

    值得一提的是 如果 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   113 天前
    1 万以内 10 个
    10 万以内 24 个
    100 万还在算,随手写了个伪代码,好慢。
    另外,自身的友好数是自身的,也计算在内的吧,我没有排除。比如目前看到的:28 、8128 。
    YUX
        2
    YUX   113 天前
    @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   113 天前
    @Xusually 你这 10 个是排除了的吧?不排除我看是 14 个啊
    YUX
        4
    YUX   113 天前
    分享一些结果:
    10000 -> 10
    100000 -> 26
    1000000 -> 82
    Xusually
        5
    Xusually   113 天前
    @luckyrayyy 嗯,代码有点问题,停了重新来。本来想写个流程示例代码的,结果随手写完就跑起来了。毫无优化,速度感人。
    YUX
        6
    YUX   113 天前
    @luckyrayyy #3
    应该是这 10 个数
    220
    284
    1184
    1210
    2620
    2924
    5020
    6368
    6232
    5564
    YUX
        7
    YUX   113 天前
    @Xusually #5 期待优化好了分享一下代码
    AAASUKA
        8
    AAASUKA   113 天前
    用一个 1 亿长的数组,序号代表数字 n,值存放 d(n)怎么样?
    input2output
        9
    input2output   113 天前
    第一反应先算素数,试着算了一下,结果到 1e6 就开始吃力了
    silentx
        10
    silentx   113 天前
    一下是 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   113 天前
    写了个单线程的,感觉这个多线程有点麻烦,算了 16 秒,结果 462 个,跟楼主有点出入,下班再看是不是哪里错了。
    luckyrayyy
        12
    luckyrayyy   113 天前
    既然排除自身的话,友好数应该是偶数个吧?楼主怎么算出来是奇数?
    YUX
        13
    YUX   113 天前
    @luckyrayyy #12 虽然友好数是成对出现的 但是如果一对友好数中有一个超过限制(1 亿) 那这个数就不能算作小于一亿的友好数
    luckyrayyy
        14
    luckyrayyy   113 天前
    @YUX 噢噢,原来如此,那应该是我漏掉了几个你说的这种情况的。
    crella
        15
    crella   113 天前
    好奇楼主为什么研究这些“数学题”。
    YUX
        16
    YUX   113 天前
    @crella #15 楼主还在读数学系
    crella
        17
    crella   113 天前
    个人微小的意见,某些奥数题目真的浪费时间。

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

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

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

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

    123444a
        34
    123444a   112 天前 via Android
    分解素因子即可,很多年前的题目了
    liyunlong41
        35
    liyunlong41   112 天前 via iPhone
    @Ultraman 应该是意识到算法的差距吧
    liyunlong41
        36
    liyunlong41   112 天前
    应该是有相应的算法来求解的,但是我不会~,直接暴力求的…,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   112 天前 via Android
    @liyunlong41 这是 acm 题,19s 通不过的
    liyunlong41
        38
    liyunlong41   112 天前 via iPhone
    @123444a 思想交流而已,不用这么认真。再说能跑出数据来了,打表不随便过嘛。
    123444a
        39
    123444a   112 天前 via Android
    @liyunlong41 没人告诉你止于 1 亿哦
    123444a
        40
    123444a   112 天前 via Android
    最终就是要打表滴呵呵
    nomoon
        41
    nomoon   112 天前
    楼主你这是在刷 project euler 么?
    YUX
        42
    YUX   112 天前
    @nomoon #41 嗯
    wutiantong
        43
    wutiantong   112 天前
    我不能认同把这个叫做数学题,作为算法题这也挺无趣的。
    starqoq
        44
    starqoq   112 天前
    首先用线性素数筛把所有素数都找出来,对于合数,也可以记录一个因子。
    然后对于和数 d(X) = d(X/p) + p (p 是 X 的一个因子)

    然后在扫一下满足 d(X)!=X && d(d(X))=X 即可
    复杂度 O(n)
    macg0406
        45
    macg0406   111 天前
    先求 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   111 天前
    @macg0406 贴 github 链接需要手机认证。。。
    链接 base64: aHR0cHM6Ly9naXN0LmdpdGh1Yi5jb20vbWFjZzA0MDYvOGE1MzU0M2U0ZTQxNjkyZjEyMjYxMjEyM2Y2ZWNhZjc=
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2880 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:13 · PVG 21:13 · LAX 06:13 · JFK 09:13
    ♥ Do have faith in what you're doing.