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

## Recommended Posts

So, I tried to determine if this is a prime number:

$2^{257885161} - 1$

If this is a prime number, it will be the largest known prime, but if not then okay. Is there a quick way to tell? I tried dividing it by other numbers, yet after a long, long set of calculations I have found no factors yet(though I did this in Mathematica so it may be wrong).

Edited by Unity+
##### Share on other sites

There a couple of ways you can check to see if a number is likely to be a prime.

Also, you can look at the Miller-Rabin primality test which actually proves if a number is composite (not prime). If the test fails, you've likely got a prime on your hands.

##### Share on other sites

There is a specialized test to see if these Mersenne numbers are prime or not: http://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test don't expect it to be quick, though. You have a fairly large number on your hands there.

Edited by Bignose
##### Share on other sites

There is a specialized test to see if these Mersenne numbers are prime or not: http://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test don't expect it to be quick, though. You have a fairly large number on your hands there.

Well, so far I have tried it with factor such as 3, 11, and 13 and so far it is passing the test. I don't know what I am accomplishing by doing this, though if this is truly a prime then it is the largest known prime now.

##### Share on other sites

So, I tried to determine if this is a prime number:

$2^{257885161} - 1$

If this is a prime number, it will be the largest known prime, but if not then okay. Is there a quick way to tell? I tried dividing it by other numbers, yet after a long, long set of calculations I have found no factors yet(though I did this in Mathematica so it may be wrong).

hmm - thats the largest mersenne prime with a 2 added at the beginning of the exponent! Any reason you think it might be a prime - or gut instinct?

just for your info - here is a quote from the GIMPS page on the pc time for checking the current largest prime (which is dwarfed by your candidate)

The primality proof took 39 days of non-stop computing on one of the University of Central Missouri's PCs. To establish there were no errors during the proof, the new prime was independently verified using different programs running on different hardware. Jerry Hallett verified the prime using CUDALucas running on a NVidia GPU in 3.6 days. Dr. Jeff Gilchrist verified the find using the standard GIMPS software on an Intel i7 CPU in 4.5 days. Finally, Serge Batalov ran Ernst Mayer's MLucas software on a 32-core server in 6 days (resource donated by Novartis IT group) to verify the new prime.

##### Share on other sites

hmm - thats the largest mersenne prime with a 2 added at the beginning of the exponent! Any reason you think it might be a prime - or gut instinct?

just for your info - here is a quote from the GIMPS page on the pc time for checking the current largest prime (which is dwarfed by your candidate)

Merely gut instinct more than anything. However, I have been making an analysis of the prime numbers through out history and I noticed a pattern of ratios.

The ratio between the variable p of Mersenne primes and the amount of digits they have seems to be close to 3.32. I am trying to determine if there is a constant, and coincidentally this value seems to follow the ratio.

UPDATE: I am still going up the prime list to see if it remains prime, and it is still succeeding(slowly, very very slowly).

Edited by Unity+
##### Share on other sites

"The ratio between the variable p of Mersenne primes and the amount of digits they have seems to be close to 3.32. I am trying to determine if there is a constant,"

For reasonably big numbers the ratio will tend to a constant.

Consider these numbers

1,10,100,1000 est

They have lengths of 1,2,3 etc.

Their logs(base 10) are 0,1,2,3

So, the number of digits a big number has is roughly proportional to the log of the number

The numbers you are looking at are of the form 2^n ( the -1 hardly matters)

and the log (base 10) of 2^n is also roughly proportional to n

So you are looking at two sets of numbers which are both proportional to n.

So they will also be proportional to each-other.

The number may be prime, but that has nothing to do with the ratio of the length of a number expressed in base 2 being proportional to the length expressed in base 10.

Try it with numbers that are not prime.

2^n has roughly n/3 digits

This page says it a whole lot better than I did
http://onlinelibrary.wiley.com/doi/10.1002/9780470124604.app15/pdf

##### Share on other sites

"The ratio between the variable p of Mersenne primes and the amount of digits they have seems to be close to 3.32. I am trying to determine if there is a constant,"

For reasonably big numbers the ratio will tend to a constant.

Consider these numbers

1,10,100,1000 est

They have lengths of 1,2,3 etc.

Their logs(base 10) are 0,1,2,3

So, the number of digits a big number has is roughly proportional to the log of the number

The numbers you are looking at are of the form 2^n ( the -1 hardly matters)

and the log (base 10) of 2^n is also roughly proportional to n

So you are looking at two sets of numbers which are both proportional to n.

So they will also be proportional to each-other.

The number may be prime, but that has nothing to do with the ratio of the length of a number expressed in base 2 being proportional to the length expressed in base 10.

Try it with numbers that are not prime.

2^n has roughly n/3 digits

This page says it a whole lot better than I did

http://onlinelibrary.wiley.com/doi/10.1002/9780470124604.app15/pdf

Though thank you for the information, it does not prove this number I have here not to be prime(unless someone has proven that it is not prime, which then I will discontinue my tests).

##### Share on other sites

out of curiosity Unity - how are you checking. I dont think I have access to any programme that could divide a 77 million digit number by another number.

btw

1. If my memory serves correct and brief checking tends to confirm - you will not find a factor for a mersenne prime candidate smaller than (2*exponent)+1. So you gotta start pretty high!

2. Try 4126162577

##### Share on other sites

http://en.wikipedia.org/wiki/Prime_number_theorem

Just elaborating Cuthber's obvservation above.

The answer to the OP question, about a quick way to check - nobody knows. If you find one, write it down and tell people about it.

##### Share on other sites

out of curiosity Unity - how are you checking. I dont think I have access to any programme that could divide a 77 million digit number by another number.

btw

1. If my memory serves correct and brief checking tends to confirm - you will not find a factor for a mersenne prime candidate smaller than (2*exponent)+1. So you gotta start pretty high!

2. Try 4126162577

I am using Mathematica to check this. It is a pretty useful tool, especially with prime numbers. Though it takes a few minutes to do, it is efficient.

I will try that. I'll tell what I find.

http://en.wikipedia.org/wiki/Prime_number_theorem

Just elaborating Cuthber's obvservation above.

The answer to the OP question, about a quick way to check - nobody knows. If you find one, write it down and tell people about it.

Well until I heard about what John was talking about I was going to use a ratio system. I don't really care if this is a prime number, though of it is then okay. This is merely just to the benefit of learning about prime numbers in general.

EDIT: 4126162577 is not a factor of the number. I'll keep searching for one.

Edited by Unity+
##### Share on other sites

I have tested many factors with this candidate and so far it is showing to be prime. I have even tested the value with $2^{57885161}- 1$.

Edited by Unity+
##### Share on other sites

I have tested many factors with this candidate and so far it is showing to be prime. I have even tested the value with $2^{57885161}- 1$.

If 257885161 is prime, then 2^257885161 - 1 won't be divisible by anything of the form 2^n - 1 for any n other than 1 and 257885161.

=Uncool-

##### Share on other sites

So, I tried to determine if this is a prime number:

$2^{257885161} - 1$

If this is a prime number, it will be the largest known prime, but if not then okay. Is there a quick way to tell? I tried dividing it by other numbers, yet after a long, long set of calculations I have found no factors yet(though I did this in Mathematica so it may be wrong).

obviously the 2^n is a composite number due to the fact it is divisible by two, unless we subtract 1 which gives a probability of it being prime or composite. Have you tried to get the answer sir two the equation and maybe we can apply laws of exponent and functions such as logaritmic to determine if there are possible factors or something that would make it composite.

Maybe people here would really help to find another prime number with mathematical eqautions to put this forums in the headlines.

Edited by gabdecena
##### Share on other sites

obviously the 2^n is a composite number due to the fact it is divisible by two, have you tried to get the answer sir two the equation and maybe we can apply laws of exponent and functions such as logaritmic to determine if there are possible factors or something that would make it composite.

Maybe people here would really help to find another prime number with mathematical eqautions to put this forums in the headlines.

Using mathematica I haven't find any proof that it is composite, though I could be wrong. I am currently trying to use other methods(it is taking a while).

##### Share on other sites

Using mathematica I haven't find any proof that it is composite, though I could be wrong. I am currently trying to use other methods(it is taking a while).

Are you looking for a mersene prime number. have you generated the answer to the equation, if its something like 1111111.......1111 there is a big possibility its a prime number.

By theorem:

Theorem Two: If 2n-1 is prime, then so is n.

Source:

http://primes.utm.edu/mersenne/

so first you need to determine if your exponent is a prime number

you would need to test it using the mersene form again such 2^n-1 = 257885161 and use logarithm and determine if n is whole number if not then there is a big chance its a prime number. By my calculations the value of n results in a whole number with a decimal value thus the number is not a result of 2 and its exponent.

Lets help one another in this forum if we suceed in getting another prime we win an award here and this site will be appreciated:

"GIMPS software was developed by founder, George Woltman, in Orlando, Florida. Scott Kurowski, in San Diego, California, wrote and maintains the PrimeNet system that coordinates all the GIMPS clients. Volunteers have a chance to earn research discovery awards of $3,000 or$50,000 if their computer discovers a new Mersenne prime. GIMPS' next major goal is to win the $150,000 award administered by the Electronic Frontier Foundation offered for finding a 100 million digit prime number." Source: http://www.mersenne.org/various/57885161.htm ALTHOUGH the computer will generate a number as such for about a week and no guarantee of success, but there is nothing wrong for trying Edited by gabdecena ##### Link to comment ##### Share on other sites Are you looking for a mersene prime number. have you generated the answer to the equation, if its something like 1111111.......1111 there is a big possibility its a prime number. By theorem: Theorem Two: If 2n-1 is prime, then so is n. Source: http://primes.utm.edu/mersenne/ so first you need to determine if your exponent is a prime number you would need to test it using the mersene form again such 2^n-1 = 257885161 and use logarithm and determine if n is whole number if not then there is a big chance its a prime number. By my calculations the value of n results in a whole number with a decimal value thus the number is not a result of 2 and its exponent. Lets help one another in this forum if we suceed in getting another prime we win an award here and this site will be appreciated: "GIMPS software was developed by founder, George Woltman, in Orlando, Florida. Scott Kurowski, in San Diego, California, wrote and maintains the PrimeNet system that coordinates all the GIMPS clients. Volunteers have a chance to earn research discovery awards of$3,000 or $50,000 if their computer discovers a new Mersenne prime. GIMPS' next major goal is to win the$150,000 award administered by the Electronic Frontier Foundation offered for finding a 100 million digit prime number."

Source:

http://www.mersenne.org/various/57885161.htm

ALTHOUGH the computer will generate a number as such for about a week and no guarantee of success, but there is nothing wrong for trying

So, is there a big chance that the candidate that is presented is a prime? Well, that brings up success for my research.

Edited by Unity+
##### Share on other sites

The answer to the question which forms the title of this thread is no.

That's why there's a prize on offer.

##### Share on other sites

Let's call your candidate U and the current largest known prime L. From what imatfaal noted concerning the exponent, we know that...

$\dfrac{U+1}{L+1}=4^{10^8}$

I thought this relation might provide some insight using the knowledge that L is prime, but it has yet to yield anything significant. (now I'm not sure why it even might)

##### Share on other sites

Let's call your candidate U and the current largest known prime L. From what imatfaal noted concerning the exponent, we know that...

$\dfrac{U+1}{L+1}=4^{10^8}$

I thought this relation might provide some insight using the knowledge that L is prime, but it has yet to yield anything significant. (now I'm not sure why it even might)

Well one can try to find common relationships of each product when two Mersenne primes are added to 1 and divided by each other. $U = 4^{10^{8}}L + 4^{10^{8}} -1$

It would be interesting if this equation were true for all Mersenne primes.

Edited by Unity+
##### Share on other sites

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

Its almost impossible to do divsion manually to check if its prime so others create their own programs which do the task for them. We only want to determine if the number would be a mersene prime. There are many other ways to do so. But what i wanted to do, is use only mathematical equations to prove that it is a prime number which is really hard considering almost all the mersene prime are computer generated.

We cannot depend solely on computer since it only follows set of instruction unlike human which is intelligent and can create new equations from almost nothing.

Edited by gabdecena
##### Share on other sites

Let's call your candidate U and the current largest known prime L. From what imatfaal noted concerning the exponent, we know that...

$\dfrac{U+1}{L+1}=4^{10^8}$

I thought this relation might provide some insight using the knowledge that L is prime, but it has yet to yield anything significant. (now I'm not sure why it even might)

The modified equation that you presented is actually more efficient than the Mersenne formula based on this sample:

15 3 Prime

23 Prime 5 Prime
31 Prime 7 Prime
47 Prime 15
55 31 Prime
71 Prime 63
79 Prime 127 Prime
95 255
119 511
127 Prime 1023
151 Prime 2047
167 Prime 4095
175 8191 Prime
191 Prime 16383
215 32767
239 Prime 65535
247 131071 Prime
271 Prime 262143
1151 Prime 524287
1183 1048575
1279 Prime 2097151
1343 4194303
1439 Prime 8388607
1567 Prime 16777215
1631 33554431
1663 Prime 67108863
1727 134217727
1759 Prime 268435455
1823 Prime 536870911
2047 1073741823

While, in this set, 56% of all using the new method are prime while for the other it is 22%.

Its almost impossible to do divsion manually to check if its prime so others create their own programs which do the task for them. We only want to determine if the number would be a mersene prime. There are many other ways to do so. But what i wanted to do, is use only mathematical equations to prove that it is a prime number which is really hard considering almost all the mersene prime are computer generated.

We cannot depend solely on computer since it only follows set of instruction unlike human which is intelligent and can create new equations from almost nothing.

Well I applied Collatz Theory to Mersenne primes and have made some progress, but I am trying to find properties right now of Mersenne primes that separate them from the Mersenne numbers, which are numbers that just come out of the Mersenne formula whether prime or not.

##### Share on other sites

So, I tried to determine if this is a prime number:

$2^{257885161} - 1$

If this is a prime number, it will be the largest known prime, but if not then okay. Is there a quick way to tell?

No. No quick or easy way to tell.

There was a movie once where some writer postulated that prime numbers could be easily figured out. It was... the movie was... it was "Sneakers" I think.

Anyhow, the plot of the movie is basically correct. If you can quickly solve prime numbers then you can crack internet encryption. You could bust into Wall Street. You could steal billions of dollars.

Basically, asking "is this number easily figurative as prime", is like asking if you can break every information safe ever made.

The answer is so far... no.

##### Share on other sites

The modified equation that you presented is actually more efficient than the Mersenne formula based on this sample:

While, in this set, 56% of all using the new method are prime while for the other it is 22%.

Well I applied Collatz Theory to Mersenne primes and have made some progress, but I am trying to find properties right now of Mersenne primes that separate them from the Mersenne numbers, which are numbers that just come out of the Mersenne formula whether prime or not.

Keep going I'm sorry I cant help you yet this time, I'm reviewing for my upcoming licensure examination for about 3 more months, maybe after the exam i can focus on what I want and hopefully take a PhD degree.

Hopefully we can apply other higher mathematics to solve that and produce another formula, for now I cannot study on that yet since our subject is too wide and we only tackled basics of the advance mathematics. I joined this forum so I could also learn from others here and I am happy I joined because some got my interest such as your problem.

Edited by gabdecena
##### Share on other sites

Keep going I'm sorry I cant help you yet this time, I'm reviewing for my upcoming licensure examination for about 3 more months, maybe after the exam i can focus on what I want and hopefully take a PhD degree.

Hopefully we can apply other higher mathematics to solve that and produce another formula, for now I cannot study on that yet since our subject is too wide and we only tackled basics of the advance mathematics. I joined this forum so I could also learn from others here and I am happy I joined because some got my interest such as your problem.

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.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account