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

[YUX]

定义: 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
• 昨天的题，欢迎继续讨论

值得一提的是 如果 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.

[Xusually]

1 万以内 10 个
10 万以内 24 个
100 万还在算，随手写了个伪代码，好慢。
另外，自身的友好数是自身的，也计算在内的吧，我没有排除。比如目前看到的：28 、8128 。

[YUX]

@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]

@Xusually 你这 10 个是排除了的吧？不排除我看是 14 个啊

[YUX]

分享一些结果：
10000 -> 10
100000 -> 26
1000000 -> 82

[Xusually]

@luckyrayyy 嗯，代码有点问题，停了重新来。本来想写个流程示例代码的，结果随手写完就跑起来了。毫无优化，速度感人。

[YUX]

@luckyrayyy #3
应该是这 10 个数
220
284
1184
1210
2620
2924
5020
6368
6232
5564

[YUX]

@Xusually #5 期待优化好了分享一下代码

[AAASUKA]

用一个 1 亿长的数组，序号代表数字 n，值存放 d(n)怎么样？

[input2output]

第一反应先算素数，试着算了一下，结果到 1e6 就开始吃力了

[silentx]

一下是 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]

写了个单线程的，感觉这个多线程有点麻烦，算了 16 秒，结果 462 个，跟楼主有点出入，下班再看是不是哪里错了。
https://gist.github.com/Beritra/4e1a4440bf8203a7df1a8ba5f2f8f5ab

[luckyrayyy]

既然排除自身的话，友好数应该是偶数个吧？楼主怎么算出来是奇数？

[YUX]

@luckyrayyy #12 虽然友好数是成对出现的 但是如果一对友好数中有一个超过限制(1 亿) 那这个数就不能算作小于一亿的友好数

[luckyrayyy]

@YUX 噢噢，原来如此，那应该是我漏掉了几个你说的这种情况的。

[crella]

好奇楼主为什么研究这些“数学题”。

[YUX]

@crella #15 楼主还在读数学系

[crella]

个人微小的意见，某些奥数题目真的浪费时间。

在 nga 看到的题目：15*15 的棋盘上布满黑棋和白旗，其中黑棋的数量等于白棋的数量+1 。求黑棋不存在五子相连的概率。注：相连的方向可以是水平线、竖直线、斜线。

[YUX]

python 服务器上 77.49 秒 今天研究了一下 numba，‘一行代码真的速度翻了十倍’ https://numba.pydata.org/

https://gist.github.com/YUX-IO/426ce33562c15fe6a56a84afc6d20987

[7Sasuke7L]

数学系是偏计算类的吧，基础数学一般不研究这种问题

[7Sasuke7L]

简单提个建议，这叫因子，或者叫正整数因子，而不是除数。

[Ultraman]

这个问题实实在在让我认识到了电脑性能的差距。。。
算了好久才算了不到 200 个。。。

[Ultraman]

@Ultraman 当然还有我自己的菜🐔水平。。。

[YUX]

@Ultraman #21 前 1 千万才有 208 个 已经一个亿的 1/10 了 hhhhh 我更关心你是用那个语言写的

[Ultraman]

@YUX #23 C 语言。376s 才跑完前 1000 个，而且才算出来 200 个结果，还不知道哪里错了。感觉 c 语言白学了 QAQ
https://pastebin.com/embed_js/F1AiPK9F

[Ultraman]

@Ultraman #24 呸，是前 1kw 个

[input2output]

用 go 写了一个，速度还行，30 几秒的样子，就是不知道哪里出错了，算出来 432 个

[YUX]

@input2output #26 前一千万是 208 个么？

[shm7]

是不是可以把质数算出来，然后用小的非质数做 线性规划

[input2output]

@input2output #26 把 uint32 改成 uint64 就好了，就是慢了好多；算下来是 462 ？
和 @luckyrayyy #11 一样
如果 a 可以等于 b，那算下来就是 467 了

[Ultraman]

@Ultraman #24 long 改成 int 时间缩短一多半也还得 111S 。

[luckyrayyy]

@input2output 你看下楼主回复我的，不是因为相等，是因为 a 小于一亿，b 大于一亿这种情况没算。

[litmxs]

10s, 500Mb 内存
C++多线程, 上古 i5 笔记本
和昨天一样的思路写的, 参照这篇文章进行了优化: https://www.xarg.org/puzzle/project-euler/problem-21/
答案是 462 个(入伙可以相等的话那就是 467 个
优化空间还很大, 应该还可以优化到 5s 内
https://gist.github.com/LiTianxiong/40263593e9464a205e567b4cf1d4314b

[ksedz]

$ time ./main
467

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

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

https://gist.github.com/shapled/e21a6d5ecd8129a6a7bccc84d1f67b9a

[123444a]

分解素因子即可，很多年前的题目了

[liyunlong41]

@Ultraman 应该是意识到算法的差距吧

[liyunlong41]

应该是有相应的算法来求解的，但是我不会~，直接暴力求的…，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]

@liyunlong41 这是 acm 题，19s 通不过的

[liyunlong41]

@123444a 思想交流而已，不用这么认真。再说能跑出数据来了，打表不随便过嘛。

[123444a]

@liyunlong41 没人告诉你止于 1 亿哦

[123444a]

最终就是要打表滴呵呵

[nomoon]

楼主你这是在刷 project euler 么？

[YUX]

@nomoon #41 嗯

[wutiantong]

我不能认同把这个叫做数学题，作为算法题这也挺无趣的。

[starqoq]

首先用线性素数筛把所有素数都找出来，对于合数，也可以记录一个因子。
然后对于和数 d(X) = d(X/p) + p (p 是 X 的一个因子)

然后在扫一下满足 d(X)!=X && d(d(X))=X 即可
复杂度 O(n)

[macg0406]

先求 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]

@macg0406 贴 github 链接需要手机认证。。。
链接 base64: aHR0cHM6Ly9naXN0LmdpdGh1Yi5jb20vbWFjZzA0MDYvOGE1MzU0M2U0ZTQxNjkyZjEyMjYxMjEyM2Y2ZWNhZjc=