New test for Mersenne prime

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

[Uncwilly]

[science_man_88]

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

(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]

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

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.

[ixfd64]

Inb4miscmaththreads.

[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

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=2ⁿ-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: 2^x-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)

[science_man_88]

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=2ⁿ-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: 2^x-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).

[ATH]

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 (2ⁿ-1)². I used the GMP library.

[science_man_88]

Originally Posted by ATH

I don't use PARI but are you sure it can handle the large numbers? x is larger than (2ⁿ-1)². 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.

[science_man_88]

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

[ATH]

Originally Posted by ATH

You can simplify this alot:
k=2ⁿ-1, m=k*(n-1)-n+2, x=m*k
Now your conditions is equivalent to: 2^x-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.