33,007
社区成员
发帖
与我相关
我的任务
分享关于互质的概率问题，不要小看
题目： 从正整数中随机地两个数，两个数互质的概率为多少？
怎么用计算机模拟
关键问题是如何取到所有的正整数，或者有什么等价的方法
怎么用计算机模拟
关键问题是如何取到所有的正整数，或者有什么等价的方法
...全文
请发表友善的回复…
发表回复
phoenixinter 2005-08-04
- 打赏
- 举报
概率应该是6/Pi^2
详细的proof可以参见TAOCP Vol 2
详细的proof可以参见TAOCP Vol 2
Leopard79 2005-07-28
- 打赏
- 举报
这个我不太知道怎么回事:(
不过他要求得是概率（本身属于古典概率类型的），而概率是在一定范围S之内的！
因而扩大到整个自然数，就要求S = N（N时自然数)，直接在无限中求概率好像没听说过！
不过他要求得是概率（本身属于古典概率类型的），而概率是在一定范围S之内的！
因而扩大到整个自然数，就要求S = N（N时自然数)，直接在无限中求概率好像没听说过！
ZeroGts 2005-07-26
- 打赏
- 举报
我也这样想过。但是各数的倍数有重复，有点不同。
在有限范围内，英文的那段肯定是正确的；但如果在无限的范围内，我觉得我的也没错，英文的也有道理。你能直接从我那段找到错误吗？这难道是所谓悖论呢？
在有限范围内，英文的那段肯定是正确的；但如果在无限的范围内，我觉得我的也没错，英文的也有道理。你能直接从我那段找到错误吗？这难道是所谓悖论呢？
Leopard79 2005-07-26
- 打赏
- 举报
g_c_b(2,3)=1对应 g_c_b(2*2,3*2)=2, g_c_b(2*3,3*3)=3, g_c_b(2*4,3*4)=4, ...
g_c_b(4,7)=1对应 g_c_b(4*2,7*2)=2, g_c_b(4*3,7*3)=3, g_c_b(4*4,7*4)=4, ...
g_c_b(12,25)=1对应 g_c_b(12*2,25*2)=2, g_c_b(12*3,25*3)=3, g_c_b(12*4,25*4)=4, ...
...
这样，每对g_c_b(a,b)=1都对应无穷多的数对g_c_b(a*d,b*d)=d，d=2,3,4...
所以d=1,2,3,...的概率是相等的。
--------------------------------
对不起，我没有仔细看你写的，你说的:每对g_c_b(a,b)=1都对应无穷多的数对g_c_b(a*d,b*d)=d，d=2,3,4...是对的，但是:所以d=1,2,3,...的概率是相等的,我感觉不对！
不要说得太多了，我举个例子你看看：
比如：
我在自然数中任选个数是3的倍数的概率p3(p3 = 1 / 3)和我在自然数中任选个数的概率p(p = 1)，你说这两个相等吗？设自然数n，只要它乘以3就会得到3的倍数（一个n对应一个3n），那么这两个数的概率相等吗？
你再对应：
我在自然数中任选两个数的g_c_d(u, v) = 3的概率p3和我在自然数中任选两个数的g_c_d(u, v) = 1的概率p，你现在认为它们相等吗？
g_c_b(4,7)=1对应 g_c_b(4*2,7*2)=2, g_c_b(4*3,7*3)=3, g_c_b(4*4,7*4)=4, ...
g_c_b(12,25)=1对应 g_c_b(12*2,25*2)=2, g_c_b(12*3,25*3)=3, g_c_b(12*4,25*4)=4, ...
...
这样，每对g_c_b(a,b)=1都对应无穷多的数对g_c_b(a*d,b*d)=d，d=2,3,4...
所以d=1,2,3,...的概率是相等的。
--------------------------------
对不起，我没有仔细看你写的，你说的:每对g_c_b(a,b)=1都对应无穷多的数对g_c_b(a*d,b*d)=d，d=2,3,4...是对的，但是:所以d=1,2,3,...的概率是相等的,我感觉不对！
不要说得太多了，我举个例子你看看：
比如：
我在自然数中任选个数是3的倍数的概率p3(p3 = 1 / 3)和我在自然数中任选个数的概率p(p = 1)，你说这两个相等吗？设自然数n，只要它乘以3就会得到3的倍数（一个n对应一个3n），那么这两个数的概率相等吗？
你再对应：
我在自然数中任选两个数的g_c_d(u, v) = 3的概率p3和我在自然数中任选两个数的g_c_d(u, v) = 1的概率p，你现在认为它们相等吗？
ZeroGts 2005-07-25
- 打赏
- 举报
我说的(a,b)是包括这个g_c_d(2*2, 3*3) = 1
但你说什么“又出现了”？(a,b)组合的概率为什么不相等？
但你说什么“又出现了”？(a,b)组合的概率为什么不相等？
Leopard79 2005-07-25
- 打赏
- 举报
你说没这个？
g_c_d(2*2, 3*3) = 1 ，这个说明这两个数是互质的阿，如果你上面的例子不包括这个的话，只能说明你求出来的p是错误的是不完全！
g_c_d(2*2, 3*3) = 1 ，这个说明这两个数是互质的阿，如果你上面的例子不包括这个的话，只能说明你求出来的p是错误的是不完全！
ZeroGts 2005-07-23
- 打赏
- 举报
没有这个啊：g_c_d(2*2, 3*3) = 1 ……
Leopard79 2005-07-22
- 打赏
- 举报
就拿你其中的一个例子来说吧！
g_c_b(2,3)=1对应 g_c_b(2*2,3*2)=2, g_c_b(2*3,3*3)=3, g_c_b(2*4,3*4)=4, ...
g_c_d(2*2, 3*3) = 1 其中2*2和3*3是在你上面的式子中拿出来的，但是它们的组合却是个互质的，这些数在你的
g_c_d(2*2, 3*3) = 1 g_c_d(2*2*2, 3*3*2) = 2 g_c_d(2*2*3, 3*3*3) = 3 ....
这些式子中又出现了阿！
在自然数中，每个数字出来的概率才是相等的，它们组成关系的集合是不等的！
g_c_b(2,3)=1对应 g_c_b(2*2,3*2)=2, g_c_b(2*3,3*3)=3, g_c_b(2*4,3*4)=4, ...
g_c_d(2*2, 3*3) = 1 其中2*2和3*3是在你上面的式子中拿出来的，但是它们的组合却是个互质的，这些数在你的
g_c_d(2*2, 3*3) = 1 g_c_d(2*2*2, 3*3*2) = 2 g_c_d(2*2*3, 3*3*3) = 3 ....
这些式子中又出现了阿！
在自然数中，每个数字出来的概率才是相等的，它们组成关系的集合是不等的！
ZeroGts 2005-07-22
- 打赏
- 举报
补充：
这些数对不重复也不遗漏。
这些数对不重复也不遗漏。
ZeroGts 2005-07-22
- 打赏
- 举报
接上面的上面：
g_c_b(2,3)=1对应 g_c_b(2*2,3*2)=2, g_c_b(2*3,3*3)=3, g_c_b(2*4,3*4)=4, ...
g_c_b(4,7)=1对应 g_c_b(4*2,7*2)=2, g_c_b(4*3,7*3)=3, g_c_b(4*4,7*4)=4, ...
g_c_b(12,25)=1对应 g_c_b(12*2,25*2)=2, g_c_b(12*3,25*3)=3, g_c_b(12*4,25*4)=4, ...
...
这样，每对g_c_b(a,b)=1都对应无穷多的数对g_c_b(a*d,b*d)=d，d=2,3,4...
所以d=1,2,3,...的概率是相等的。
g_c_b(2,3)=1对应 g_c_b(2*2,3*2)=2, g_c_b(2*3,3*3)=3, g_c_b(2*4,3*4)=4, ...
g_c_b(4,7)=1对应 g_c_b(4*2,7*2)=2, g_c_b(4*3,7*3)=3, g_c_b(4*4,7*4)=4, ...
g_c_b(12,25)=1对应 g_c_b(12*2,25*2)=2, g_c_b(12*3,25*3)=3, g_c_b(12*4,25*4)=4, ...
...
这样，每对g_c_b(a,b)=1都对应无穷多的数对g_c_b(a*d,b*d)=d，d=2,3,4...
所以d=1,2,3,...的概率是相等的。
Leopard79 2005-07-22
- 打赏
- 举报
对于任意g_c_d(a,b)=1的数对(a,b)，a<>b，都可以对应无穷多的数对：
(2a,2b), (3a,3b), (4a,4b)...
有g_c_d(2a,2b)=2, g_c_d(3a,3b)=3, g_c_d(4a,4b)=4, ...
这些数对都不会重复，而且取得每一数对的概率都相等，那么
p+p+p+p...=1
则p->0。
a=b的情况忽略。
这样似乎也是正确的啊。
----------------------------------
取得每一对数的概率是都相等的(指的是个体)，但是他们之间g_c_d(u, v) = d的概率(指的是集合)是不等的!
p+p+p+p...=1 其中每个p是不同的！
(2a,2b), (3a,3b), (4a,4b)...
有g_c_d(2a,2b)=2, g_c_d(3a,3b)=3, g_c_d(4a,4b)=4, ...
这些数对都不会重复，而且取得每一数对的概率都相等，那么
p+p+p+p...=1
则p->0。
a=b的情况忽略。
这样似乎也是正确的啊。
----------------------------------
取得每一对数的概率是都相等的(指的是个体)，但是他们之间g_c_d(u, v) = d的概率(指的是集合)是不等的!
p+p+p+p...=1 其中每个p是不同的！
ZeroGts 2005-07-21
- 打赏
- 举报
但是如果我这样解：
对于任意g_c_d(a,b)=1的数对(a,b)，a<>b，都可以对应无穷多的数对：
(2a,2b), (3a,3b), (4a,4b)...
有g_c_d(2a,2b)=2, g_c_d(3a,3b)=3, g_c_d(4a,4b)=4, ...
这些数对都不会重复，而且取得每一数对的概率都相等，那么
p+p+p+p...=1
则p->0。
a=b的情况忽略。
这样似乎也是正确的啊。
对于任意g_c_d(a,b)=1的数对(a,b)，a<>b，都可以对应无穷多的数对：
(2a,2b), (3a,3b), (4a,4b)...
有g_c_d(2a,2b)=2, g_c_d(3a,3b)=3, g_c_d(4a,4b)=4, ...
这些数对都不会重复，而且取得每一数对的概率都相等，那么
p+p+p+p...=1
则p->0。
a=b的情况忽略。
这样似乎也是正确的啊。
ZeroGts 2005-07-21
- 打赏
- 举报
我明白那段英文说什么了，u是d的倍数的概率是1/d，v是d的倍数的概率也是1/d，所以g_c_d(u,v)=d的概率就是p/d^2。
Leopard79 2005-07-21
- 打赏
- 举报
Sorry!
它证明时... ===>他证明时...
它证明时... ===>他证明时...
Leopard79 2005-07-21
- 打赏
- 举报
它证明时集合扩展不是安照自然数来的(1, 2, 3, ...)，而是按照最大公约数来的!
g_c_d(u, v) = 1; 形成集合s1
g_c_d(u, v) = 2; 形成集合s2
...
g_c_d(u, v) = d; 形成集合sd
...
因为任意两个自然数u, v的都可以在s1, s2, ..., sd, ...中对应！
所以d趋于无穷时，对应于整个自然数！
如果g_c_d(u, v) = 1表明u, v是互质的，在整个自然数中它的概率为p
g_c_d(u，v) = 2表明它是由s1扩充而来的，现在的集合是s1 + s2，那么它在集合中的概率当然要把
当g_c_d(u, v) = 1时的两个互质的数包含进去了！那么它的概率就为p / 2^2，这也是表示g_c_d(u，v) = 2在整个任意两个自然数中的概率！
g_c_d(u, v) = 1; 形成集合s1
g_c_d(u, v) = 2; 形成集合s2
...
g_c_d(u, v) = d; 形成集合sd
...
因为任意两个自然数u, v的都可以在s1, s2, ..., sd, ...中对应！
所以d趋于无穷时，对应于整个自然数！
如果g_c_d(u, v) = 1表明u, v是互质的，在整个自然数中它的概率为p
g_c_d(u，v) = 2表明它是由s1扩充而来的，现在的集合是s1 + s2，那么它在集合中的概率当然要把
当g_c_d(u, v) = 1时的两个互质的数包含进去了！那么它的概率就为p / 2^2，这也是表示g_c_d(u，v) = 2在整个任意两个自然数中的概率！
ZeroGts 2005-07-20
- 打赏
- 举报
为什么the probability that g_c_d(u, v) = d is equal to l/d times l/d times p, namely p/d^2？
楼上说的为什么
(u/d)*1 (u/d)*2 ... (u/d)*(d-1) (u/d)*d m (d个中选一个) m要在(u/d)*1~(u/d)*d中选？
楼上说的为什么
(u/d)*1 (u/d)*2 ... (u/d)*(d-1) (u/d)*d m (d个中选一个) m要在(u/d)*1~(u/d)*d中选？
Leopard79 2005-07-20
- 打赏
- 举报
Thus the probability that
g_c_d(u, ZJ) = d is equal to l/d times l/d times p
这里怎么理解??
---------------------------------
他是通过求最大公约数的方法来证明的！
首先设两个数互质的概率为p！
再设两个数的最大公约数为d的概率为qd！有这个条件q1 + q2 + ... + qd + ... = 1
假设：g_c_d(u, v) = d （u，v的最大公约数为d，表明d是u和v的因子）
==>g_c_d(u/d, v/d) = 1；
(u/d)*1 (u/d)*2 ... (u/d)*(d-1) (u/d)*d m (d个中选一个)
(v/d)*1 (v/d)*2 ... (v/d)*(d-1) (v/d)*d n (d个中选一个)
P(g_c_d(m, n) = d) = 1 / d^2;
有条件概率可知
P(g_c_d(u, v) = d | g_c_d(u/d, v/d) = 1) * P(g_c_d(u/d, v/d) = 1) = P(g_c_d(u, v) = d)
试中：P(g_c_d(u, v) = d | g_c_d(u/d, v/d) = 1) = P(g_c_d(m, n) = d) = 1 / d^2;
P(g_c_d(u/d, v/d) = 1)两个数（u/d, v/d）互质的概率 = p
P(g_c_d(u, v) = d) = pd;
=====>1 / d^ * p = pd;
=====> p * (1 + 1 / 2^2 + 1 / 3^2 + ...) = 1;
.......
ps：其中至少有一个数等于一时，也会出现g_c_d(u, v) = 1的情况，但是由于1与整个自然数相比起来，就微乎其微了，所以用程序演示时，p的值是围绕6 / π^2 上下波动的，但是最终收敛于6 / π^2的！
g_c_d(u, ZJ) = d is equal to l/d times l/d times p
这里怎么理解??
---------------------------------
他是通过求最大公约数的方法来证明的！
首先设两个数互质的概率为p！
再设两个数的最大公约数为d的概率为qd！有这个条件q1 + q2 + ... + qd + ... = 1
假设：g_c_d(u, v) = d （u，v的最大公约数为d，表明d是u和v的因子）
==>g_c_d(u/d, v/d) = 1；
(u/d)*1 (u/d)*2 ... (u/d)*(d-1) (u/d)*d m (d个中选一个)
(v/d)*1 (v/d)*2 ... (v/d)*(d-1) (v/d)*d n (d个中选一个)
P(g_c_d(m, n) = d) = 1 / d^2;
有条件概率可知
P(g_c_d(u, v) = d | g_c_d(u/d, v/d) = 1) * P(g_c_d(u/d, v/d) = 1) = P(g_c_d(u, v) = d)
试中：P(g_c_d(u, v) = d | g_c_d(u/d, v/d) = 1) = P(g_c_d(m, n) = d) = 1 / d^2;
P(g_c_d(u/d, v/d) = 1)两个数（u/d, v/d）互质的概率 = p
P(g_c_d(u, v) = d) = pd;
=====>1 / d^ * p = pd;
=====> p * (1 + 1 / 2^2 + 1 / 3^2 + ...) = 1;
.......
ps：其中至少有一个数等于一时，也会出现g_c_d(u, v) = 1的情况，但是由于1与整个自然数相比起来，就微乎其微了，所以用程序演示时，p的值是围绕6 / π^2 上下波动的，但是最终收敛于6 / π^2的！
gxqcn 2005-07-20
- 打赏
- 举报
再重新排版一遍！
（上次发贴因为是直接从pdf上拷贝下来，没注意到有些符号出现乱码，影响了大家的阅读和理解）
[Theorem](G. Lejeune Dirichlet, Abhandlungen Kbniglich PreuB. Akad. Wiss.(1849), 69-83). If u and v are integers chosen at random, the probability that g_c_d(u, v) = 1 is 6/π^2 ≈.60793.
A precise formulation of this theorem, which carefully defines what is meant by being “chosen at random,” appears in exercise 10 with a rigorous proof. Let us content ourselves here with a heuristic argument that shows why the theorem is plausible.
If we assume, without proof, the existence of a well-defined probability p that g_c_d(u, v) equals unity, then we can determine the probability that g_c_d(u, TJ) = d for any positive integer d, because g_c_d(u, v) = d if and only if u is a multiple of d and v is a multiple of d and g_c_d(u/d, v/d) = 1. Thus the probability that g_c_d(u, v) = d is equal to l/d times l/d times p, namely p/d^2. Now let us sum these probabilities over all possible values of d; we should get
1 = ∑ p/d^2 = p(1 + 1/4 + 1/9 + 1/16 + . . . ).
d>l
Since the sum 1 + 1/4 + 1/9 + . . . = H∞(2) is equal to π^2/6 , we need p = 6/π^2 in order to make this equation come out right.
（上次发贴因为是直接从pdf上拷贝下来，没注意到有些符号出现乱码，影响了大家的阅读和理解）
[Theorem](G. Lejeune Dirichlet, Abhandlungen Kbniglich PreuB. Akad. Wiss.(1849), 69-83). If u and v are integers chosen at random, the probability that g_c_d(u, v) = 1 is 6/π^2 ≈.60793.
A precise formulation of this theorem, which carefully defines what is meant by being “chosen at random,” appears in exercise 10 with a rigorous proof. Let us content ourselves here with a heuristic argument that shows why the theorem is plausible.
If we assume, without proof, the existence of a well-defined probability p that g_c_d(u, v) equals unity, then we can determine the probability that g_c_d(u, TJ) = d for any positive integer d, because g_c_d(u, v) = d if and only if u is a multiple of d and v is a multiple of d and g_c_d(u/d, v/d) = 1. Thus the probability that g_c_d(u, v) = d is equal to l/d times l/d times p, namely p/d^2. Now let us sum these probabilities over all possible values of d; we should get
1 = ∑ p/d^2 = p(1 + 1/4 + 1/9 + 1/16 + . . . ).
d>l
Since the sum 1 + 1/4 + 1/9 + . . . = H∞(2) is equal to π^2/6 , we need p = 6/π^2 in order to make this equation come out right.
rickone 2005-07-20
- 打赏
- 举报
Thus the probability that
g_c_d(u, ZJ) = d is equal to l/d times l/d times p
这里怎么理解??
g_c_d(u, ZJ) = d is equal to l/d times l/d times p
这里怎么理解??
rickone 2005-07-20
- 打赏
- 举报
那个证明素数有无穷多个的证明是一个很有名的证明,在历史上,是数学上的经典证明之一.
加载更多回复（31）
