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

257116 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

100000110000002 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

2×3×397 Posts
Default

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

3×5×11×19 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 online now   Reply With Quote
Old 2011-05-19, 20:01   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 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

3×5×11×19 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 online now   Reply With Quote
Old 2011-05-19, 20:39   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 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

26×131 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

3·5·11·19 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 online now   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 12:10.

Tue May 18 12:10:07 UTC 2021 up 40 days, 6:51, 1 user, load averages: 2.27, 2.00, 1.83

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.