mersenneforum.org > Math New test for Mersenne prime
 Register FAQ Search Today's Posts Mark Forums Read

 2011-05-19, 11:54 #1 allasc   Aug 2010 SPb 2·17 Posts 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 .....
 2011-05-19, 12:51 #2 Uncwilly 6809 > 6502     """"""""""""""""""" Aug 2003 101×103 Posts 247678 Posts
2011-05-19, 13:39   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

24·3·52·7 Posts

Quote:
 Originally Posted by allasc 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

2011-05-19, 14:23   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110100002 Posts

Quote:
 Originally Posted by allasc 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.

 2011-05-19, 17:49 #5 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 2×17×73 Posts Inb4miscmaththreads.
2011-05-19, 19:19   #6
ATH
Einyen

Dec 2003
Denmark

5×677 Posts

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

2011-05-19, 20:01   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110100002 Posts

Quote:
 Originally Posted by ATH 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).

2011-05-19, 20:33   #8
ATH
Einyen

Dec 2003
Denmark

5×677 Posts

Quote:
 Originally Posted by science_man_88 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.

2011-05-19, 20:39   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

24×3×52×7 Posts

Quote:
 Originally Posted by ATH 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

2011-05-19, 21:05   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

24·3·52·7 Posts

Quote:
 Originally Posted by science_man_88 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).

2011-05-19, 21:09   #11
ATH
Einyen

Dec 2003
Denmark

5·677 Posts

Quote:
 Originally Posted by ATH 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

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 paulunderwood Miscellaneous Math 18 2017-01-26 20:33 spkarra Math 21 2015-01-23 18:13 jocelynl Math 8 2006-10-20 19:36 illman-q Miscellaneous Math 33 2004-09-19 05:02

All times are UTC. The time now is 14:04.

Sat Oct 1 14:04:22 UTC 2022 up 44 days, 11:32, 1 user, load averages: 1.50, 1.40, 1.26