 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   New test for Mersenne prime (https://www.mersenneforum.org/showthread.php?t=15607)

 allasc 2011-05-19 11:54

New test for Mersenne prime

Post of Russia
[URL="http://dxdy.ru/post447534.html#p447534"]http://dxdy.ru/post447534.html#p447534[/URL]

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 .....

 Uncwilly 2011-05-19 12:51

:soapbox:

 science_man_88 2011-05-19 13:39

[QUOTE=allasc;261767]Post of Russia
[URL="http://dxdy.ru/post447534.html#p447534"]http://dxdy.ru/post447534.html#p447534[/URL]

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]

[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[/CODE]

 science_man_88 2011-05-19 14:23

[QUOTE=allasc;261767]Post of Russia
[URL="http://dxdy.ru/post447534.html#p447534"]http://dxdy.ru/post447534.html#p447534[/URL]

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]

[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 ....

is what google turns it into it's basically the same for the math part though.

 ixfd64 2011-05-19 17:49

 ATH 2011-05-19 19:19

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)[/QUOTE]

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

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)

 science_man_88 2011-05-19 20:01

[QUOTE=ATH;261790]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=2[SUP]n[/SUP]-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: [B]2[SUP]x-1[/SUP] = 1 (mod k)[/B] AND [B](k-n+2)[SUP]x-1[/SUP] = 1 (mod k)[/B]

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)[/QUOTE]

my test gave false results using a basic PARI script ( mostly all variable=value except a if statement).

 ATH 2011-05-19 20:33

[QUOTE=science_man_88;261791]my test gave false results using a basic PARI script ( mostly all variable=value except a if statement).[/QUOTE]

I don't use PARI but are you sure it can handle the large numbers? x is larger than (2[SUP]n[/SUP]-1)[SUP]2[/SUP]. I used the GMP library.

 science_man_88 2011-05-19 20:39

[QUOTE=ATH;261793]I don't use PARI but are you sure it can handle the large numbers? x is larger than (2[SUP]n[/SUP]-1)[SUP]2[/SUP]. I used the GMP library.[/QUOTE]

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.

 science_man_88 2011-05-19 21:05

[QUOTE=science_man_88;261795]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.[/QUOTE]

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).

 ATH 2011-05-19 21:09

[QUOTE=ATH;261790]You can simplify this alot:
k=2[SUP]n[/SUP]-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: [B]2[SUP]x-1[/SUP] = 1 (mod k)[/B] AND [B](k-n+2)[SUP]x-1[/SUP] = 1 (mod k)[/B][/QUOTE]

Actually only the condition [B](k-n+2)[SUP]x-1[/SUP] = 1 (mod k)[/B] is needed, I get the same results just searching for numbers fulfilling this.

All times are UTC. The time now is 05:58.