能否证明拥有 4 个约数的自然数最多

[qinjiannet]

分别统计了 100 ， 1000 ， 10000 以内的自然数的约数个数分布情况。

得出了这样的猜测：拥有 4 个约数的自然数最多。

如果猜测是正确的，能否加以证明？

相关链接： http://bookshadow.com/weblog/2016/11/28/python-matplotlib-divisor-count-scatter-bar/

[yushiro]

歪一下楼，这个图形是程序跑完自动生成的？还是把数据丢 excel 里面用 excel 画图的？

[yushiro]

汗，看到外链了，是用组件的啊

[qinjiannet]

@yushiro 用 matplotlib 画的

[moonmagian]

10000 的数据量有点太少了，先试着跑一下几百万的数据吧

[qinjiannet]

@moonmagian 跑了 10 万的数据，和上面的结果相同。

[wy315700]

那是因为你找的数不够大

[qinjiannet]

@wy315700 大概到多少数量级可以看到区别？

[alicli]

别浪费时间了，如果不限定范围，结论是拥有四个约数的自然数和拥有三个约数的自然数一样多

[kindjeff]

就我的直觉来说，我觉得八楼是对的

[qinjiannet]

@alicli 能否解释一下原因？

[rrfeng]

这个……

1. 素数无限
2. 任取 4 个素数，乘积得到一个数。有无限种取法
3. 任取 5 个素数，有无限种取法……
4. 任取 N 个素数，也有无限种取法……

反过来看，拥有 N 个约数的自然数都有无限多个。

[Valyrian]

无限集合的比较： https://en.wikipedia.org/wiki/Cardinality

[alicli]

@qinjiannet 楼上说的挺详细的，你可以再搜一下''偶数和自然数一样多''，是个经典的问题

[9hills]

@alicli 无限数也有比较方法。

比如 2 的倍数比 3 的倍数多。这个是一个严肃的数学问题。

[9hills]

@9hills @alicli 例子举错了， 2 的倍数和 3 的倍数应该可以一一对应。但是有理数比素数多，这个算一个例子

[9hills]

fix: 有理数->正整数。。。口误

[xcatliu]

题目应该修改为
给定任意一个不小于 100 的自然数 N ，统计小于 N 的自然数的约数的个数，其中含有 4 个约数的最多。
上述猜想是否成立？如果不成立，那么 N 是多少时会不成立？

[DiamondbacK]

不能证明，因为结论不成立。

恰好有 4 个约数的正整数的集合是无穷大的，而整数集是最小的无穷集合。
所以恰好有 4 个约数的正整数的集合的势，等于整数集的势相等。
也就是说恰好有 4 个约数的正整数，与整数一样多。
同理，恰好有 2 个约数的正整数，也与整数一样多。即素数与整数一样多。
这就类似于，偶数与整数一样多，奇数与整数一样多。

不能理解的话，以下换一种角度论述。

假设整数 n 恰好有 4 个约数，则存在素数 p 和 q ， p <> q ，使得 n = p * q 。
则整数 a1 = p ^ 2 * q 和 a2 = p * q ^ 2 恰好有 6 个约数，且 a1 <> a2 。

假设正整数 m 也恰好有 4 个约数， m <> n ，则存在素数 r 和 s ， r <> s ，使得 m = r * s 。
那么整数 b1 = r ^ 2 * s 和 b2 = r * s ^ 2 恰好有 6 个约数，且 b1 <> b2 。

因为 m <> n ，所以集合 {r, s } <> {p, q}，所以 {b1, b2} 与 {a1, a2 } 不交。

综上，对于每一个恰好有 4 个约数的整数，都有两个恰好有 6 个约数的整数与之对应，且前者不相同时后者也不会重复，所以，恰好有 4 个约数的整数，不多于恰好有 6 个约数的整数的一半。

换成数学语言就是，存在从集合 { 恰好有 6 个约数的整数 } 到 { 恰好有 4 个约数的整数 } 的「满射」，所以前者的数量不小于后者。

[DiamondbacK]

@9hills
有理数也是「可数集」，与整数可以一一对应。
实数集的势大于有理数集的势，这个是成立的。

[aaronzjw]

把范围不断扩大, 说不定就找到反例了