mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-19, 10:36   #56
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

111012 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
You are still calculaing Mp for composite p. Read Wiki on Mersenne primes. p needs to be prime. Put an if statement at the beginning of the loop to check p is prime.

This is bad: s = 4; Do[s = Mod[(s*s - 2), Mp] ....
This is good: s = Mod[4, Mp]; Do[s = s^2-2 ....

When you have your MMA code running on a 1572864 core computer we will believe your absurd claims.

What the hell do you think Mp = 2^Prime[p] - 1 does?
Here p is prime because it is Prime[p] i.e. p->Prime[p]. Mathematica function Prime[p] returns the p-th prime number i.e. Prime[1]=2, Prime[2]=3, Prime[3]=5 etc. I am not running it on 1572864 core computer. It is the EFF https://www.eff.org/ which posted the 150 000 $ prize to find the 100 000 digits Mersenne prime and IBM constructed this computer so they can find it by themselves even with general problems Mathematica and they expect you to run something else. I only say that it is possible to find those fast there and only using this code. My 1GHz to confirm the biggest known takes some 1 year of the constant run. The multicore IBM is also strategic computer capable to calculate optimal orders for simulated war (like chess playing code but simulating the military operations in real time) so it has most likely the classified access i.e. for the people with security clearance Q from the governmental labs like the Los Alamos. Did not check that yet who can get CPU time account there.

Last fiddled with by mattprim on 2021-02-19 at 11:24
mattprim is offline   Reply With Quote
Old 2021-02-19, 10:50   #57
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

Here is the PariGP code which is running more less the same fast (one night on 1.5 GHz) to check the same what which my Mathematica compiled code:

LL(p)={
my(m=Mod(4,1<<p-1));
for(i=3,p,m=m^2-2);
m==0
};
? search()={
print("2^2-1");
forprime(p=3,43112609,
if(LL(p), print("2^"p"-1"))
)
};
?
? search()

2^2-1
2^3-1
2^5-1
2^7-1
2^13-1
2^17-1
2^19-1
2^31-1
2^61-1
2^89-1
2^107-1
2^127-1
2^521-1
2^607-1
2^1279-1
2^2203-1
2^2281-1
2^3217-1
2^4253-1
2^4423-1
2^9689-1
2^9941-1
2^11213-1
2^19937-1
2^21701-1
2^23209-1
2^44497-1

Last fiddled with by mattprim on 2021-02-19 at 10:53
mattprim is offline   Reply With Quote
Old 2021-02-19, 11:20   #58
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,863 Posts
Default

Okay grasshopper, now implement modular reduction over Mp either in Pari/GP or MMA.

Then do some shallow trial division by 2*k*p+1.

I expect this to speed up your codes by 20 fold.
paulunderwood is offline   Reply With Quote
Old 2021-02-19, 11:33   #59
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

1D16 Posts
Default

Sorry, I am only mathematician with PhD trying to do some research how to get 150 thousand dollars prize for 100 million digits prime. I actually believe there is some Fermat Last (Great) Theorem like theorem which Mersennes are primes stating like "The Mersenne number is the prime if and only if ... " i.e. its prime exponent fulfills some conditions which then I would call a superprime or prime prime. The theorem than would allow to simply construct the next larger Mersenne prime. For example: the Mersenne prime is the prime if and only its exponent Modulo division by all the lower primes is the prime. Or: The Mersenne prime is the prime if and only if its position in primes number factorization does not contain 13 etc. i.e. the result of the LL test can be predicted from it.

Last fiddled with by mattprim on 2021-02-19 at 12:13
mattprim is offline   Reply With Quote
Old 2021-02-19, 14:26   #60
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

111012 Posts
Default

The prove of LL test not getting out of the integer number space is comparatively easy for n=3 but it does not want go that way
easy for larger:

let s = x^2

Then let

s_1 = x^2*x^2 - x = x^4 - x = x*(x^3-1) = x (x-1)(1+x+x^2)

but from the geometric series 1+x+x^2 = (1-x^3)/(1-x)

so s1 is devisable by (1-x^3)/(1-x) which for x=2 is exactly the Mersenne prime 2^3-1=7

But if you generate this polynomials in general higher not much can be done and seen that way. Simply gets worse than the normal Great Fermat theorem that some polynomial in x of 2p-2 order for x integer is integer-proportional to x^n-1 only for n a certain prime and x=2.

Last fiddled with by mattprim on 2021-02-19 at 14:36
mattprim is offline   Reply With Quote
Old 2021-02-19, 15:50   #61
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by mattprim View Post
Sorry, I am only mathematician with PhD trying to do some research how to get 150 thousand dollars prize for 100 million digits prime.
...but you don't know the 165-year-old Lucas-Lehmer test. For comparison, this is what cars looked like 165 years ago, and this was the current state of the art research toward the internal combustion engine. Please, update your knowledge -- if you want to make a breakthrough, you can't start from 19th-century tech.
CRGreathouse is offline   Reply With Quote
Old 2021-02-19, 16:18   #62
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11000100010102 Posts
Default

This whole thread is pointless.

Mathematica is not the tool to use. Is it for general purpose, and not optimised for Mersenne primes.

The OP is wasting time trying to use it.
retina is online now   Reply With Quote
Old 2021-02-19, 16:54   #63
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5·997 Posts
Default

Quote:
Originally Posted by mattprim View Post
I actually believe there is some Fermat Last (Great) Theorem like theorem which Mersennes are primes stating like "The Mersenne number is the prime if and only if ... " i.e. its prime exponent fulfills some conditions which then I would call a superprime or prime prime.
AFAIK the greatest mathematical importance of Fermat's Last Theorem is that no proof was known, and efforts to find a proof greatly advanced the subject of Algebraic Number Theory

Fermat's "little theorem" is much more pertinent, leading to a simple explanation of the fact that if p is prime and q divides 2p - 1, then p divides q-1.

If you think there's a way to test whether the prime p is such that 2p - 1 is prime, which is significantly cheaper computationally than the methods currently known and used, I doubt you would be able to discover it by testing exponents in the known range.

Mersenne himself thought he had a way of determining which exponents p gave prime values of 2p - 1. He didn't.

Last fiddled with by Dr Sardonicus on 2021-02-19 at 16:55
Dr Sardonicus is offline   Reply With Quote
Old 2021-02-19, 16:57   #64
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111010110112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Mersenne himself thought he had a way of determining which exponents p gave prime values of 2p - 1. He didn't.
See A109461 and Mersenne Primes: Early history.
CRGreathouse is offline   Reply With Quote
Old 2021-02-19, 21:22   #65
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

2910 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
...but you don't know the 165-year-old Lucas-Lehmer test. For comparison, this is what cars looked like 165 years ago, and this was the current state of the art research toward the internal combustion engine. Please, update your knowledge -- if you want to make a breakthrough, you can't start from 19th-century tech.
I am just proving it to you for one 3-2=1 iteration: 2^3-1=7 is the Mersenne prime and it is dividing s_1:

The prove of LL test not getting out of the integer number space is comparatively easy for n=3 but it does not want go that way
easy for larger:

let s_0 = x^2

Then let

s_1 = x^2*x^2 - x = x^4 - x = x*(x^3-1) = x (x-1)(1+x+x^2)

but from the geometric series 1+x+x^2 = (1-x^3)/(1-x)

so s1 is devisable by (1-x^3)/(1-x) which for x=2 is exactly the Mersenne prime 2^3-1=7

But if you generate this polynomials in general higher not much can be done and seen that way. Simply gets worse than the normal Great Fermat theorem that some polynomial in x of 2p-2 order for x integer is integer-proportional to x^n-1 only for n a certain prime and x=2.

Last fiddled with by mattprim on 2021-02-19 at 21:39
mattprim is offline   Reply With Quote
Old 2021-02-19, 21:26   #66
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

10,007 Posts
Default

Have you thought about programing LL up in Excel instead?
Uncwilly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Searching for m. primes is like playing lottery joblack Lounge 20 2009-01-05 15:18
to be faster at searching mersenne primes flosculus Information & Answers 6 2008-11-10 18:59
searching for Mersenne primes davieddy Math 7 2007-08-21 04:51
A Proposal for searching Recurrence Series Primes Erasmus Factoring 3 2004-05-14 09:26
Need help with math problem re: searching for all primes. daxm Miscellaneous Math 5 2003-07-20 19:32

All times are UTC. The time now is 09:37.


Thu Oct 21 09:37:27 UTC 2021 up 90 days, 4:06, 1 user, load averages: 0.82, 0.87, 0.97

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.