网站logo优化,wordpress 关键词,wordpress网站定制,网站提示代码容斥原理是一种计数方法#xff0c;用于计算多个集合的并集中元素的个数#xff0c;以避免重复计算。以下是其基本内容及相关公式#xff1a; 两个集合的容斥原理 若有集合A和集合B#xff0c;那么A与B的并集中元素的个数等于A集合元素个数加上B集合元素个数#xff0c;再…容斥原理是一种计数方法用于计算多个集合的并集中元素的个数以避免重复计算。以下是其基本内容及相关公式 两个集合的容斥原理 若有集合A和集合B那么A与B的并集中元素的个数等于A集合元素个数加上B集合元素个数再减去A与B交集的元素个数即|AUB| |A||B|-|A∧ B|。 例如一个班级中喜欢数学的有30人喜欢语文的有25人既喜欢数学又喜欢语文的有10人。那么喜欢数学或语文的人数为30 25-1045人。 三个集合的容斥原理 对于集合A、B、C它们的并集中元素个数公式为|AUBUC||A||B||C|-|A∧ B|-|A∧ C|-|B∧ C| |A∧ B∧ C|。 例如在某学校的社团活动中参加音乐社团的有50人参加绘画社团的有40人参加体育社团的有35人。同时参加音乐和绘画社团的有15人同时参加音乐和体育社团的有10人同时参加绘画和体育社团的有8人三个社团都参加的有3人。则参加社团的总人数为5040 35-15-10-8395人。 可以把容斥原理推广到一般情况(略)。 容斥原理在组合数学、概率论、数论等领域都有广泛应用比如在计算排列组合问题中满足特定条件的排列数或在概率计算中求多个事件至少发生一个的概率等。 下面介绍容斥原理在自然数集中的应用一一欧拉函数φ(n)。符号φ(n)表示n以内的与n互质的自然数个数。
如求10以内的与10互质的自然数(除0外)。
过程:{12345678910}。因为102X5被2整除的自然数个数有10÷25与2互质的自然数个数为10(1-1/2)5。被5整除的自然数有10÷52个与5互质的自然数个数有10(1-1/5)8。所以同时与2和5都互质的自然数个数有10(1~1/2)(1-1/5)4。即φ(10)4。
把φ(n)可以推广到任意连续的n个自然数中计算结果与n以内的与n互质的自然数个数是相同的。如{891011121314151617}φ(1o)4即与10互质的数有9111317。 也可以把欧拉函数φ(n)推广到等差数列中如奇数集A:{135…2n-1}。A中n个元素与n互质的元素个数是φ(n)。
因为A中所有元素都与2互质计算φ(n)时先把n分解因数化为质数幂之积的形式由容斥原理再计算结果。如:φ(10)A中10个元素与10互质的元素{137911131719}即φ(10)10(1-1/5)8。推广到任意连续的10个元素中如(9111315171921232527}中与1θ互质的元素{911131719212327}即φ(10)10(1-1/5)8。
进一步把欧拉函数应用到素数的存在数域孪生素数的存在数域和哥德巴赫猜想的存在数域中能给n以内的素数个数的近似函数表示式孪生素数个数的近似函数表示式和2n表两个素数之和的哥德巴赫猜想的“11“个数表示式。具体介绍如下 ①素数个数的表示式
数域A:{123…nn1…m}其中m2x3x5…xp(连续素数之积)p为素数p^2≤n那么A中与m互质的数个数为φ(m)(2-1)(3-1)(5-1)…(p-1)。设A(n)表示n以内的与m互质的数的个数即A(n)表示了n以内的素数个数(包含1但不包含23…p的个数。由于A(n)/n≈φ(m)/m所以
A(n)≈n(1-1/2)(1-1/3)…(1-1/p)。
②孪生素数的个数表示式
设数域B:{(-11)(02)(13)…(n-2n)…(m-2m)}其中m2x3x5…xp(连续素数之积)p为素数p^2≤n那么B中与m互质的元素个数为φ(m)(2-1)(3-2)(5-2)…(p-2)。设B(n)表示n以内的与m互质的元素的个数即B(n)表示了n以内的孪生素数个数(包含(-11)个数但不包含与23…p的互质的元素个数意义:p与元素互质指p与元素中的两个数都互质)。由于B(n)/n≈φ(m)/m所以 B(n)≈n(1-1/2)(1-2/3)…(1-2/p)。 ③哥德巴赫猜想的“11个数表示式 设数域C:{(12n-1)(22n-2)(32n-3)…(2n-nn)…(m2n-m)}其中m2x3x5…xp(连续素数之积)p为素数p^2≤2n那么C中与m互质的元素个数为φ(m)(2-1)(3-r2)(5-r3)…(p-rt)其中当p|2n时rt1当p不整除2n时rt2。设C(2n)表示两素数之和的个数但不包含p以内素数的“11″个数即C(2n)表示了C中n以内的(素数素数)个数包含(12n-1)为(1素数)时的个数但不包含与23…p的互质的元素个数(意义:p与元素互质指p与元素中的两个数都互质)。由于C(2n)/n≈φ(m)/m所以 C(n)≈n(1-1/2)(1-r2/3)…(1-rt/p)。 欧拉函数还有许多应用在筛除合数方面应用欧拉函数形成了固定的方法:欧拉函数筛法。欧拉函数筛法在筛取素数孪生素数哥德巴赫猜想的“11方面比埃氏筛法更为先进。如
100199298筛去含2因子的和得
100199397595再筛去含3因子的和得
1005951189178323772971
筛去含5因子的和得
1001189178323772971
4159475353475941…
筛去含7因子的和得
100118917832971
41594753。由于筛去100397于是
100397118917832971
41594753。
所以100表两个素数之和的个数为6。(李扩继)
