Mersenne Sieve


by arydberg
Tags: mersenne, sieve
arydberg
arydberg is offline
#1
Jan15-13, 03:40 PM
P: 73
Following is a list of 39 Mersenne numbers. Some are prime and some are not. These are generated with x =( 2^n) -1. Many of the largest primes known are Mersenne primes.

I would like to point out that a sieve may be used to block out many non prime Mersenne numbers.

For example for n = 2 x = 3 but on closer inspection every even value of n other than n = 2 is non prime furthermore they are all divisible by 3, Thus we can cross out n=4, n=6, … up to n=38.

Also starting at n=3 and x = 7 we find that every third number larger than 3 is divisible by 7 so we could cross out n = 6, n=9, n=12 … up to n = 39.

Now lets move to n=5 or x = 31. now we can cross out every fifth number larger than n=5 as they are all divisible by 31

if we move to n=7 and x = 127 we find that every 7th number larger than 7 is divisible by 127 and can be crossed out.

11 should be crossed off as 2047 is not prime

My question is does this go on forever and can we use it to delete many Mersenne numbers as non primes.



The next prime is 11
n 2^n - 1
n = 1 x = 1
n = 2 x = 3
n = 3 x = 7
n = 4 x = 15
n = 5 x = 31
n = 6 x = 63
n = 7 x = 127
n = 8 x = 255
n = 9 x = 511
n = 10 x = 1023
n = 11 x = 2047
n = 12 x = 4095
n = 13 x = 8191
n = 14 x = 16383
n = 15 x = 32767
n = 16 x = 65535
n = 17 x = 131071
n = 18 x = 262143
n = 19 x = 524287
n = 20 x = 1048575
n = 21 x = 2097151
n = 22 x = 4194303
n = 23 x = 8388607
n = 24 x = 16777215
n = 25 x = 33554431
n = 26 x = 67108863
n = 27 x = 134217727
n = 28 x = 268435455
n = 29 x = 536870911
n = 30 x = 1073741823
n = 31 x = 2147483647
n = 32 x = 4294967295
n = 33 x = 8589934591
n = 34 x = 17179869183
n = 35 x = 34359738367
n = 36 x = 68719476735
n = 37 x = 137438953471
n = 38 x = 274877906943
n = 39 x = 549755813887
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
RamaWolf
RamaWolf is offline
#2
Jan15-13, 11:28 PM
P: 96
You should look at: http://en.wikipedia.org/wiki/Mersenne_primes

There you can see, that n in your notatation must be prime to let 2**n - 1 be prime
RamaWolf
RamaWolf is offline
#3
Jan16-13, 04:45 AM
P: 96
As a consequence of Theorem 18 from Hardy-Wright, we have the following

Corollary: For two natural numbers 1 < a and b: a[itex]{^b}[/itex] - 1 is composite if a > 2 (because (a - 1) divides a[itex]^{b}[/itex] - 1);
or in the case a = 2: if b = s * t (because 2[itex]^{s}[/itex] - 1 divides 2[itex]^{s*t}[/itex] - 1

arydberg
arydberg is offline
#4
Jan16-13, 02:31 PM
P: 73

Mersenne Sieve


yes but consider the number 11 which is a prime while 2^11 -1 is not a prime.
arydberg
arydberg is offline
#5
Jan16-13, 02:33 PM
P: 73
yes but this does not help
RamaWolf
RamaWolf is offline
#6
Jan17-13, 03:03 AM
P: 96
I think, my Corollary helps to delete all 2[itex]{^b}[/itex] - 1 with a composite b; but unfortunately, there is no help for sieving the Mersenne primes:

Theorem 18 by HW says (in short): 'If 2[itex]{^b} - 1[/itex] is a prime, then b is a prime'; and the 'other way round' is not valid
arydberg
arydberg is offline
#7
Jan17-13, 08:06 AM
P: 73
To show that (X^(2*n) ) - 1 has a factor of x-1 for any n.


Consider x^2 - 1 = (x-1) * (x+1 )

so if x^2 -1 is a factor of a function then x-1 is a factor.

Consider x^4 - 1 = ( x^2 -1 ) * ( x^2 + 1 )

so x-1 is a factor of x^4 -1

consider x^6 - 1 = (x^2 -1 ) * ( x^4 + x^2 + 1 )

so x-1 is a factor of x^6 -1

consider x^8-1 = ( x^2 -1 ) * ( x^6 + x^ 4 + x^ 2 + 1 )

so x-1 is a factor of x^8 -1
etc

So it seems to me…

x^(2*n) - 1 = (x^2 -1 ) * ( x^(2*(n-1)) + x^(2 * (n-2)) + ……. + 1 )


Register to reply

Related Discussions
A new prime sieve Linear & Abstract Algebra 23
Twin Prime Sieve Linear & Abstract Algebra 2
Goldbach’s Conjecture and the 2-Way Sieve General Math 6
Sieve of Eratosthenes - Programming in VB Computing & Technology 14