mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-06-08, 01:20   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·547 Posts
Default Alternative to LL

Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+1/a));a==2
Seems to be 10 times slower than LL.
paulunderwood is online now   Reply With Quote
Old 2016-06-08, 02:03   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

206078 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+1/a));a==2
Seems to be 10 times slower than LL.
it only works for odd p
LaurV is offline   Reply With Quote
Old 2017-11-13, 23:49   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×3×547 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+1/a));a==2
Seems to be 10 times slower than LL.
I found another one:

Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+3/a));a==0
If only there was some better-than-squaring-computationally way of taking an inverse mod a Mersenne number. Or being able to solve x^2+6 == 0 mod mp without exponentiation.

Last fiddled with by paulunderwood on 2017-11-13 at 23:56
paulunderwood is online now   Reply With Quote
Old 2017-11-13, 23:56   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Or being able to solve x^2+6 == 0 mod mp without exponentiation.
comes down to where the squares are on the arithmetic progression y(mp)-6. parity of x is the parity of y.

Last fiddled with by science_man_88 on 2017-11-13 at 23:57
science_man_88 is offline   Reply With Quote
Old 2017-12-11, 00:56   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·3·547 Posts
Default

Here is another test for Mersennes:

Code:
f(p)=local(mp=2^p-1,a=Mod(2,mp),b);for(b=3,p,a=a^2*2-1);a==0
paulunderwood is online now   Reply With Quote
Old 2017-12-11, 01:05   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Here is another test for Mersennes:

Code:
f(p)=local(mp=2^p-1,a=Mod(2,mp),b);for(b=3,p,a=a^2*2-1);a==0
we know about it ... see: https://oeis.org/A002812 like with most alterations of the LL test it's got many start values.

Last fiddled with by science_man_88 on 2017-12-11 at 01:08
science_man_88 is offline   Reply With Quote
Old 2017-12-11, 02:54   #7
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×72 Posts
Post

I don't know if this is useful but https://oeis.org/A002812 happens to be the subset of the sequence https://oeis.org/A110293. Like the Mersenne sequence 2^n-1, this is also a divisibility sequence.

a(n) = 2*a(n-1)^2 - 1, starting a(0)=n

b(n) = b(n-1)^2-2, starting b(0)=n

are generalizations of https://oeis.org/A110293

I don't know the sequences which a(n) or b(n) are subsets of.

That is, there exists sequences A(n) and B(n) such that

A(2^n) = a(n)
B(2^n) = b(n)

The sequences a(n) and b(n)

For further discussion let

ll(2^n) be the sequence in https://oeis.org/A002812

and

ll(n) be the sequence in https://oeis.org/A110293

Another question that comes up is how are ll(n) and 2^n-1 related to eachother other than the fact that if 2^n-1 is prime, then 2^n-1 divides ll(2^(n-2)).
carpetpool is offline   Reply With Quote
Old 2018-05-02, 15:37   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

CD216 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I found another one:

Code:
f(p)=mp=2^p-1;a=Mod(2,mp);for(b=1,p-1,a=(a/2+3/a));a==0
If only there was some better-than-squaring-computationally way of taking an inverse mod a Mersenne number. Or being able to solve x^2+6 == 0 mod mp without exponentiation.
The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime:

1^2+6 == 0 mod 2^3-1
5^2+6 == 0 mod 2^5-1
11^2+6 == 0 mod 2^7-1
1405^2+6 == 0 mod 2^13-1

Last fiddled with by paulunderwood on 2018-05-02 at 15:40
paulunderwood is online now   Reply With Quote
Old 2018-05-02, 17:32   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime:

1^2+6 == 0 mod 2^3-1
5^2+6 == 0 mod 2^5-1
11^2+6 == 0 mod 2^7-1
1405^2+6 == 0 mod 2^13-1
12²+6== 0 mod 2^4-1

Last fiddled with by science_man_88 on 2018-05-02 at 17:32
science_man_88 is offline   Reply With Quote
Old 2018-05-02, 17:57   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

52·131 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime:

1^2+6 == 0 mod 2^3-1
5^2+6 == 0 mod 2^5-1
11^2+6 == 0 mod 2^7-1
1405^2+6 == 0 mod 2^13-1
2968558982^2 + 6 == 0 (mod 2^37 - 1)
;-)

Last fiddled with by Dr Sardonicus on 2018-05-02 at 18:05
Dr Sardonicus is offline   Reply With Quote
Old 2018-05-02, 18:40   #11
ONeil
 
ONeil's Avatar
 
Dec 2017

107 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
The solution to x^2+6 == 0 mod mp seems to act as a "certificate". Seemingly, knowing x leads to a rapid verification of the Mersenne prime:

1^2+6 == 0 mod 2^3-1
5^2+6 == 0 mod 2^5-1
11^2+6 == 0 mod 2^7-1
1405^2+6 == 0 mod 2^13-1
Paul can you elaborate on this concept of rapid verification of Mprime?.
ONeil is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java applet alternative a1call Programming 19 2019-11-08 22:31
alternative ( points of view ) cmd cmd 51 2019-09-28 14:56
Fulsorials a1call Miscellaneous Math 41 2019-07-21 14:19
CEMPLLA: An alternative to GIMPS ? CEMPLLA Author Data 233 2019-06-28 17:18
free alternative to EasyFit? ixfd64 Software 1 2008-04-26 21:28

All times are UTC. The time now is 18:35.

Sat Jul 11 18:35:28 UTC 2020 up 108 days, 16:08, 0 users, load averages: 1.47, 1.56, 1.52

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.