mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   checking big digit number as prime (https://www.mersenneforum.org/showthread.php?t=25538)

drmurat 2020-05-13 08:24

checking big digit number as prime
 
which one is hard . calculating big digit number or checking it . which methods ca be use for checkig numbers ?

[b][color=red][size=4]MODERATOR NOTE:[/size] Thread moved from FermatSearch forum[/color][/b]

Uncwilly 2020-05-13 13:40

Are you asking how hard it is to take 2[SUP]332,199,893[/SUP]-1 and expand it to its full decimal form vs checking it to see if it is prime?
The first is very fast. Faster than the old machines could display it. The second is slow.

If you have some complex formula to calculate the number vs checking it to see if it is prime, even that, calculating the number is faster than checking it (in almost every case).

paulunderwood 2020-05-13 14:29

[QUOTE=Uncwilly;545234]Are you asking how hard it is to take 2[SUP]332,199,893[/SUP]-1 and expand it to its full decimal form vs checking it to see if it is prime?
The first is very fast. Faster than the old machines could display it. The second is slow.

If you have some complex formula to calculate the number vs checking it to see if it is prime, even that, calculating the number is faster than checking it (in almost every case).[/QUOTE]

Just to expand on your "in almost very case". PRP'ing a huge partitions number is quicker than computing its decimal digits (with the latest Pari/GP version). Proving it prime or even checking the certificate is a few orders more time-consuming.

VBCurtis 2020-05-13 17:25

As for "which methods" from the OP question- it depends on the form that describes your number, as well as how big "big digits" is.

Give us more info about what size and what form you have in mind, you'll get a better answer.

drmurat 2020-05-13 17:49

I think I am at the begining . :) I get 2^50.000 at first night with my own code . can we think it is big :) . I am recording all results from 2 ^ 1 to 2 ^ 50000 . and it goes on I want to calculate fermat and mersenne primes

paulunderwood 2020-05-13 18:03

[QUOTE=drmurat;545279]I think I am at the begining . :) I get 2^50.000 at first night with my own code . can we think it is big :) . I am recording all results from 2 ^ 1 to 2 ^ 50000 . and it goes on I want to calculate fermat and mersenne primes[/QUOTE]

If you taking about how long it takes to wrtie the number to file: The following takes ~1 ms with [URL="https://pari.math.u-bordeaux.fr/download.html"]Pari/GP[/URL]:

[CODE]gettime();write("delMe",2^50000+1);gettime()
1
[/CODE]

drmurat 2020-05-13 18:15

I am calculating 2^50000 and writing to file and calcupating 2^50001 and ... goes on . I get 2^60000 . big numbers get years and years ...

Uncwilly 2020-05-13 18:20

Apfloat also works nice: [url]http://www.apfloat.org/apfloat/[/url]
Also [url]http://numcalc.com/[/url] handles it quickly
And 2^50000-1 is not prime. The exponent has to be prime.

drmurat 2020-05-13 18:29

thank you . it will be so helpfull to me . I get 2 ^ 65000

Uncwilly 2020-05-13 18:36

[QUOTE=drmurat;545288]thank you . it will be so helpfull to me . I get 2 ^ 65000[/QUOTE]
What are your plans (please use a paragraph to state it)? If you are just practicing your coding, look at places that can help you learn. If you don't trust what everyone else has done, you have issues. Are you testing the numbers using L-L? Or are you doing it via a more rudimentary way? What language/platform are you using? Why do you want the decimal expansion?

drmurat 2020-05-13 18:48

okay . I am not plannig to improve my coding . I am behind so many thing about primes . I am medical doctor . I know a bit coding . and intrested in with primes nearly 20 mounths .I do my calculations with my own . it has to reason fitst when I need data fot one process . getting whole data is hard . you must open so many zip files . make them as you want . it gets so time . the second reason making calculation with your own gives you a chance of oservation . I am asking here to calculating 2 ^70000 is hard . I realy dont know the answer .

VBCurtis 2020-05-13 21:52

You keep saying "calculating 2^{some 5-digit number}". What calculation are you doing?

You don't need the decimal expansion to decide if it is prime. You also don't need to write your own software. So, what is it you want to do?

I feel like you intend to find some primes, and then write (to disk? To screen? both?) out the decimal expansions of those primes.

But you aren't even telling us what numbers you are checking. 2^50000 is obviously not prime; do you mean 2^50000 -1, or 2^50000 +1, or something else entirely?

You mentioned fermat and mersenne primes- those have been checked to quite large values, and software is easily available if you wish to contribute to those searches. Why start over from scratch, which gives you no chance whatsoever to discover something previously unknown?

a1call 2020-05-14 02:07

Look at the link in post number 6. It's a program that you can download for free and set up. It's a calculator which can calculate any number you give it instantly. You don't need to write your own program. There is no theoretical limit on how big a number you can give it. The only limitation is your computer's memory. Regardless you can instantly calculate numbers with millions of digit. Proving then prime can take very long time. Days, months, years....

drmurat 2020-05-14 06:50

okay . my method to calculate exponents of 2 is similar to used methods and it is slower than them . I am calculating all because maybe I catch a relation of them so I need a library
what did I do until now .
I achive 3 method to check primes . one is for twin primes and it is well known . one is primes and sont have advantag to clasicap method . one for 6 x k - 1 primes . in this method you dont use all primes until squareroot . but it cant reduce number of calculation.
I worked on goldbach 4 ways for even numbers 2 ways to odd numbers I also calculatwd numbers until 10^7 but no one doesnt explain infinity
I found a speciality of fibonacci numbers but I think it is known
I am working two geometrical shape can be related with primes
and some more
I must look my papers
I use simple maths for calculation
thats all :)

drmurat 2020-05-14 08:28

[QUOTE=VBCurtis;545305]You keep saying "calculating 2^{some 5-digit number}". What calculation are you doing?

You don't need the decimal expansion to decide if it is prime. You also don't need to write your own software. So, what is it you want to do?

I feel like you intend to find some primes, and then write (to disk? To screen? both?) out the decimal expansions of those primes.

But you aren't even telling us what numbers you are checking. 2^50000 is obviously not prime; do you mean 2^50000 -1, or 2^50000 +1, or something else entirely?

You mentioned fermat and mersenne primes- those have been checked to quite large values, and software is easily available if you wish to contribute to those searches. Why start over from scratch, which gives you no chance whatsoever to discover something previously unknown?[/QUOTE]

2^50000 only a sample

carpetpool 2020-05-15 18:39

[QUOTE=drmurat;545292]okay . I am not plannig to improve my coding . I am behind so many thing about primes . I am medical doctor . I know a bit coding . and intrested in with primes nearly 20 mounths .I do my calculations with my own . it has to reason fitst when I need data fot one process . getting whole data is hard . you must open so many zip files . make them as you want . it gets so time . the second reason making calculation with your own gives you a chance of oservation . I am asking here to calculating 2 ^70000 is hard . I realy dont know the answer .[/QUOTE]

You seem to have the right idea. You want to calculate 2^n for some integer n. However, this integer n is the one you want to test for primality, and not even 2^n, but 2^n mod n. (n may have, thousands, millions, and maybe even a billion digits). Look up modular or binary exponentiation.

If a does not divide n, n is prime --> a^n = a mod n --> a^(n-1) = 1 mod n

[SUP]What happens when n is composite?[/SUP]

VBCurtis 2020-05-15 18:59

[QUOTE=carpetpool;545480]You seem to have the right idea. You want to calculate 2^n for some integer n. However, this integer n is the one you want to test for primality, and not even 2^n, but 2^n mod n. (n may have, thousands, millions, and maybe even a billion digits). Look up modular or binary exponentiation.[/QUOTE]

If n is the exponent, as you have clearly indicated, n *cannot* have millions or billions of digits for any meaningful description or test for primality.

The number 2^n may indeed be as large as those descriptions, but the exponent 'n' cannot. 2 raised to a thousands-of-digits number is not an item we contemplate for primality testing, ever.


All times are UTC. The time now is 03:06.

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