mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-05-19, 11:54   #1
allasc
 
Aug 2010
SPb

2×17 Posts
Default New test for Mersenne prime

Post of Russia
http://dxdy.ru/post447534.html#p447534

sequence in the OEIS
A190213

Numbers n such that a==0(mod k) and b==0(mod k), where k=2^n-1, m=(2^n-1)*(n-1)-n+2, x=m*(2^n-1), 2^(x-1)==(a+1)(mod x), m^(x-1)==(b+1)(mod x)

1, 3, 4, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217

EXAMPLE
n=3
k=2^3-1=7
m=(2^3-1)*(3-1)-3+2=13
x=m*(2^n-1)=13*7=91
2^(x-1)==(a+1)(mod x);2^90==(63+1)(mod 91), a=63
m^(x-1)==(b+1)(mod x);13^90==(77+1)(mod 91), b=77

test conditions
a==0(mod k), 63==0(mod 7)
b==0(mod k), 77==0(mod 7)
----------------------------------------

All odd numbers are of Mersenne exponents: primes n such that 2^n - 1 is prime A000043

4 is the only even number
why not 2? I do not know .....
allasc is offline   Reply With Quote
Old 2011-05-19, 12:51   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

3×47×71 Posts
Default

Uncwilly is offline   Reply With Quote
Old 2011-05-19, 13:39   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by allasc View Post
Post of Russia
http://dxdy.ru/post447534.html#p447534

sequence in the OEIS
A190213

Numbers n such that a==0(mod k) and b==0(mod k), where k=2^n-1, m=(2^n-1)*(n-1)-n+2, x=m*(2^n-1), 2^(x-1)==(a+1)(mod x), m^(x-1)==(b+1)(mod x)

1, 3, 4, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217

EXAMPLE
n=3
k=2^3-1=7
m=(2^3-1)*(3-1)-3+2=13
x=m*(2^n-1)=13*7=91
2^(x-1)==(a+1)(mod x);2^90==(63+1)(mod 91), a=63
m^(x-1)==(b+1)(mod x);13^90==(77+1)(mod 91), b=77

test conditions
a==0(mod k), 63==0(mod 7)
b==0(mod k), 77==0(mod 7)
----------------------------------------

All odd numbers are of Mersenne exponents: primes n such that 2^n - 1 is prime A000043

4 is the only even number
why not 2? I do not know .....
Code:
(10:34)>test(n)= k=2^n-1;m=(2^n-1)*(n-1)-n+2;x=m*(2^n-1);a=((2^(x-1))%x)-1;b=((2^(x-1))%x)-1;if(a%k==0 && b%k==0,print(n))
%167 = (n)->k=2^n-1;m=(2^n-1)*(n-1)-n+2;x=m*(2^n-1);a=((2^(x-1))%x)-1;b=((2^(x-1))%x)-1;if(a%k==0&&b%k==0,print(n))
(10:36)>for(n=1,100,test(n))
1
2
3
4
5
7
9
11
  *** _^_: length (lg) overflow
science_man_88 is offline   Reply With Quote
Old 2011-05-19, 14:23   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by allasc View Post
Post of Russia
http://dxdy.ru/post447534.html#p447534

sequence in the OEIS
A190213

Numbers n such that a==0(mod k) and b==0(mod k), where k=2^n-1, m=(2^n-1)*(n-1)-n+2, x=m*(2^n-1), 2^(x-1)==(a+1)(mod x), m^(x-1)==(b+1)(mod x)

1, 3, 4, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217

EXAMPLE
n=3
k=2^3-1=7
m=(2^3-1)*(3-1)-3+2=13
x=m*(2^n-1)=13*7=91
2^(x-1)==(a+1)(mod x);2^90==(63+1)(mod 91), a=63
m^(x-1)==(b+1)(mod x);13^90==(77+1)(mod 91), b=77

test conditions
a==0(mod k), 63==0(mod 7)
b==0(mod k), 77==0(mod 7)
----------------------------------------

All odd numbers are of Mersenne exponents: primes n such that 2^n - 1 is prime A000043

4 is the only even number
why not 2? I do not know .....
Quote:
Proper application here
A190213

Numbers n such that a == 0 (mod k) and b == 0 (mod k),
where
k = 2 ^ n-1
m = (2 ^ n-1) * (n-1)-n +2,
x = m * (2 ^ n-1)
2 ^ (x-1) == (a +1) (mod x),
m ^ (x-1) == (b +1) (mod x)

1, 3, 4, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217

example
-------------------------------------------------- ---------------------------------
n = 3
k = 2 ^ 3-1 = 7
m = (2 ^ 3-1) * (3-1) -3 +2 = 13
x = m * (2 ^ n-1) = 13 * 7 = 91
2 ^ (x-1) == (a +1) (mod x); 2 ^ 90 == (63 +1) (mod 91), a = 63
m ^ (x-1) == (b +1) (mod x); 13 ^ 90 == (77 +1) (mod 91), b = 77

check the basic condition
a == 0 (mod k), 63 == 0 (mod 7)
b == 0 (mod k), 77 == 0 (mod 7)
-------------------------------------------------- ---------------------------------

all odd numbers are exponents Mersenne numbers A000043
test was only able to 3217, on the processor boils
but for me it is an achievement:) to find a test that does not make mistakes up to (2 ^ 3217-1)

4 - the only even number
interesting question is Why 4 instead of 2?? I don `t know ....

ready to hear any comments, maybe I invented the bicycle?
is what google turns it into it's basically the same for the math part though.
science_man_88 is offline   Reply With Quote
Old 2011-05-19, 17:49   #5
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

19×127 Posts
Default

Inb4miscmaththreads.
ixfd64 is offline   Reply With Quote
Old 2011-05-19, 19:19   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23·397 Posts
Default

Testing natural numbers from 2 to 11213, this conjecture is true only for the exponents of the 23 first prime mersenne numbers except 2 is missing and 4 is included:
3,4,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213

Quote:
Numbers n such that a==0(mod k) and b==0(mod k), where k=2^n-1, m=(2^n-1)*(n-1)-n+2, x=m*(2^n-1), 2^(x-1)==(a+1)(mod x), m^(x-1)==(b+1)(mod x)
You can simplify this alot:
k=2n-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: 2x-1 = 1 (mod k) AND (k-n+2)x-1 = 1 (mod k)

Explanation:
Since x=m*k:
2^(x-1)==(a+1)(mod m*k) => 2^(x-1) = m*k*c1 + a+1 for some constant c1
and
a==0(mod k) => a = k*c2 for some constant c2.

Inserting k*c2 for a in the first equation gives:
2^(x-1) = m*k*c1 + k*c2 + 1 = 1 (mod k)

In the same way it can be shown:
m^(x-1) = 1 (mod k)
But instead of m it's faster to use m mod k:
m = k*(n-1)-n+2 = -n+2 (mod k) = k-n+2 (mod k) (-n+2 is negative, so if we want we can add k to make it positive)
So:
m^(x-1) = (-n+2)^(x-1) = (k-n+2)^(x-1) = 1 (mod k)

This is why n=2 doesn't work since k-n+2 = k and k^(x-1) = 0 (mod k)

Last fiddled with by ATH on 2011-05-19 at 19:26
ATH is offline   Reply With Quote
Old 2011-05-19, 20:01   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by ATH View Post
Testing natural numbers from 2 to 11213, this conjecture is true only for the exponents of the 23 first prime mersenne numbers except 2 is missing and 4 is included:
3,4,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213



You can simplify this alot:
k=2n-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: 2x-1 = 1 (mod k) AND (k-n+2)x-1 = 1 (mod k)

Explanation:
Since x=m*k:
2^(x-1)==(a+1)(mod m*k) => 2^(x-1) = m*k*c1 + a+1 for some constant c1
and
a==0(mod k) => a = k*c2 for some constant c2.

Inserting k*c2 for a in the first equation gives:
2^(x-1) = m*k*c1 + k*c2 + 1 = 1 (mod k)

In the same way it can be shown:
m^(x-1) = 1 (mod k)
But instead of m it's faster to use m mod k:
m = k*(n-1)-n+2 = -n+2 (mod k) = k-n+2 (mod k) (-n+2 is negative, so if we want we can add k to make it positive)
So:
m^(x-1) = (-n+2)^(x-1) = (k-n+2)^(x-1) = 1 (mod k)

This is why n=2 doesn't work since k-n+2 = k and k^(x-1) = 0 (mod k)
my test gave false results using a basic PARI script ( mostly all variable=value except a if statement).
science_man_88 is offline   Reply With Quote
Old 2011-05-19, 20:33   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23×397 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
my test gave false results using a basic PARI script ( mostly all variable=value except a if statement).
I don't use PARI but are you sure it can handle the large numbers? x is larger than (2n-1)2. I used the GMP library.
ATH is offline   Reply With Quote
Old 2011-05-19, 20:39   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by ATH View Post
I don't use PARI but are you sure it can handle the large numbers? x is larger than (2n-1)2. I used the GMP library.
it gave the list he gave different before it ran into the length overflow. and you can check my test I posted the code. % is mod in this case.

Last fiddled with by science_man_88 on 2011-05-19 at 20:40
science_man_88 is offline   Reply With Quote
Old 2011-05-19, 21:05   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
it gave the list he gave different before it ran into the length overflow. and you can check my test I posted the code. % is mod in this case.
tried your suggestions to him and I got a length overflow using only primes before I saw 11 ( and I saw 11 in the version I was originally using).
science_man_88 is offline   Reply With Quote
Old 2011-05-19, 21:09   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23×397 Posts
Default

Quote:
Originally Posted by ATH View Post
You can simplify this alot:
k=2n-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: 2x-1 = 1 (mod k) AND (k-n+2)x-1 = 1 (mod k)
Actually only the condition (k-n+2)x-1 = 1 (mod k) is needed, I get the same results just searching for numbers fulfilling this.

Last fiddled with by ATH on 2011-05-19 at 21:09
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
Another way to PRP test Mersenne numbers paulunderwood Miscellaneous Math 18 2017-01-26 20:33
How do I test if it is a mersenne prime on GIMPS? spkarra Math 21 2015-01-23 18:13
another mersenne prime test jocelynl Math 8 2006-10-20 19:36
The 40th known Mersenne prime, 220996011-1 is not PRIME! illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 22:32.


Fri Oct 22 22:32:17 UTC 2021 up 91 days, 17:01, 0 users, load averages: 1.81, 1.88, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.