[Math] Prime number progression?!

On April 22 2011 08:03 Starfox wrote:
You are looking at http://en.wikipedia.org/wiki/Mersenne_prime basically. If you'd be abelt to proof that every step produces a prime you would be the candidate for the next fields medal for sure. :D

On April 22 2011 08:03 Starfox wrote:
You are looking at http://en.wikipedia.org/wiki/Mersenne_prime basically.

On April 22 2011 08:05 graNite wrote:
Will do.

Anyone with a supercomp here? Need a5 - a100 :D

On April 22 2011 08:35 Rtran10 wrote:
2^8 = 256. (2^8)-1 = 255. 255 is not prime. Am i doing this right?

On April 22 2011 08:45 SonuvBob wrote:
TL is not here to do your homework for you.

edit: reopened. apparently this is an unsolved problem, so even if it is his homework, no one can do it for him. :p

On April 22 2011 12:50 micronesia wrote:
Haha my initial insticts were right! I was gonna leave this open then when I saw SoB close it I was like "hmmmm it DOES sound like a hw thread" but... GOOD LUCK. Whoever solves it gets my <3

On April 22 2011 12:43 Antisocialmunky wrote:


The OP needs to rephrase his question so its not so easy to misread. I had to read it like 5 times.

On April 22 2011 07:48 graNite wrote:
with

it produces:

2
3
7
127
...

how can i prove that every number coming of this progression is prime?
if that's not possible, how can i disprove it?

On May 15 2011 08:11 VIB wrote:
That one is easy. All that problem is saying is that a number X, if multiplied by itself a prime number of times minus 1 (itself) will always be a prime number.

It's obviously this will only be true if X = 48÷2(9+3)

Since 48÷2(9+3)=2 then all the output of that sequence are prime numbers.

Next?

On April 22 2011 08:40 cgrinker wrote:
Not that such a sequence exists yet but

You would want to use an inductive proof to show that the next element in the sequence satisfied your constraint.

which it doesn't.

On May 15 2011 08:15 Samhax wrote:


Man what are you smoking? If you can find a sequence with only prime numbers it's fucking huge! I don't think you realise what you are saying...

On May 15 2011 08:20 mcc wrote:

I suppose he is trolling using the formula from the infamous "math" thread about notations.

On May 15 2011 08:44 dUTtrOACh wrote:
The only way to test if it produces only prime numbers is to run divisibility tests on the answers for each case. You could write a program which can store the ridiculously large integers produced. Each will need to be tested for divisibility using modulus. Probably fairly time consuming. And when do you stop testing it?

On May 15 2011 08:46 Samhax wrote:


I dont think the op has the computer to do it, but i'm pretty the answer is no but you need a super computer to prove it or if he is lucky the first non prime number is not that big.

On May 15 2011 08:44 dUTtrOACh wrote:
The only way to test if it produces only prime numbers is to run divisibility tests on the answers for each case.

On May 15 2011 08:52 VIB wrote:
You do realize "each case" is infinite right? If anyone ever solves this problem, it's not gonna be by making a computer bigger than infinite

On May 15 2011 08:48 dUTtrOACh wrote:


That's basically my point.

[...]

In mathematics, a Mersenne number, named after Marin Mersenne (a French monk who began the study of these numbers in the early 17th century), is a positive integer that is one less than a power of two:

M_p=2^p-1

Some definitions of Mersenne numbers require that the exponent p be prime, since the associated number must be composite if p is.

A Mersenne prime is a Mersenne number that is prime. It is known[2] that if 2p − 1 is prime then p is prime, so it makes no difference which Mersenne number definition is used. As of October 2009, 47 Mersenne primes are known. The largest known prime number (243,112,609 − 1) is a Mersenne prime.[3] Since 1997, all newly-found Mersenne primes have been discovered by the "Great Internet Mersenne Prime Search" (GIMPS), a distributed computing project on the Internet.

[...]

Many fundamental questions about Mersenne primes remain unresolved. It is not even known whether the set of Mersenne primes is finite. The Lenstra–Pomerance–Wagstaff conjecture asserts that, on the contrary, there are infinitely many Mersenne primes and predicts their order of growth. It is also not known whether infinitely many Mersenne numbers with prime exponents are composite, although this would follow from widely believed conjectures about prime numbers, for example, the infinitude of Sophie Germain primes congruent to 3 (mod 4).

A basic theorem about Mersenne numbers states that in order for Mp to be a Mersenne prime, the exponent p itself must be a prime number. This rules out primality for numbers such as M4 = 24 − 1 = 15: since the exponent 4 = 2×2 is composite, the theorem predicts that 15 is also composite; indeed, 15 = 3×5. The three smallest Mersenne primes are

M2 = 3, M3 = 7, M5 = 31.

While it is true that only Mersenne numbers Mp, where p = 2, 3, 5, … could be prime, often Mp is not prime even for a prime exponent p. The smallest counterexample is the Mersenne number

M11 = 211 − 1 = 2047 = 23 × 89,

which is not prime, even though 11 is a prime number. The lack of an obvious rule to determine whether a given Mersenne number is prime makes the search for Mersenne primes an interesting task, which becomes difficult very quickly, since Mersenne numbers grow very rapidly. The Lucas–Lehmer primality test (LLT) is an efficient primality test that greatly aids this task. The search for the largest known prime has somewhat of a cult following. Consequently, a lot of computer power has been expended searching for new Mersenne primes, much of which is now done using distributed computing.

On May 15 2011 09:03 Samhax wrote:
Wikipedia give the larger Mersenne prime number 2^43 112 609 -1 discovered and 2^(2^127-1) -1 is bigger. So there is no way to prove it even with a super computer.

Close the post :p

On May 15 2011 09:08 Mithrandir wrote:
This is an unsolved problem.

These are Catalan-Mersenne Prime Numbers.

http://en.wikipedia.org/wiki/Double_Mersenne_number#Catalan-Mersenne_number

To the OP, please don't post unsolved problems and waste peoples' time.

On May 15 2011 09:08 ZerGuy wrote:


Actually it's perfectly possible that this particular number can be proved as composed. It's just not known to be prime.

On May 15 2011 09:12 Sufficiency wrote:
I seriously doubt you have given a formula that always produces prime number.

Thus, I suggest you should compute a few iterations and check if they are primes.

On May 15 2011 09:08 ZerGuy wrote:

Was OP just a troll? So rude.

On May 15 2011 09:20 aoeua wrote:
I have discovered a truly marvellous solution for this problem. Unfortunately, the post width here is too narrow to contain it.

On May 15 2011 09:21 Samhax wrote:


Haha Fermat quote, but Andrew Wiles did it!

On May 15 2011 08:57 Samhax wrote:


Maybe 2^127 -1 is not prime, if the op is lucky. But if 2^127 -1 is prime then you need for sure a super computer to prove it.

On May 15 2011 10:32 blah_blah wrote:


2^{127}-1 is prime.

On May 15 2011 08:57 Samhax wrote:
Maybe 2^127 -1 is not prime, if the op is lucky. But if 2^127 -1 is prime then you need for sure a super computer to prove it.

On May 15 2011 11:26 Wonders wrote:


This number was known to be prime in 1876, when they didn't have supercomputers. Even then there were much better techniques for testing primality than exhaustively checking divisibility.

On May 15 2011 09:20 aoeua wrote:
I have discovered a truly marvellous solution for this problem. Unfortunately, the post width here is too narrow to contain it.

On May 15 2011 11:51 NB wrote:
one of the rule of TL is do not ask homework here!

about the math problem, use induction (basic 1st year math)

On May 15 2011 11:41 Samhax wrote:


I didn't say for 2^127 -1 you need a super computer, this number is "relatively" small (~10^38). But for 2^(2^127-1) -1, show me how you can do it whitout a super computer, knowing that 2^127 -1 is prime. I really want to see that.

edit : when i talked about super computer, i was talking about the next iterations.

On May 15 2011 11:55 Mithrandir wrote:


2^(2^127-1)-1 cannot be done even with today's super computers, although people have checked all possible factors up to 10^50 without success.

On May 15 2011 12:00 Samhax wrote:


Yeah i know, but knowing the size of the number it's impossible to test it without computers. It's my point.

On May 15 2011 12:07 arbiter_md wrote:

If you'd put all the computers in the world to work on this problem for the next 10 billion years, you wouldn't yet know if that number is really prime. Assuming it is prime.

That's how big that number is. Math has many simple ways to tell the people that some questions will never get responses.

On May 15 2011 18:08 Manit0u wrote:
On a sidenote: I've noticed an increasing amount of posts starting with 'hi TL' or something like that. It seems similar to 'sub /b/' or whatever.
Anyway, my point is, why the hell would you use 'hi TL' on a TL? Just 'Hi!' would be enough in my opinion. There's no need for redundant stuff, especially one that shares some similarities with 4chan...

On May 15 2011 12:07 arbiter_md wrote:

If you'd put all the computers in the world to work on this problem for the next 10 billion years, you wouldn't yet know if that number is really prime. Assuming it is prime.

That's how big that number is. Math has many simple ways to tell the people that some questions will never get responses.