素数吧 关注:868贴子:5,337
  • 0回复贴,共1

只用加法验证梅森素数或求整数的分解式

只看楼主收藏回复

  1.需要用到的是整数列“1,2,3,…,n”的累计和值表作为参照表:
  如 S1=1 S2=3 S3=6 S4=10 S5=15 S6=21 …Sn=(n+1)n/2
  2.这种方法依据的原理是:任意奇数(且大于3)如果非质数,
   那么其必定可以表示为一组由三个或三个以上的连续整数组成的数列,
   数列的和值等于该整数,例如:9=2+3+4,15=1+2+3+4+5。
  简单证明如下:
   如果有奇数Z=AB,Z>3,其中A<=B,A与B均为奇数;
   一组连续的整数列是“N,N+1,N+2,…,N+X”其中X>=2,其和值为(N+N+X)(N+X-N+1)/2,
   AB=(N+N+X)(N+X-N+1)/2=(2N+X)(X+1)/2,其中N与X必有解。
   其解为:当B/A>2时有 X=2A-1 N=(B+1)/2-A
       当B/A<2时有 X=B-1 N=A-(B-1)/2
       总有 X=A-1 N=B-(A-1)/2
  3.下面开始验证奇数是否质数
   将待验证的任意奇数Z(且大于3),对照累计和值表,
   情况一、如果奇数Z(且大于3)等于某个累计和值则一定是非质数,两个约数分别是n与(n+1)/2;
   如果奇数Z(且大于3)不等于某个累计和值,则必定介于两个累计和值之间,有Sn-1<Z<Sn,
   令Z与Sn的差为x,那么有Z=(n+1)n/2-x,
   情况二、将x值对照累计和值表,如果x等于某个累计和值,即有x=(y+1)y/2,
   那么有Z=(n+1)n/2-(y+1)y/2=(y+1+n)(n-y)/2,只要满足(n-y)>=3,
   其中(y+1+n)与(n-y)必定分别是一奇一偶,
   当中的奇数是Z的公约数,当中的偶数除以2是Z的另一个公约数。
   情况三、将x值对照累计和值表,x也不等于某个累计和值,
   那么可以x+(n+1),将x+(n+1)值再次对照累计和值表,
   看x+(n+1)值是否如“情况二”等于某个累计和值,等于的话则如法分解;
   如果仍然不等于的话,则依然可以继续用x+(n+1)+(n+2)值对照累计和值表,反复递加对照。
   如果直至“x+(n+1)+(n+2)+…+(n+y)”的值>Z/3时,
   仍然没出现等于某个累计和值的情况则Z是质数。
   上面的过程其实就是
   由 p(p+1)/2=x+(n+y+n+1)(n+y-n-1+1)/2
   得 p(p+1)=2x+(2n+y+1)y
   求上面的以p和y为未知数的二元二次方程是否存在正整数解。


IP属地:广东1楼2018-06-17 11:07回复