问简微 问简微
不许在我的帖子或有我在的楼层下方发带有侮辱本人的字眼的评论,或者把哈基米歌曲奉为圭臬的评论,否则一律删除,举报并强拉黑,并说一句没3868
关注数: 15 粉丝数: 227 发帖数: 1,833 关注贴吧数: 23
衡量一个数合成性的另一个指标:“高度拆分性” 将1/n拆成三个不同的埃及分数和的形式,也就是1/n=1/x+1/y+1/z(x, y, z, n∈N*,x<y<z),给定n,记对应的解的数量为φ(n) 对于正整数N,如果任意正整数n<N都有φ(n)<φ(N),则称N为“高度拆分数”,或者“高拆分数” 比如1只能拆成1/2+1/3+1/6,则φ(1)=1 1/2对应有1/3+1/7+1/42, 1/3+1/8+1/24, 1/3+1/9+1/18, 1/3+1/10+1/15, 1/4+1/5+1/20, 1/4+1/6+1/12总共6种拆法,则φ(2)=6,而φ(1)<φ(2),则2为“高拆分数” 1/3对应15种拆法,则φ(3)=15, 而φ(1), φ(2)均小于φ(3),则3为“高拆分数” 2000以内的“高拆分数”有以下这些: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 42, 45, 48, 56, 60, 84, 90, 105, 120, 140, 168, 180, 210, 240, 252, 280, 315, 336, 360, 420, 630, 660, 720, 840, 1260, 1680 我们可以发现,其中有很多都是“高合成数”,并且,除此之外,其余的数的合成性都是比较强的,有一些奇数以及不是3的倍数的偶数也在这个列表里 但是φ(n)极为复杂,没有初等的表达式,有时候,数比较大的情况需要借助Python语言来帮我们计算总数,时间复杂度为O(n²),在数值达到几千的时候,甚至需要得等好久才能出来,程序写出来之后,我只是挑选了其中的若干个代表性的(因数比较多的)进行验证,忽视了数海里因数比较少的较大数,所以,结果可能不是那么可靠
1/a+1/b+1/c=1/n情况数 在网上经常看到的问题,把一个埃及分数拆成三个埃及分数之和,也就是把1/n拆成1/a+1/b+1/c(a<b<c且a, b, c∈N*),这个问题很好解决,只需要套公式1/k=1/(k+1)+1/k(k+1)即可 现在我把这个问题进行升级,问1/a+1/b+1/c=1/n(n, a, b, c∈N*,a<b<c)中,对某个特定的n,总共有多少种不同的方法,记ψ(n)为相应的方法数,我们不妨从比较小的情况开始: n=1时,只有一组解(a, b, c)=(2, 3, 6), 则ψ(1)=1 n=2时,总共有6组解(a, b, c)=(3, 7, 42), (3, 8, 24), (3, 9, 18), (3, 10, 15), (4, 5, 20), (4, 6, 12), 则ψ(2)=6 n=3时,解的数量明显增多,因为1/3=1/4+1/12,12具有高合成性,1/12拆成两个埃及分数之和的情况数就有7种,不难发现,n=3对应的情况有(a, b, c)=(4, 13, 156), (4, 14, 84), (4, 15, 60), (4, 16, 48), (4, 18, 36), (4, 20, 30), (4, 21, 28), (5, 8, 120), (5, 9, 45), (5, 10, 30), (5, 12, 20), (6, 7, 42), (6, 8, 24), (6, 9, 18), (6, 10, 15)总共7+4+4=15种情况,ψ(3)=15 我们可以发现,随着n的增大,由于我们需要讨论a的范围在n到3n之间,且不包含n和3n,总共2n-2个数,并且其中的某一些对应的情况没解,所以,讨论的复杂性也在逐渐增大 到了n=4, 就更复杂了,1/4减去1/5, 1/6, 1/7, 1/8, 1/9, 1/10分别是1/20, 1/12, 3/28, 1/8, 5/36, 3/20,并且3/28, 5/36和3/20都不是埃及分数,所以需要单独拎出来讨论,而n=4, a=11对应的情况无解,我们可以发现有(a, b, c)=(5, 21, 420), (5, 22, 220), (5, 24, 120), (5, 25, 100), (5, 28, 70), (5, 30, 60), (5, 36, 45), (6, 13, 156), (6, 14, 84), (6, 15, 60), (6, 16, 48), (6, 18, 36), (6, 20, 30), (6, 21, 28), (7, 10, 140), (7, 12, 42), (7, 14, 28), (8, 9, 72), (8, 10, 40), (8, 12, 24), (9, 12, 18), (10, 12, 15), 则ψ(4)=22 n=5情况数就更多了,1/5=1/6+1/30,光是一个1/30就有13种拆法,1/5-1/7=2/35,2/35对应4种拆法,1/5-1/8=3/40,3/40有(14, 280), (15, 120), (16, 80), (20, 40), (24, 30)这5种,此外还有(9, 12, 180), (9, 15, 45), (9, 18, 30), 1/10的4种,以及(12, 15, 20)总共30种,ψ(5)=30 n越大,情况越复杂,但是好像没有能够表达ψ(n)的通项公式或者递推公式,试问,复杂度如何去分析
一个结论,关于埃及分数和 把1/k(k∈N*)拆成n个埃及分数和,值最小的分数(也就是分母最大的分数)的分母Aₙ可能的最大值满足递推关系Aₙ₊₁=Aₙ(Aₙ+1),A₁=k,这个递推关系的通项无法用初等函数表示 我们可以知道Aₙ|Aₙ₊₁ 那么,有一个问题:已知P为素数 是否存在N, n≥N时,有P|Aₙ恒成立 比如P=7时,我们可以进行模7运算: k≡1时,A₁≡1, A₂≡1*2=2, A₃≡2*3=6, A₄≡6*7≡0 由于Aₙ|Aₙ₊₁, 所以k=1时,n≥4时Aₙ一定能被7整除 同时得知k≡2的情况同样满足给定N,当n≥N时7|Aₙ k≡3时,3*4≡5, 5*6≡2,又回到k≡2的情况了 k≡4时,4*5≡6, 6*7≡0,可知k=5, 6时会得到同样的结果 所以P=7时,任意k∈N这个结论一定成立 补充一个结论,就是对于模P(P为素数)运算,k(k+1)与(P-k-1)(P-k)同余,所以A₁=k和A₁=P-k-1的情况是等同的,所以考虑是否存在N,n≥N时,P|Aₙ的问题,只需要考虑1≤k≤(P-1)/2的情况即可 由于A₂=A₁(A₁+1), A₃=A₂(A₂+1),A₂+1=A₁²+A₁+1, Aₙ₊₁+1=Aₙ²+Aₙ+1,所以,Aₙ₊₁/Aₙ(n≥2)包含的因数只能是3或者6k+1形状的,又因为k(k+1)(k²+k+1)一定是3的倍数(也就是A₃一定是3的倍数,P=3时结论一定成立),所以Aₙ₊₁/Aₙ(n≥3)包含的因数只能是6k+1形状的,所以,P为6k+5形状的素数时,结论不成立 我们再考虑P=13:模13运算,只需要1≤k≤6的情况: k=1: 1*2≡2, 2*3≡6, 6*7≡3, 3*4≡12, 12*13≡0,同理对k=2, 3, 6成立; k=4: 4*5≡7, 7*8≡4,循环了,同理k=5, 7, 8也会出现循环 P=19:模19运算,只需考虑1≤k≤9: k=1: 1*2≡2, 2*3≡6, 6*7≡4, 4*5≡1(循环,k=2, 4, 6同样出现循环) k=3: 3*4≡12, 12*13≡4, 4*5≡1(循环) k=5: 5*6≡11, 11*12≡18(接下来整除,k=7同理) k=8: 8*9≡15(与k=3等效,循环) k=9: 9*10≡14(与k=4等效,循环) 貌似每个P=6K+1(7除外), 总有一部分最终会被P整除,有一部分则陷入循环,永远不会整除,那么,对于这个结论,只有P=2, 3, 7才对任意k都成立,其他的素数,应该如何去考虑
我在网上看到的一道题,据说是未解之谜,下面是我自己的看法 也就是对于任意正整数n≥3,1/x+1/y+1/z=4/n均存在正整数解(x, y, z)满足条件 这是我在网上看到的,在B站刷视频的时候看到的,那位视频的博主说他依然是未解之谜,接下来是我自己的看法: 不妨采用分类讨论法: n为4的倍数时,记n=4k, 则4/n=1/k,由于1/k可以使用万能公式1/k=1/(k+1)+1/k(k+1)=1/(k+2)+1/(k+1)(k+2)+1/k(k+1)拆解,所以n=4k时一定存在正整数解 n为偶数,但不是4的倍数时,记n=4k+2, 则4/n=2/(2k+1)=(2k+2)/(2k+1)(k+1)=(1+(2k+1))/(2k+1)(k+1)=1/(2k+1)(k+1)+1/(k+1)=1/(2k+1)(k+1)+1/(k+2)+1/(k+1)(k+2),也一定存在正整数解 则n为偶数时,一定存在正整数解 下面只需要考虑n为奇数的情况: 不妨优先考虑n除以4余3的情况:n=4k-1, 则4/n=4/(4k-1)=4k/k(4k-1)=(1+4k-1)/k(4k-1)=1/k(4k-1)+1/k=1/k(4k-1)+1/(k+1)+1/k(k+1),一定存在正整数解 n为合数时,n存在因数p≥5,不妨记n=pq, 则4/n=4/pq=1/q·4/p, 可知假若n=p满足条件,则n=pq也满足条件 注意到4/9=1/3+1/9=1/3+1/10+1/90=1/4+1/9+1/12=1/3+1/12+1/36,则n为3的正整数次幂时,一定存在正整数解 所以,只需要证明所有的4k+1型的素数满足条件即可 不妨记n=4k+1, 则4/n=4/(4k+1)=4(k+1)/(4k+1)(k+1)=(3+4k+1)/(4k+1)(k+1)=1/(k+1)+3/(4k+1)(k+1) k=3u-1时,n一定为3的倍数,3/(4k+1)(k+1)=1/3u(4u-1),此时一定存在正整数解,于是,n为3的倍数时,一定存在正整数解 k=3u+1时,3/(4k+1)(k+1)=3/(12u+5)(3u+2)=3/(36u²+39u+10)=3/((36u²+39u+6)+4) u=2v时,36u²+39u+6一定为6的倍数,记为6A, 3/(6A+4)=1/2·3/(3A+2)=1/2·(3(A+1)/(A+1)(3A+2))=1/2·((3A+2+1)/(A+1)(3A+2))=1/2·(1/(A+1)+1/(A+1)(3A+2))=1/2(A+1)+1/2(A+1)(3A+2), 此时n=4k+1=12u+5=24v+5 同理,k=3u, u=2v+1时,(4k+1)(k+1)=6B+4,同样存在正整数解,此时n=24v+13 由于Z/24Z的单位群为{1, 5, 7, 11, 13, 17, 19, 23}, 由于7, 11, 19, 23, 5, 13的情况均已讨论,只需要证明所有的24v+1以及24v+17的素数成立即可,也就是8k+1形状的素数成立即可 注意到3/(4k+1)(k+1)=1/(k+1)·3/(4k+1), 而4k+1=24v+17时,k=6v+4, 3/(4k+1)(k+1)=1/(6v+5)·3/(24v+17)=1/(6v+5)·(3(8v+6)/(8v+6)(24v+17))=1/(6v+5)·(1/(8v+6)+1/(8v+6)(24v+17)),则对于n=24v+17的情况一定存在正整数解 这个时候,情况讨论缩小到了只需要讨论n=24v+1型的素数的情况 24v+1型的素数有:73, 97, 193, 241, 313, 409, 433, 457, 577, 601, 673, 769, 937, 1009等 当k+1存在(3u+2)形状的素因数时,可以知道一定存在正整数解(读者自己证明),若k+1不存在(3u+2)形状的素因数,则x=k+1时不存在相应的解,(不妨使用下面的证明方法证明: 3/(Πᵢ₌₁ⁿ pᵢ)=1/y+1/z, 其中pᵢ=3kᵢ+1时,记Πᵢ₌₁ⁿ pᵢ=K, 则3/K=1/y+1/z=(y+z)/yz, 则3yz=K(y+z), (3y-K)(3z-K)=K², 而3y-K≡3z-K≡2(mod 3), 而K²没有3k+2形状的因数,所以,在这种情况下,没有相应的解) 这样,我们可以继续缩小需要考虑的范围 比如n=73时,(n+3)/4=19不存在(3k+2)形状的因数,则需要考虑别的x, x=20时,1/y+1/z=4/73-1/20=7/(20*73)=(5+2)/(20*73)=1/292+1/730 则4/73=1/20+1/292+1/730 n=97时,(n+3)/4=25, 25可以被5整除 接下来的证明非常复杂,燃尽了
1 下一页