mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-19, 21:47   #67
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

805610 Posts
Default

Quote:
Originally Posted by LaurV View Post
You don't seem to comprehend much of the idea how large these numbers are...
We watched a video recently that did a good job of showing how big a (relatively small) 256-bit number is.

Xyzzy is offline   Reply With Quote
Old 2021-02-20, 13:58   #68
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

22×227 Posts
Default

Mathematica has some very spiffy front end processing, plus plotting and so on, but the back end speed was nothing special for bulk processing back when I tested it. It was slower than Pari/GP when you got into the actual work of big powmods, etc. Again, their selling point is the front end processing and the whole package.

Pari/GP is nice, and the interpreter is quite fast considering. It also has some very nice algorithms, but for simple things, it's usually slower than GMP (but we're now in the 1.5-10x range, not 100-10000x). For most tasks, 3x slower is more than acceptable for being able to write a couple lines of highly readable GP code, vs. hand writing 100 line GMP function calls. Not to mention all the extra functions that you get.

See the Lucas-Lehmer task on RosettaCode for some examples including C/GMP, Pari/GP, and Mathematica. Especially see the C/GMP code, which is going to be much faster than Mathematica for this. In turn, especially as the size increases, gwnum / PRIME95 is going to be faster yet. Substantially so for exponents on the frontier. This shouldn't come as a surprise given the goal and target audience of each.

tl;dr: see retina's previous post. :)
danaj is offline   Reply With Quote
Old 2021-02-20, 15:25   #69
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
Have you thought about programing LL up in Excel instead?
I don't know precisely what you mean by Excel programming. It is the table editor not the programming language. But if you mean the Microsoft Visual Basic: https://www.excel-vba.com/vba-excel-install.htm then no.

The code in Visual Basic is on this list: http://rosettacode.org/wiki/Lucas-Lehmer_test#PARI.2FGP

I only wanted to know what to do that Mathematica PrimeQ[2^n-1] returns me True or False on the Mersenne of the interest i.e. above the current known. And for sure with Compile and Parallel options or using Mathlink to link to compiled code you can write your own routine for example called MyPrimeQ[] which is as fast as Prime95.

Already without doing anything difficult I managed to exclude one giant by default IntegerQ[] which replies if the number is integer after some hours of running that:

In[31]:= PrimeQ[58 501 120 901]
Out[31]= True
In[28]:= IntegerQ[(2^(58 501 120 901) - 1) / (13 384 * 2 * 58 501 120 901 + 1)]
Out[28]= True

Last fiddled with by mattprim on 2021-02-20 at 16:05
mattprim is offline   Reply With Quote
Old 2021-02-20, 18:28   #70
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

53×29 Posts
Default

There is a huge difference in run times between checking Mp/f is integer and Mod(2,f)^p==1. Really. You should try it. Only a fool wouldn't.

Last fiddled with by paulunderwood on 2021-02-20 at 19:17
paulunderwood is offline   Reply With Quote
Old 2021-02-24, 08:44   #71
mattprim
 
mattprim's Avatar
 
Feb 2021
Salt Lake City, UT

29 Posts
Default

The proof of LL test to be all the time in the integer space is comparatively easy in special cases of the Mersenne exponent a it is for the Great (Last) Fermat Theorem. You can proceed like that for any n as long as you can handle the symbolic math (note that for n=7 already the polynomial of 62-nd order appears and generally of 2^(n-1)-2 order so it shows from the little Fermat theorem for 2 that p must be the prime to partition like that. The proof for n=5:

Let s_0=x^2. Then for s_{n+1} = s_n*s_n - x, s_3/x/(x-1) = 1 + 2 x^2 + x^3 + x^4 - 3 x^5 + x^6 + x^7 + 3 x^8 - 3 x^9 - 3 x^10 - 3 x^11 + x^12 + x^13 + x^14. Lets pull out x^5 from the part of the polynomial of at least 5-th order and add the factor and subtract the factor so one term is divisible by x^5-1 and do the same again with the residual polynomial. The resulting polynomial is P(x)=-5 - 2 x + 4 x^2 + 5 x^3 - x^4 but the Polynomial Q(x) =-5 - 2 x + 4 x^2 + 5 x^3 - x^4 - x^5 + 1 factorizes Q(x)=-(-2 + x) (-2 - 2 x + x^2 + 3 x^3 + x^4) i.e. Q(2)=0 so P(2) = 2^5-1 so is divisible by M_5 and so the s_3 is.

And for n=7:

Let s_0=x^2. Then for s_{n+1} = s_n*s_n - x, s_5/x/(x-1) = 1 + 2 x^2 - 3 x^3 + 11 x^4 - 15 x^5 + 29 x^6 - 56 x^7 + 86 x^8 - 140 x^9 + 224 x^10 - 326 x^11 + 494 x^12 - 710 x^13 + 898 x^14 - 1311 x^15 + 1849 x^16 - 2139 x^17 + 2725 x^18 - 3759 x^19 + 4329 x^20 - 5039 x^21 + 6209 x^22 - 6899 x^23 + 8217 x^24 - 9347 x^25 + 8709 x^26 - 10639 x^27 + 13273 x^28 - 9759 x^29 + 10113 x^30 - 16239 x^31 + 11227 x^32 - 6675 x^33 + 15561 x^34 - 13045 x^35 + 2895 x^36 - 10965 x^37 + 13299 x^38 - 1011 x^39 + 5149 x^40 - 10891 x^41 + 869 x^42 - 979 x^43 + 7029 x^44 - 1027 x^45 - 691 x^46 - 3603 x^47 + 769 x^48 + 741 x^49 + 1469 x^50 - 351 x^51 - 351 x^52 - 463 x^53 + 97 x^54 + 97 x^55 + 105 x^56 - 15 x^57 - 15 x^58 - 15 x^59 + x^60 + x^61 + x^62. Lets pull out x^7 from the part of the polynomial of at least 7-th order and add the factor and subtract the factor so one term is divisible by x^7-1 and do the same again with the residual polynomial and again and again till it is 6-th order polynomial occurs adding all the reminders. The resulting residual polynomial deciding the divisibility by x^7-1 is P(x)=-2253 - 1405 x + 623 x^2 + 1966 x^3 + 2126 x^4 + 398 x^5 - 1454 x^6 but the Polynomial Q(x) =-2253 - 1405 x + 623 x^2 + 1966 x^3 + 2126 x^4 + 398 x^5 - 1454 x^6 - 261 (-x^7 + 1) factorizes Q(x)=-(-2 + x) (1257 + 1331 x + 354 x^2 - 806 x^3 - 1466 x^4 - 932 x^5 + 261 x^6) i.e. Q(2)=0 so P(2) = - 261*(2^7-1)=3*3*2*29*(2^7-1) so is divisible by M_7 and so the s_5 is.

Last fiddled with by mattprim on 2021-02-24 at 09:01
mattprim is offline   Reply With Quote
Old 2021-02-24, 09:13   #72
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E2916 Posts
Default

Are you seriously thinking of spreading this calculation over a supercomputer running Mathematica? At the current wavefront you would need to calculate a polynomial with ~2^109000000 terms, let alone store and manipulate all the coefficients.
paulunderwood is offline   Reply With Quote
Old 2021-02-24, 09:40   #73
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

10111111011012 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
At the current wavefront you would need to calculate a polynomial with ~2^109000000 terms, let alone store and manipulate all the coefficients.
With ~2^265 atoms in the observable universe, that means we only have to store 2^108999735 coefficients into each atom. So, IOW, not a problem at all, why haven't we done it yet?
retina is online now   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 13:30.

Wed Apr 21 13:30:14 UTC 2021 up 13 days, 8:11, 0 users, load averages: 2.24, 2.08, 1.87

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.