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

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

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

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