这是一个创建于 2922 天前的主题，其中的信息可能已经有所发展或是发生改变。
分别统计了 100 ， 1000 ， 10000 以内的自然数的约数个数分布情况。
得出了这样的猜测：拥有 4 个约数的自然数最多。
如果猜测是正确的，能否加以证明？
相关链接： http://bookshadow.com/weblog/2016/11/28/python-matplotlib-divisor-count-scatter-bar/
第 1 条附言 · 2016-11-28 14:16:34 +08:00
如果将题目做如下修改，能否得出结论？
给定任意一个不小于 100 的自然数 N ，统计小于 N 的自然数的约数的个数，其中含有 4 个约数的最多。
上述猜想是否成立？如果不成立，那么 N 是多少时会不成立？
给定任意一个不小于 100 的自然数 N ，统计小于 N 的自然数的约数的个数，其中含有 4 个约数的最多。
上述猜想是否成立？如果不成立，那么 N 是多少时会不成立？
第 2 条附言 · 2016-11-28 22:08:47 +08:00
已经证明上述猜测不成立 = =
当N = 1000000（一百万）、 10000000（一千万）时，最多的约数是8个 。
或许最多的约数是从4 -> 8 -> 16这样逐渐右移的？
N = 1000000（一百万）:
N = 10000000（一千万）：
 |
1
yushiro 2016-11-28 13:04:41 +08:00 via iPhone
歪一下楼，这个图形是程序跑完自动生成的？还是把数据丢 excel 里面用 excel 画图的？
|
|
2
yushiro 2016-11-28 13:05:38 +08:00 via iPhone
汗，看到外链了，是用组件的啊
|
 |
3
qinjiannet OP @yushiro 用 matplotlib 画的
|
 |
4
moonmagian 2016-11-28 13:08:31 +08:00 via Android
10000 的数据量有点太少了，先试着跑一下几百万的数据吧
|
|
5
qinjiannet OP @moonmagian 跑了 10 万的数据，和上面的结果相同。
|
 |
6
wy315700 2016-11-28 13:22:01 +08:00
那是因为你找的数不够大
|
|
7
qinjiannet OP @wy315700 大概到多少数量级可以看到区别？
|
 |
8
alicli 2016-11-28 13:33:38 +08:00 via iPhone
别浪费时间了，如果不限定范围，结论是拥有四个约数的自然数和拥有三个约数的自然数一样多
|
 |
9
kindjeff 2016-11-28 13:36:13 +08:00 via iPhone
就我的直觉来说，我觉得八楼是对的
|
|
10
qinjiannet OP @alicli 能否解释一下原因？
|
 |
11
rrfeng 2016-11-28 13:41:00 +08:00
这个……
1. 素数无限 2. 任取 4 个素数，乘积得到一个数。有无限种取法 3. 任取 5 个素数，有无限种取法…… 4. 任取 N 个素数，也有无限种取法…… 反过来看，拥有 N 个约数的自然数都有无限多个。 |
 |
12
Valyrian 2016-11-28 13:50:25 +08:00  1
|
|
13
alicli 2016-11-28 13:51:50 +08:00 via iPhone
@qinjiannet 楼上说的挺详细的，你可以再搜一下''偶数和自然数一样多''，是个经典的问题
|
 |
16
9hills 2016-11-28 13:57:57 +08:00
fix: 有理数->正整数。。。口误
|
 |
17
xcatliu 2016-11-28 14:08:39 +08:00 via iPhone 2
题目应该修改为
给定任意一个不小于 100 的自然数 N ，统计小于 N 的自然数的约数的个数，其中含有 4 个约数的最多。 上述猜想是否成立？如果不成立，那么 N 是多少时会不成立？ |
 |
18
DiamondbacK 2016-11-28 14:12:00 +08:00 4
不能证明，因为结论不成立。
恰好有 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 个约数的整数 } 的「满射」，所以前者的数量不小于后者。 |
|
19
DiamondbacK 2016-11-28 14:13:46 +08:00 1
|
 |
20
aaronzjw 2016-11-28 14:13:51 +08:00
把范围不断扩大, 说不定就找到反例了
|
|
21
qinjiannet OP @xcatliu 感谢回复，添加了一条附言！
|
|
22
qinjiannet OP @DiamondbacK 感谢回复！好高端。。。需要仔细理解一下
|
 |
23
theoractice 2016-11-28 14:18:04 +08:00 1
首先应该正确定义问题。一种合理的定义方式是：
对任意的自然数 N ，定义 P(x)为小于 N 的自然数 x 的约数，那么存在一个自然数 n ，使得对于所有的 N>n ，有 max[P(x)]=4 。 合理的定义应该不止这一种，但没必要把问题绕到比较无穷集合的大小上去，那显然不是楼主发问的本意。 |
|
24
qinjiannet OP @theoractice 是的，我参考 17L 的回复添加了一条附言。
|
|
25
theoractice 2016-11-28 14:23:13 +08:00
@DiamondbacK
证明本身没问题，但我不认为这完全符合 @qinjiannet 提问的本意。如楼上已经提到的那样，奇数和自然数当然是一一对应的，但对于任意的 N ，小于 N 的奇数永远是小于 N 的自然数的一半。这种理解更符合楼主做实验的初衷。 |
|
26
DiamondbacK 2016-11-28 14:26:56 +08:00
@theoractice
P(x) 的参数都没有 N ，「对任意自然数 N 」就没体现出来，应该用 P(N)。 这个定义下的结论不成立，很明显，对于任意大的 n ，可以构造更大的整数 a(n)，使得 a(n) 有任意多个约数，具体来说，让 a(n) 等于一个足够大的素数的整数幂即可。 楼主的问题本身表述基本完整，不是「绕到」无穷集合，本来就是无穷集合的问题。 |
|
27
DiamondbacK 2016-11-28 14:28:55 +08:00
@theoractice 好像 我对你的 max() 理解不对。
|
|
28
DiamondbacK 2016-11-28 14:38:54 +08:00
算了，楼主的新定义比较清楚，直接讨论新定义吧。
先想想。 |
 |
29
BingoXuan 2016-11-28 14:59:19 +08:00 via iPhone
如果给定连续的自然数集合，那么他们都可以由小于集合上界的两个自然数相乘所得，由于非素数的数远比素数多，那么两个数中存在非素数的组合比纯素数组合多。非素数的数通过同样的递归分解，得到更多约数。而且随着自然数越大，分解的约数越多，情况就越多，但是同样约数数量越少。因此两个素数相乘应该最多，其次是三个素数，接着是四个素数。
并不严谨，望赐教 |
|
30
DiamondbacK 2016-11-28 15:00:32 +08:00
我在 18 楼的证明漏掉了一种情形：对于恰有 4 个约数的正整数 n ，也可能是 n = p ^ 3 形式， p 为素数。
这不难修补。令 m = p ^ 5 与 n 对应即可。 |
 |
31
Quaintjade 2016-11-28 15:32:24 +08:00
自然数与自然数的无限子集应该是等势的，简单的说就是一样多。
如果只考察不大于 N 的有限集合，结论也许成立。 拥有 4 个约数的 k ，换句话来说就是有两个不同的质因数 a 和 b ，约数是{1, a, b, k}；或者立方数，约数是{1, c, c^2, k}。 |
|
32
Quaintjade 2016-11-28 15:36:54 +08:00
@Quaintjade 无限=>无穷
|
 |
33
Eleutherios 2016-11-28 15:37:24 +08:00
|
 |
34
wdhwg001 2016-11-28 15:49:32 +08:00
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)为其他值的状况。 好的现在问题是极限之间的比较了，问题似乎简单了一些，我再思考一下。 |
 |
35
garham 2016-11-28 15:49:34 +08:00
用素数的估计公式，能算出来小于 N 有 k 个约数的数的上下限，无穷大的时候应该可以证明
|
|
36
wdhwg001 2016-11-28 15:59:03 +08:00
也就是说，约数有 4 个的数可以定义为以下集合：
{x|x=a×b, a 和 b 均为质数} ∪ {x|x=a^3, a 为质数} 更近了一些，可以模糊的有感知，但甚至写不出“是最多的”的一种准确的，方便证明的表达。 |
|
37
wdhwg001 2016-11-28 16:13:02 +08:00
这样，我们可以继续写出：
约数有 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 个集合的并集的感觉… …不行，仿佛看到了无限的未来，有些怀疑我的数学知识是否够用了… |
 |
38
chiva 2016-11-28 17:57:02 +08:00 via iPhone
@rrfeng 不能这么想，这与 @qinjiannet 的问题不同了，他说的是一定范围内
|
 |
39
vtoexshan 2016-11-28 20:10:14 +08:00
你搞这个什么企图？
|
|
40
theoractice 2016-11-28 21:16:36 +08:00
@Eleutherios 嗯对，笔误了
|
 |
41
wenxw1997 2016-11-28 21:26:20 +08:00 via Android
楼上用集合的势考虑当然正确，不过楼主不是已经给了另一种“多少”的定义吗？楼主应该是想知道：
拥有四个约数的小于 n 的正整数个数>拥有某个固定的 k 个约数的小于 n 的正整数个数 是否成立 如果成立，还能否进一步估计这两个差别是怎样，能否找到一个函数 f(k)去估计 |
|
42
wenxw1997 2016-11-28 21:27:17 +08:00 via Android
上面的命题应该补上 n→∞
|
 |
43
innoink 2016-11-28 21:44:54 +08:00
我数学已经还给老师了。。不过看偶数坐标的图像。。感感觉很像卡方分布的一种图像。。
|
|
44
innoink 2016-11-28 21:53:05 +08:00
你说的约数算不算 1 和本身？
|
|
45
qinjiannet OP @innoink 算 1 和本身
|
 |
46
Mistwave 2016-11-28 22:29:30 +08:00 1
建议找点集合论的书翻一翻，@DiamondbacK 这位的答案思路是对的。
我从另一个角度试着阐述一下 有命题：任意有穷个可数集的笛卡儿积是可数集。 若 a, b, c, d 都属于正整数集 Z+，则有序对<a, b, c, d>组成的集合相当于四个可数集的笛卡儿积，显然也是可数集。 那么我们只需要将四个数相乘起来，可以得到{abcd | a, b, c, d ∈ Z+} 是上述集合的无穷真子集，显然也是可数集。 将此处的“ 4 ”个约数推广一下，拥有任意有限个约数 n 的自然数集都是可数集。 又有，可数集与自然数集 N 均等势（可以理解为集合大小一样），所以无论拥有几个约数的自然数集，都是等势的。 所以楼主的命题是不成立的。 |
 |
47
netzzx 2016-11-28 23:26:40 +08:00
为什么不改为考虑前 N 个自然数中有四个约数的自然数所占的比例呢? 这不就躲过去无穷集合的势的问题了么
|
 |
48
jasonding 2016-11-29 10:21:42 +08:00
任意一个奇数素数乘以 2 得到的结果都只有 4 个约数
|
|
49
jasonding 2016-11-29 10:24:56 +08:00
哦，不限于奇数，任意一个素数乘以 2 的结果都是只有 4 个约数的
|
 |
51
oldj 2016-11-29 11:31:48 +08:00
@jasonding 这么说起来其实任意两个素数的积，都有 4 个约数。比如 a 、 b 是两个素数，且 a≠b ，那么它们的积的约数有：{1, a, b, a*b }。
|
|
52
rrfeng 2016-11-29 11:47:06 +08:00
我们定义考察范围为 1-N ，可以找到素数列表中的第 M 个素数： R(1)=1 ， R(2)=2 ， R(3)=3 ， R(4)=5 ... R(M-1)， R(M) ..
使得 R(M-3)*R(M-2)*R(M-1)*R(M) < N < R(M-2)*R(M-1)*R(M)*R(M+1) 然后从 1-M 个素数中，任意取 n （ N<5 ） 个素数相乘，得到很多自然数，都属于 1 - N 显然 4 个数的取法最多。 考察 5 个素数的积……编不下去了…… |
 |
53
reture 2016-11-29 14:06:40 +08:00
|
|
54
qinjiannet OP @reture 这个是整数的不重复质因子的数目吧？
|
 |
56
phpcyy 2016-11-30 11:07:59 +08:00
@DiamondbacK 请问素数和合数等势吗？素数的势是不是小于合数？
|
|
57
DiamondbacK 2016-11-30 11:54:18 +08:00
@phpcyy 素数集、合数集都与整数集等势。可数集的无限子集统统等势。
|
Select Language