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

[qinjiannet]

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

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

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

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

[qinjiannet]

@xcatliu 感谢回复，添加了一条附言！

[qinjiannet]

@DiamondbacK 感谢回复！好高端。。。需要仔细理解一下

[theoractice]

首先应该正确定义问题。一种合理的定义方式是：
对任意的自然数 N ，定义 P(x)为小于 N 的自然数 x 的约数，那么存在一个自然数 n ，使得对于所有的 N>n ，有 max[P(x)]=4 。

合理的定义应该不止这一种，但没必要把问题绕到比较无穷集合的大小上去，那显然不是楼主发问的本意。

[qinjiannet]

@theoractice 是的，我参考 17L 的回复添加了一条附言。

[theoractice]

@DiamondbacK
证明本身没问题，但我不认为这完全符合 @qinjiannet 提问的本意。如楼上已经提到的那样，奇数和自然数当然是一一对应的，但对于任意的 N ，小于 N 的奇数永远是小于 N 的自然数的一半。这种理解更符合楼主做实验的初衷。

[DiamondbacK]

@theoractice
P(x) 的参数都没有 N ，「对任意自然数 N 」就没体现出来，应该用 P(N)。
这个定义下的结论不成立，很明显，对于任意大的 n ，可以构造更大的整数 a(n)，使得 a(n) 有任意多个约数，具体来说，让 a(n) 等于一个足够大的素数的整数幂即可。

楼主的问题本身表述基本完整，不是「绕到」无穷集合，本来就是无穷集合的问题。

[DiamondbacK]

@theoractice 好像 我对你的 max() 理解不对。

[DiamondbacK]

算了，楼主的新定义比较清楚，直接讨论新定义吧。
先想想。

[BingoXuan]

如果给定连续的自然数集合，那么他们都可以由小于集合上界的两个自然数相乘所得，由于非素数的数远比素数多，那么两个数中存在非素数的组合比纯素数组合多。非素数的数通过同样的递归分解，得到更多约数。而且随着自然数越大，分解的约数越多，情况就越多，但是同样约数数量越少。因此两个素数相乘应该最多，其次是三个素数，接着是四个素数。
并不严谨，望赐教

[DiamondbacK]

我在 18 楼的证明漏掉了一种情形：对于恰有 4 个约数的正整数 n ，也可能是 n = p ^ 3 形式， p 为素数。
这不难修补。令 m = p ^ 5 与 n 对应即可。

[Quaintjade]

自然数与自然数的无限子集应该是等势的，简单的说就是一样多。

如果只考察不大于 N 的有限集合，结论也许成立。
拥有 4 个约数的 k ，换句话来说就是有两个不同的质因数 a 和 b ，约数是{1, a, b, k}；或者立方数，约数是{1, c, c^2, k}。

[Quaintjade]

@Quaintjade 无限=>无穷

[Eleutherios]

@9hills 有理数和正整数同构，都是可数无穷（最小的无穷数），这个没什么问题；如果素数有无穷个的话，那么素数肯定也和正整数同构。

@theoractice 应该用 argmax{ P(x) }

[wdhwg001]

http://primes.utm.edu/glossary/xpage/tau.html

设 x 的约数为 d(x)，则 x 和 d(x)存在这样的关系：

x=k[1]^e[1] × k[2]^e[2] × …… × k[n]^e[n]

d(x)=(e[1]+1)×(e[2]+1)× …… ×(e[n]+1)

其中， k[]为 x 的质因数， e[]为 x 质因数分解后每一项质因数出现的次数。

那么，你的猜想就是说当 d(x)=4 时，即 d(x)=(1+1)×(1+1)和 d(x)=(3+1)时的情况，你感觉似乎 x 可能存在的值的总量要大于 d(x)为其他值的状况。

好的现在问题是极限之间的比较了，问题似乎简单了一些，我再思考一下。

[garham]

用素数的估计公式，能算出来小于 N 有 k 个约数的数的上下限，无穷大的时候应该可以证明

[wdhwg001]

也就是说，约数有 4 个的数可以定义为以下集合：
{x|x=a×b, a 和 b 均为质数} ∪ {x|x=a^3, a 为质数}

更近了一些，可以模糊的有感知，但甚至写不出“是最多的”的一种准确的，方便证明的表达。

[wdhwg001]

这样，我们可以继续写出：

约数有 2 个的数可以定义为以下集合：
{x|x=a, a 为质数}

约数有 3 个的数可以定义为以下集合：
{x|x=a^2, a 为质数}

约数有 4 个的数可以定义为以下集合：
{x|x=a^3, a 为质数}∪{x|x=a×b, a 和 b 均为质数, a<b}

约数有 5 个的数可以定义为以下集合：
{x|x=a^4, a 为质数}

约数有 6 个的数可以定义为以下集合：
{x|x=a^5, a 为质数}∪{x|x=a×b^2, a 和 b 均为质数, a<b}∪{x|x=a^2×b, a 和 b 均为质数, a<b}

……有某种规律在其中，像是…

如果一个数的约数有 n 个的话，它可以写成这样的， d(n)-1 个集合的并集的感觉…

…不行，仿佛看到了无限的未来，有些怀疑我的数学知识是否够用了…

[chiva]

@rrfeng 不能这么想，这与 @qinjiannet 的问题不同了，他说的是一定范围内

[vtoexshan]

你搞这个什么企图？

[theoractice]

@Eleutherios 嗯对，笔误了