Is there a quick way to determine if this is a prime number?

[gabrelov]

Collatz Theory is a newer form of mathematics(recent). I developed it originally to try to solve the Collatz conjecture, but I found more than I bargained for with Collatz Theory. For example, I have developed algorithms for the factorizations of composites consisting of two primes, the Mersenne hailstone sequences, hailstone series equations, and Collatz-Matrix equations.

 

The most helpful for this problem are the Mersenne hailstone sequences, hailstone series equations, and Collatz-Matrix equations. I am getting really close to finding some equation to easily prove a Mersenne number to be a prime. It will just take some more analysis.

 

Hopefully you get one and learn more from you, this will help me further if I take up post graduate degrees.

[Amaton]

Well one can try to find common relationships of each product when two Mersenne primes are added to 1 and divided by each other.

 

 

[math]U = 4^{10^{8}}L + 4^{10^{8}} -1[/math]

 

Yeah, I got to that as well, but it doesn't seem like it could do anything. Because one requires that "+1" for both primes, the relation becomes pretty trivial. We're simply looking at powers of 2 separated arithmetically by a relatively large number, so I don't see how it could shed light on your candidate's primality. However, I may be thinking too superficially, and one could use more indirect logic and make use of it in a proof.

[Unity+]

 

Yeah, I got to that as well, but it doesn't seem like it could do anything. Because one requires that "+1" for both primes, the relation becomes pretty trivial. We're simply looking at powers of 2 separated arithmetically by a relatively large number, so I don't see how it could shed light on your candidate's primality. However, I may be thinking too superficially, and one could use more indirect logic and make use of it in a proof.

Well, a proof could be derived from it. Since the two variables of U and L are prime(assuming), then it could try to prove that after a certain amount of numbers that are derived from the Mersenne formula that it will be prime or not prime.

 

For example, I used the new formula to get more primes than the Mersenne formula, however it took the increase of the exponent n for the 4 values to do so. After a certain while, you have to increase n in order to get more primes as you increase the size of the primes.

[gabrelov]

Well, a proof could be derived from it. Since the two variables of U and L are prime(assuming), then it could try to prove that after a certain amount of numbers that are derived from the Mersenne formula that it will be prime or not prime.

 

For example, I used the new formula to get more primes than the Mersenne formula, however it took the increase of the exponent n for the 4 values to do so. After a certain while, you have to increase n in order to get more primes as you increase the size of the primes.

 

As I was reviewing I remembered that the exponent of 2 is prime so maybe I can create a simple program from visula basic C++ to run a non terminating exponent input on two and so on and forth. The program is relatively easy to make but the problem the processing capability of current computers. I'll test it this upcoming monday and ask some help from my younger brother to create the program.

 

It goes like these: (2^2)-1 = 3 which is prime by law and then substitute it back to (2^3)-1 =7 prime again, and so on and so forth until I reach the maximum possible prime number.

Edited August 3, 2013 by gabrelov

[Amaton]

 

As I was reviewing I remembered that the exponent of 2 is prime so maybe I can create a simple program from visula basic C++ to run a non terminating exponent input on two and so on and forth. The program is relatively easy to make but the problem the processing capability of current computers. I'll test it this upcoming monday and ask some help from my younger brother to create the program.

 

It goes like these: (2^2)-1 = 3 which is prime by law and then substitute it back to (2^3)-1 =7 prime again, and so on and so forth until I reach the maximum possible prime number.

 

If I'm understanding your process correctly, you're basically doing: [math]p_{n+1}=2^{p_{n}}-1[/math] for [math]p_1=2[/math]?

 

The statement is that "For [math]M_n=2^n-1[/math], if [math]M_n[/math] is prime, then [math]n[/math] itself is also prime." However, the converse is not generally true, and so the primality of the resulting numbers in your sequence will be uncertain. Your sequence will get very large very quickly, so you'll be testing extremely large numbers (though I may be misinterpreting your idea).

[Unity+]

 

If I'm understanding your process correctly, you're basically doing: [math]p_{n+1}=2^{p_{n}}-1[/math] for [math]p_1=2[/math]?

 

The statement is that "For [math]M_n=2^n-1[/math], if [math]M_n[/math] is prime, then [math]n[/math] itself is also prime." However, the converse is not generally true, and so the primality of the resulting numbers in your sequence will be uncertain. Your sequence will get very large very quickly, so you'll be testing extremely large numbers (though I may be misinterpreting your idea).

This is the equation I am referring to:

 

[math]U = 4^{n}L + 4^{n} - 1[/math]

 

As the variable L gets larger, so will the variable n over time. For example, once U equals 71 n must be increased to 2 in order to get more prime numbers than when it is equal to 1.

[gabrelov]

 

If I'm understanding your process correctly, you're basically doing: [math]p_{n+1}=2^{p_{n}}-1[/math] for [math]p_1=2[/math]?

 

The statement is that "For [math]M_n=2^n-1[/math], if [math]M_n[/math] is prime, then [math]n[/math] itself is also prime." However, the converse is not generally true, and so the primality of the resulting numbers in your sequence will be uncertain. Your sequence will get very large very quickly, so you'll be testing extremely large numbers (though I may be misinterpreting your idea).

 

I'm sorry but i just got my idea from the theorem that if (2^n)-1 results in a prime then n is also a prime number.

Since Its just a theorem it may hold true for small values here are examples below and to note that n should always be prime to get also prime. Maybe its not true for bigger numbers so I'm gonna test it for bigger numbers.

 

2²-1 = 3

2³-1 = 7

2⁵-1 = 31

2⁷-1 = 127

 

The problem with my equation is that it may be simple but I think computer will not be able to run it when the number reaches so high such as thousands digits. If the computer stops processing there is nothing left doing but back to drawing board.

 

I think I will resort to mathematical equations again and derive and also to be able to get accurate answer.

Edited August 4, 2013 by gabrelov

[Unity+]

I have now been using a prime factorization algorithm to determine if the candidate is a prime number(it is going to take a while). However, it most likely is a prime number and(if my calculations are correct), it is over 18,000,000 digits long. However, I am still doing some calculations to find the precise size of the number.

 

UPDATE: The number is 77,631,169 digits long.

Well, I hope here is some good news.

 

I have used Fermat's Little Theorem to try to predict that it was a prime number, and it seems to be true. You can check my work(if anyone knows Mathematica, here is the code).

Simplify[Mod[2^257885161, 257885161] == Mod[2, 257885161], 
 Element[2, Integers] && Element[257885161, Primes]]

And the result turned out to be true. Also, I found another prime candidate that is over 100,000,000(167,940,168 digits long more exactly) digits long:

Simplify[Mod[2^557885161, 557885161] == Mod[2, 557885161], 
 Element[2, Integers] && Element[557885161, Primes]]

Though Fermat's little theorem may not be proof enough that they are prime, it still gives a hopeful chance that they are.

 

The first prime candidate(with a need of confirmation) is now proven to be a prime using Fermat's Little Theorem and Wilson's Theorem.

FullSimplify[Mod[((2^(257885161) - 1) - 1)!, (2^(257885161) - 1)], 
 Element[(2^(257885161) - 1), Primes]]

Due to some limitations with Mathematica, I will have to work around with the second prime candidate, but it has been proven with Fermat's Little Theorem to be prime.

Edited August 9, 2013 by Unity+

[Unity+]

Here is the sufficient proof of the primality of the first candidate using Wilson's theorem.

 

 

 

If this is true, then the candidate is prime.

 

EDIT: The first candidate has been proven a prime, a Mathematica document will be uploaded to prove as such.

Edited August 9, 2013 by Unity+

[imatfaal]

hmm... are you sure that you are maintaining precision. For a start Mathematica relies on GMP which maxes out at 2^32 - and your number has (let alone its factorial) has more digits than that. How long is it taking mathematica to crunch an answer?

[Unity+]

hmm... are you sure that you are maintaining precision. For a start Mathematica relies on GMP which maxes out at 2^32 - and your number has (let alone its factorial) has more digits than that. How long is it taking mathematica to crunch an answer?

Mathematica's memory for amount of digits depends on the memory of the computer and Mathematica doesn't calculate the value in one try, but relies on an algorithm to calculate all the values(I can tell you that it takes a long time for an output to come out). I know this because I have programmed specific mathematical algorithms involving(which have existed before) to carry out the product larger than the 2^32 limit(though, I have a 64 bit computer, so it would max out at 2^64).

 

Well, for the actual proving of the prime number as it would be confirmed Daedalus is using some program using the NVidia GPU, which will still take some time in order for it to confirm the prime number. I simply used Fermat's Little theorem(which is still not enough to prove it, but states that it most likely is prime).

 

I did recheck Wilson's theorem document and realized there was something wrong. Mathematica did stop it's calculation there(unfortunately). Right now, I am waiting for Daedalus to report whether CUDALucas has determined it to be a prime or not. It will take some time. I am keeping my fingers crossed. I will give him credit if it is prime.

 

Since I am calculating this with Mathematica 9, there is much precision within the process. Though you could argue that computers do make rounding mistakes, which may be relevant to calculation in this circumstance, I don't see any evidence as to this conclusion.

Edited August 13, 2013 by Unity+

[imatfaal]

even a 64 bit computer would top out at 2^37. Note I am not saying that GMP cannot handle numbers bigger than 2^32 - it can handle numbers with 2^32 digits!! But your number has close to that - and its factorial will have far more than that.

Mathematica's memory for amount of digits depends on the memory of the computer and Mathematica doesn't calculate the value in one try, but relies on an algorithm to calculate all the values(I can tell you that it takes a long time for an output to come out). I know this because I have programmed specific mathematical algorithms involving(which have existed before) to carry out the product larger than the 2^32 limit(though, I have a 64 bit computer, so it would max out at 2^64).

 

Well, for the actual proving of the prime number as it would be confirmed Daedalus is using some program using the NVidia GPU, which will still take some time in order for it to confirm the prime number. I simply used Fermat's Little theorem(which is still not enough to prove it, but states that it most likely is prime).

 

I did recheck Wilson's theorem document and realized there was something wrong. Mathematica did stop it's calculation there(unfortunately). Right now, I am waiting for Daedalus to report whether CUDALucas has determined it to be a prime or not. It will take some time. I am keeping my fingers crossed. I will give him credit if it is prime.

 

Since I am calculating this with Mathematica 9, there is much precision within the process. Though you could argue that computers do make rounding mistakes, which may be relevant to calculation in this circumstance, I don't see any evidence as to this conclusion.

 

If you look back at my initial response you will notice that I gave you how long it took for the largest mersenne prime to be checked on a GPU. It took 3 and a bit days.

 

Your number is almost exactly 2^200,000,000 times bigger than that number. How long do you think it is gonna take to run that check?

 

 

BTW Fermat Pseudoprimes satisfy the fermat little and yet are composite.

 

BTW 2 Lucas - Lehmer is a probabilistic test - and not deterministic. The deterministic are much much longer

[Unity+]

even a 64 bit computer would top out at 2^37. Note I am not saying that GMP cannot handle numbers bigger than 2^32 - it can handle numbers with 2^32 digits!! But your number has close to that - and its factorial will have far more than that.

 

If you look back at my initial response you will notice that I gave you how long it took for the largest mersenne prime to be checked on a GPU. It took 3 and a bit days.

 

Your number is almost exactly 2^200,000,000 times bigger than that number. How long do you think it is gonna take to run that check?

 

 

BTW Fermat Pseudoprimes satisfy the fermat little and yet are composite.

 

BTW 2 Lucas - Lehmer is a probabilistic test - and not deterministic. The deterministic are much much longer

Well...I don't know then. I guess that ends my search. I don't really have the resources to do anything of this magnitude at this moment.

[imatfaal]

take a look at the great internet mersenne prime search - and take heart! They use distributed computing - maybe whilst you wait for inspiration you can join in

[Unity+]

take a look at the great internet mersenne prime search - and take heart! They use distributed computing - maybe whilst you wait for inspiration you can join in

But I already have.

[Unity+]

I just noticed that there is a test feature in the Prime95 program to test specific primes. This will come in handy.

 

Since the iteration is at 12678/257885161(approximately, I altered some iteration counts so that it only shows it for a certain amount). It will take a while, but with Prime95 it should work(unless they are also not reliable).

Edited August 15, 2013 by Unity+

[gabrelov]

I am very sorry sir I cannot help you yet since my exams are approaching near and I am very nervous already and really spending all my time studying. I hope you understand.

[Unity+]

Apparently the prime was already tested before(supposedly the error Prime95 gave me indirectly states this).

 

Well, at least things were learned.

[imatfaal]

Sorry - I never thought to check if it had already been factored

 

http://www.mersenne.org/report_exponent/?exp_lo=257885161&exp_hi=257885171&B1=Get+status

[Unity+]

Sorry - I never thought to check if it had already been factored

 

http://www.mersenne.org/report_exponent/?exp_lo=257885161&exp_hi=257885171&B1=Get+status

What strikes me is the fact that it says that even the highest number that the software can do is already factored, which means no more tests can be done until they update the software to do higher calculations.

[imatfaal]

What strikes me is the fact that it says that even the highest number that the software can do is already factored, which means no more tests can be done until they update the software to do higher calculations.

 

mmm - Unless they went straight to the end of the book and read the last page to the largest number they could test and did that as a proof of concept - but there are still oodles of numbers to test in between the ceiling (ie every possibility tested below) and the maximum. I must admit if I had a new program and lots of run time I would probably "shoot for the moon" and go for the highest possibility first - when that failed I would be sensible and start marking off from the already established ceiling.

[gabrelov]

Sir Unity may I ask what happened?

 

Hve you found out if that is a prime?

[Unity+]

Sir Unity may I ask what happened?

 

Hve you found out if that is a prime?

It turned out that the number was already tested not to be a prime.

[gabrelov]

It turned out that the number was already tested not to be a prime.

 

What a sad conclusion

[imatfaal]

 

What a sad conclusion

Oh I don't know about that... I learnt a lot from the thread and I hope Unity did as well; that seems a pretty good (even if not optimal) outcome