V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
qinjiannet
V2EX  ›  程序员

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

  •  
  •   qinjiannet · 2016-11-28 13:01:46 +08:00 · 5278 次点击
    这是一个创建于 2677 天前的主题,其中的信息可能已经有所发展或是发生改变。

    分别统计了 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 是多少时会不成立?
    第 2 条附言  ·  2016-11-28 22:08:47 +08:00

    已经证明上述猜测不成立 = =

    当N = 1000000(一百万)、 10000000(一千万)时,最多的约数是8个 。

    或许最多的约数是从4 -> 8 -> 16这样逐渐右移的?

    N = 1000000(一百万):

    N = 10000000

    N = 10000000(一千万):

    N = 10000000

    57 条回复    2016-11-30 11:54:18 +08:00
    yushiro
        1
    yushiro  
       2016-11-28 13:04:41 +08:00 via iPhone
    歪一下楼,这个图形是程序跑完自动生成的?还是把数据丢 excel 里面用 excel 画图的?
    yushiro
        2
    yushiro  
       2016-11-28 13:05:38 +08:00 via iPhone
    汗,看到外链了,是用组件的啊
    qinjiannet
        3
    qinjiannet  
    OP
       2016-11-28 13:05:47 +08:00
    @yushiro 用 matplotlib 画的
    moonmagian
        4
    moonmagian  
       2016-11-28 13:08:31 +08:00 via Android
    10000 的数据量有点太少了,先试着跑一下几百万的数据吧
    qinjiannet
        5
    qinjiannet  
    OP
       2016-11-28 13:11:19 +08:00
    @moonmagian 跑了 10 万的数据,和上面的结果相同。
    wy315700
        6
    wy315700  
       2016-11-28 13:22:01 +08:00
    那是因为你找的数不够大
    qinjiannet
        7
    qinjiannet  
    OP
       2016-11-28 13:22:42 +08:00 via iPhone
    @wy315700 大概到多少数量级可以看到区别?
    alicli
        8
    alicli  
       2016-11-28 13:33:38 +08:00 via iPhone
    别浪费时间了,如果不限定范围,结论是拥有四个约数的自然数和拥有三个约数的自然数一样多
    kindjeff
        9
    kindjeff  
       2016-11-28 13:36:13 +08:00 via iPhone
    就我的直觉来说,我觉得八楼是对的
    qinjiannet
        10
    qinjiannet  
    OP
       2016-11-28 13:40:08 +08:00 via iPhone
    @alicli 能否解释一下原因?
    rrfeng
        11
    rrfeng  
       2016-11-28 13:41:00 +08:00
    这个……

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

    反过来看,拥有 N 个约数的自然数都有无限多个。
    Valyrian
        12
    Valyrian  
       2016-11-28 13:50:25 +08:00   ❤️ 1
    alicli
        13
    alicli  
       2016-11-28 13:51:50 +08:00 via iPhone
    @qinjiannet 楼上说的挺详细的,你可以再搜一下''偶数和自然数一样多'',是个经典的问题
    9hills
        14
    9hills  
       2016-11-28 13:52:07 +08:00
    @alicli 无限数也有比较方法。

    比如 2 的倍数比 3 的倍数多。这个是一个严肃的数学问题。
    9hills
        15
    9hills  
       2016-11-28 13:56:52 +08:00
    @9hills @alicli 例子举错了, 2 的倍数和 3 的倍数应该可以一一对应。但是有理数比素数多,这个算一个例子
    9hills
        16
    9hills  
       2016-11-28 13:57:57 +08:00
    fix: 有理数->正整数。。。口误
    xcatliu
        17
    xcatliu  
       2016-11-28 14:08:39 +08:00 via iPhone   ❤️ 2
    题目应该修改为
    给定任意一个不小于 100 的自然数 N ,统计小于 N 的自然数的约数的个数,其中含有 4 个约数的最多。
    上述猜想是否成立?如果不成立,那么 N 是多少时会不成立?
    DiamondbacK
        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 个约数的整数 } 的「满射」,所以前者的数量不小于后者。
    DiamondbacK
        19
    DiamondbacK  
       2016-11-28 14:13:46 +08:00   ❤️ 1
    @9hills
    有理数也是「可数集」,与整数可以一一对应。
    实数集的势大于有理数集的势,这个是成立的。
    aaronzjw
        20
    aaronzjw  
       2016-11-28 14:13:51 +08:00
    把范围不断扩大, 说不定就找到反例了
    qinjiannet
        21
    qinjiannet  
    OP
       2016-11-28 14:17:15 +08:00
    @xcatliu 感谢回复,添加了一条附言!
    qinjiannet
        22
    qinjiannet  
    OP
       2016-11-28 14:17:52 +08:00
    @DiamondbacK 感谢回复!好高端。。。需要仔细理解一下
    theoractice
        23
    theoractice  
       2016-11-28 14:18:04 +08:00   ❤️ 1
    首先应该正确定义问题。一种合理的定义方式是:
    对任意的自然数 N ,定义 P(x)为小于 N 的自然数 x 的约数,那么存在一个自然数 n ,使得对于所有的 N>n ,有 max[P(x)]=4 。

    合理的定义应该不止这一种,但没必要把问题绕到比较无穷集合的大小上去,那显然不是楼主发问的本意。
    qinjiannet
        24
    qinjiannet  
    OP
       2016-11-28 14:19:03 +08:00
    @theoractice 是的,我参考 17L 的回复添加了一条附言。
    theoractice
        25
    theoractice  
       2016-11-28 14:23:13 +08:00
    @DiamondbacK
    证明本身没问题,但我不认为这完全符合 @qinjiannet 提问的本意。如楼上已经提到的那样,奇数和自然数当然是一一对应的,但对于任意的 N ,小于 N 的奇数永远是小于 N 的自然数的一半。这种理解更符合楼主做实验的初衷。
    DiamondbacK
        26
    DiamondbacK  
       2016-11-28 14:26:56 +08:00
    @theoractice
    P(x) 的参数都没有 N ,「对任意自然数 N 」就没体现出来,应该用 P(N)。
    这个定义下的结论不成立,很明显,对于任意大的 n ,可以构造更大的整数 a(n),使得 a(n) 有任意多个约数,具体来说,让 a(n) 等于一个足够大的素数的整数幂即可。

    楼主的问题本身表述基本完整,不是「绕到」无穷集合,本来就是无穷集合的问题。
    DiamondbacK
        27
    DiamondbacK  
       2016-11-28 14:28:55 +08:00
    @theoractice 好像 我对你的 max() 理解不对。
    DiamondbacK
        28
    DiamondbacK  
       2016-11-28 14:38:54 +08:00
    算了,楼主的新定义比较清楚,直接讨论新定义吧。
    先想想。
    BingoXuan
        29
    BingoXuan  
       2016-11-28 14:59:19 +08:00 via iPhone
    如果给定连续的自然数集合,那么他们都可以由小于集合上界的两个自然数相乘所得,由于非素数的数远比素数多,那么两个数中存在非素数的组合比纯素数组合多。非素数的数通过同样的递归分解,得到更多约数。而且随着自然数越大,分解的约数越多,情况就越多,但是同样约数数量越少。因此两个素数相乘应该最多,其次是三个素数,接着是四个素数。
    并不严谨,望赐教
    DiamondbacK
        30
    DiamondbacK  
       2016-11-28 15:00:32 +08:00
    我在 18 楼的证明漏掉了一种情形:对于恰有 4 个约数的正整数 n ,也可能是 n = p ^ 3 形式, p 为素数。
    这不难修补。令 m = p ^ 5 与 n 对应即可。
    Quaintjade
        31
    Quaintjade  
       2016-11-28 15:32:24 +08:00
    自然数与自然数的无限子集应该是等势的,简单的说就是一样多。

    如果只考察不大于 N 的有限集合,结论也许成立。
    拥有 4 个约数的 k ,换句话来说就是有两个不同的质因数 a 和 b ,约数是{1, a, b, k};或者立方数,约数是{1, c, c^2, k}。
    Quaintjade
        32
    Quaintjade  
       2016-11-28 15:36:54 +08:00
    @Quaintjade 无限=>无穷
    Eleutherios
        33
    Eleutherios  
       2016-11-28 15:37:24 +08:00
    @9hills 有理数和正整数同构,都是可数无穷(最小的无穷数),这个没什么问题;如果素数有无穷个的话,那么素数肯定也和正整数同构。

    @theoractice 应该用 argmax{ P(x) }
    wdhwg001
        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)为其他值的状况。

    好的现在问题是极限之间的比较了,问题似乎简单了一些,我再思考一下。
    garham
        35
    garham  
       2016-11-28 15:49:34 +08:00
    用素数的估计公式,能算出来小于 N 有 k 个约数的数的上下限,无穷大的时候应该可以证明
    wdhwg001
        36
    wdhwg001  
       2016-11-28 15:59:03 +08:00
    也就是说,约数有 4 个的数可以定义为以下集合:
    {x|x=a×b, a 和 b 均为质数} ∪ {x|x=a^3, a 为质数}

    更近了一些,可以模糊的有感知,但甚至写不出“是最多的”的一种准确的,方便证明的表达。
    wdhwg001
        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 个集合的并集的感觉…

    …不行,仿佛看到了无限的未来,有些怀疑我的数学知识是否够用了…
    chiva
        38
    chiva  
       2016-11-28 17:57:02 +08:00 via iPhone
    @rrfeng 不能这么想,这与 @qinjiannet 的问题不同了,他说的是一定范围内
    vtoexshan
        39
    vtoexshan  
       2016-11-28 20:10:14 +08:00
    你搞这个什么企图?
    theoractice
        40
    theoractice  
       2016-11-28 21:16:36 +08:00
    @Eleutherios 嗯对,笔误了
    wenxw1997
        41
    wenxw1997  
       2016-11-28 21:26:20 +08:00 via Android
    楼上用集合的势考虑当然正确,不过楼主不是已经给了另一种“多少”的定义吗?楼主应该是想知道:
    拥有四个约数的小于 n 的正整数个数>拥有某个固定的 k 个约数的小于 n 的正整数个数
    是否成立
    如果成立,还能否进一步估计这两个差别是怎样,能否找到一个函数 f(k)去估计
    wenxw1997
        42
    wenxw1997  
       2016-11-28 21:27:17 +08:00 via Android
    上面的命题应该补上 n→∞
    innoink
        43
    innoink  
       2016-11-28 21:44:54 +08:00
    我数学已经还给老师了。。不过看偶数坐标的图像。。感感觉很像卡方分布的一种图像。。
    innoink
        44
    innoink  
       2016-11-28 21:53:05 +08:00
    你说的约数算不算 1 和本身?
    qinjiannet
        45
    qinjiannet  
    OP
       2016-11-28 21:55:20 +08:00
    @innoink 算 1 和本身
    Mistwave
        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 均等势(可以理解为集合大小一样),所以无论拥有几个约数的自然数集,都是等势的。

    所以楼主的命题是不成立的。
    netzzx
        47
    netzzx  
       2016-11-28 23:26:40 +08:00
    为什么不改为考虑前 N 个自然数中有四个约数的自然数所占的比例呢? 这不就躲过去无穷集合的势的问题了么
    jasonding
        48
    jasonding  
       2016-11-29 10:21:42 +08:00
    任意一个奇数素数乘以 2 得到的结果都只有 4 个约数
    jasonding
        49
    jasonding  
       2016-11-29 10:24:56 +08:00
    哦,不限于奇数,任意一个素数乘以 2 的结果都是只有 4 个约数的
    rrfeng
        50
    rrfeng  
       2016-11-29 11:27:56 +08:00
    @jasonding 偶素数只有一个哈哈哈
    oldj
        51
    oldj  
       2016-11-29 11:31:48 +08:00
    @jasonding 这么说起来其实任意两个素数的积,都有 4 个约数。比如 a 、 b 是两个素数,且 a≠b ,那么它们的积的约数有:{1, a, b, a*b }。
    rrfeng
        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 个素数的积……编不下去了……
    reture
        53
    reture  
       2016-11-29 14:06:40 +08:00
    qinjiannet
        54
    qinjiannet  
    OP
       2016-11-29 16:15:42 +08:00
    @reture 这个是整数的不重复质因子的数目吧?
    jasonding
        55
    jasonding  
       2016-11-30 09:55:30 +08:00
    @oldj 恩,是这样的。
    phpcyy
        56
    phpcyy  
       2016-11-30 11:07:59 +08:00
    @DiamondbacK 请问素数和合数等势吗?素数的势是不是小于合数?
    DiamondbacK
        57
    DiamondbacK  
       2016-11-30 11:54:18 +08:00
    @phpcyy 素数集、合数集都与整数集等势。可数集的无限子集统统等势。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1048 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 71ms · UTC 22:35 · PVG 06:35 · LAX 15:35 · JFK 18:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.