mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   The "one billion minus 999,994,000" digits prime number (https://www.mersenneforum.org/showthread.php?t=20568)

a1call 2015-10-31 21:22

Thank You for the reply and link [B]Batalov,

[/B]What is the largest number of digits that can be generated using the tool that you linked to?

Any idea on the maximum number of input digits for the Wolfram Alpha Pro?

Thanks in advance.

Batalov 2015-10-31 21:32

Factordb is a (free) webservice that its owner periodically adjusts and tunes. The limits may be variable, but as this link shows, [URL="http://factordb.com/index.php?query=%2810^10000001-1%29%2F9"]10 million digits[/URL] are not forbidden by size: http://factordb.com/index.php?query=%2810^10000001-1%29%2F9 (iirc, the limits were lower before, perhaps at 1 million digits)

There is no one single limit. [URL="http://factordb.com/res.php"]There are limits[/URL]: by size, by computation time that the server spend on "you" (which it defines by your IP address), on a number of queries that you can run in any given hour, etc. Once any of these are exceeded, the server will let you know.

a1call 2015-10-31 21:44

Thank you, Can't get the 1st link but it doesn't matter. 10^7 is just too big, I doubt it if any online/offline calculator, free or pro can do arithmetic in that range and attest to the evaluated number being prime.
Would appreciate if someone let's me know if there is though.

Batalov 2015-10-31 21:49

If we also consider the deeper level of your question (even if you didn't mean it) --

The tool(s) for searching for large Riesel primes are hidden behind the factordb.com facade. The largest currently known Riesel prime is at the moment has 3,580,969 decimal digits, and as for its cousin with the '+' sign (the Proth primes), the largest one has 3,918,990 digits and the next ones can be soon found in the area of above 9 million digits. These searches are limited only by time, not by tool's limitations as it were (those technical limits are comfortably far for years to come).

danaj 2015-10-31 23:30

Both gwnum and GMP can do arithmetic on million digit numbers, and there is one or more open source or freely available LLR code using each library. gwnum is much faster at that size, but GMP (or Pari) could certainly be used to double check something if it was desired.

a1call 2015-10-31 23:59

Thank you [B]danaj[/B],

I will look into your suggestions. I am not a linux guru though have used it fairly enough in the past. I have installed PARI/gp on an Ubuntu virtual machine. Not sure how to run it though. It seems to be the engine behind Mathomatic but last time I checked (very superficially) it seemed to give the message the integer is too long or something.
Anywho Thank you for the suggestions.

jasong 2015-11-04 04:26

I'm not an expert at this by any means, but I think you need to install and figure out the "libraries" that have been suggested in one or two posts of this thread.

I put quotes around libraries because I'm not certain I'm using the term correctly. I'm post-noob(amateur?) when it comes to Linux, but it's been years.

off-topic: Been intending to buy a cheap Linux box and only use my Win 10 pc for gaming. Haven't gotten around to it, though.

Xyzzy 2015-11-04 12:26

[QUOTE=jasong;414901]off-topic: Been intending to buy a cheap Linux box and only use my Win 10 pc for gaming. Haven't gotten around to it, though.[/QUOTE][URL]https://www.debian.org/CD/live/[/URL]

:mike:

a1call 2015-11-05 02:45

Thank You [B]jasong [/B]and [B]Xyzzy[/B],

I think I found a path of less resistance than Linux (for me).

[QUOTE=rogue;413493]Also, any number you find needs to be proven prime with other software. pfgw will be able to do a PRP test on anything, but there is no quick way to prove primality on most PRPs.

I suggest that you start smaller, about 1,000 decimal digits. If it is relatively easy to find PRPs of that size and they can be proven prime using Primo if pfgw can't handle them. You will need to show that all numbers of that size that you generate with your code are both PRP and prime before anyone takes you seriously.[/QUOTE]

The following [B]1073 digit prime[/B] was found using Theorem 2 as a prime candidate (Not converging) and limited programming (loops are limited by time on free accounts of Wolfram Development Platform Beta) and verified by this tool (Thank you MFB) in 18m 21s:
[URL]http://www.alpertron.com.ar/ECM.HTM[/URL]

Not meant as a stepping stone to Billion digits, but I am hooked on finding primes:

[CODE]17301304951032760979391540193063942238627682268484375059657797614141421418495209718498044122698756352618538497495820651532862095140913836791275751603224329708365511386845438457428416851015999781499739435257993030575395521148456370126973589861926447884890905040895142783915003661035159229205944992835893864590602509263424611416123644256541090152154512730215021789569325707624767626996064050083616852868906332140134344237134396002824248209935006343957263114330913889773184009113859258418819604265270733786352915204992280741674163394608327544357353928253505413942752531277381920544376012570452429112062991939767408636679110093897812817626397868615203488782193665960754503922109247702751732229582159545932429202012497327629174354607890117512658337229246677699256833499748867690239242308519052661350031566032280211872532743075445338450341469721741259844914418473536208488402577491114597561265849781778899521612711411589991576446341769618521815120994972553526447111347234336226114001576307246794751766320656024207911756851820233499473255290178571719920249186095508547296580127621[/CODE]
ETA You will have to scroll right to see the whole number.

danaj 2015-11-05 11:51

The nice thing about Maurer and Shawe-Taylor random prime generation is that they construct a primality certificate as they create the prime. The certificate is a chain of BLS theorem 3 or Pocklington steps respectively. 1073 digit primes [i]with certificates[/i] are produced in 2-6 seconds by my code, which is not particularly fast at this.

Standard random prime generation is a bit faster, but then leaves one having to do a proof, which was the problem with large primes -- our current general form methods are only computationally feasible to 30k digits or so. So of course your method would need to do something similar to the Maurer or Shawe-Taylor methods, where you have a solid theorem that proves that the larger number is prime if the smaller number is prime (or some other similar condition such as the appropriate variables of theorem 1 that allow its duplication).

a1call 2015-11-05 17:03

[QUOTE=danaj;415011]The nice thing about Maurer and Shawe-Taylor random prime generation is that they construct a primality certificate as they create the prime. The certificate is a chain of BLS theorem 3 or Pocklington steps respectively. 1073 digit primes [i]with certificates[/i] are produced in 2-6 seconds by my code, which is not particularly fast at this.

Standard random prime generation is a bit faster, but then leaves one having to do a proof, which was the problem with large primes -- our current general form methods are only computationally feasible to 30k digits or so. So of course your method would need to do something similar to the Maurer or Shawe-Taylor methods, where you have a solid theorem that proves that the larger number is prime if the smaller number is prime (or some other similar condition such as the appropriate variables of theorem 1 that allow its duplication).[/QUOTE]

Thank you for your reply.
Your method is faster than mine which basically is a very short routine which takes in 2 relatively small variables (<100 in this case) that I have to try inputting manually due to free account limitation (no random function is used). A thereon such as theorem 1 is of value for finding primes even when it does not converge to less than the square since it can be used to construct routines which yield primes with astronomically higher probability than random trials. For example odd numbers are twice as likely to be primes than integers in general. Factor out divisible by 3s and you improve your odds substantially more.
As for billion digits, computation limitation is a big problem. So a mathematical approach is probably the practical approach.
For a very simplified example:
p=x!!-2^y , p<x^2
Can be easily shown/proven to have a solution with more than one billion decimal digits (or any other number of digits) which is guaranteed to be a prime.
However getting numeric solutions for x and y are virtually impossible.
My Thereon 1 and to a greater degree Theorem 2 (undisclosed so far) has a much more probable solution. Obviously my mathematical skills have not sufficed to find a solution yet. But I am convinced that such a solution is feasible given proper mathematical skills (much better than mine).


All times are UTC. The time now is 13:04.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.