hi tl
i saw a few math topics recently and noticed there are some good mathematics here.
i have a prime number problem and can't solve it.

lets look at this progression (is progression the right word?)

[image loading]

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?

ty

Bibdy

United States3481 Posts

April 21 2011 22:50 GMT

I haven't done mathematical proofs in donkey's years, but I recall the easiest way to disprove something is to find one specific scenario where the rule doesn't work. That's enough to can the whole formula.

graNite

Germany4434 Posts

April 21 2011 22:51 GMT

the problem is that the numbers get really high really fast.
after 127 comes 2^127-1 ... (which is prime)

Starfox

Austria699 Posts

April 21 2011 23:03 GMT

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

graNite

Germany4434 Posts

April 21 2011 23:05 GMT

Will do.

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

Antisocialmunky

United States5912 Posts

April 21 2011 23:05 GMT

:\ can't you google your homework?

The proof is on wiki.

gogogadgetflow

United States2583 Posts

April 21 2011 23:08 GMT

If his homework is interesting in and of itself and generates discussion I think he has the right to share it. Of course math isn't my strong suit so I can't say if its interesting or not :p

JingleHell

United States11308 Posts

April 21 2011 23:11 GMT

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

Isn't there a cash bounty for calculating new Mersenne primes?

qrs

United States3637 Posts

April 21 2011 23:12 GMT

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

Well...a tiny subset of Mersenne primes, anyway.

stepover12

United States175 Posts

April 21 2011 23:19 GMT

#10

I was thinking about how to prove it using fermat's little theorem... but according to wiki it is still an open question

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

"Although the first five terms (up to M(127)) are prime, no known methods can decide if any more of these numbers are prime (in any reasonable time) simply because the numbers in question are too huge, unless a factor of M(M(127)) is discovered."

Primadog

United States4411 Posts

April 21 2011 23:20 GMT

#11

[edit] sorry, I don't know what I am talking about.

mcc

Czech Republic4646 Posts

April 21 2011 23:23 GMT

#12

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

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

I don't think any computer will help you to do that. a5 = M127 and is a prime, but above that you are too far out.

If you would be able to prove your statement, then you would have solved one of important unsolved mathematical problems and I do not think anyone here can really help you with that

Basically if I see it correctly you would have proven that there is infinite number of Mersenne primes.

EDIT:typo

ptrpb

Canada753 Posts

April 21 2011 23:26 GMT

#13

RECURSIVE INDUCTION
FUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
Just finished a course on this stuff, but I've forgotten most of it sorry man.
Best of luck though

MisterD

Germany1338 Posts

April 21 2011 23:27 GMT

#14

i tried ..

(01:24) gp > a = 2
%1 = 2
(01:24) gp > a = 2 ^ a - 1
%2 = 3
(01:24) gp > a = 2 ^ a - 1
%3 = 7
(01:24) gp > a = 2 ^ a - 1
%4 = 127
(01:24) gp > a = 2 ^ a - 1
%5 = 170141183460469231731687303715884105727
(01:24) gp > a = 2 ^ a - 1
*** length (lg) overflow

so .. a5 works, a6 does not work anymore^^ it's a little big.

so for a5:

(01:24) gp > a
%6 = 170141183460469231731687303715884105727
(01:25) gp > factor(a)
%7 = [170141183460469231731687303715884105727 1]

meaning a5 is still prime.

Day[9]

United States7366 Posts

April 21 2011 23:29 GMT

#15

2^67 - 1 = 147,573,952,589,676,412,927 = 193,707,721 x 761,838,257,287

So 2^67 isn't prime : ]

Cheers!

Day[9]

United States7366 Posts

April 21 2011 23:30 GMT

#16

Oh shit I misread your post, I thought you were asking about Marsenne primes in general. Agh I'm such a doof

Primadog

United States4411 Posts

April 21 2011 23:32 GMT

#17

Can we start nominating Day9 for the fields medal yet?

Oracle

Canada411 Posts

April 21 2011 23:32 GMT

#18

If there were a way to prove that this progression results in primes then people wouldn't be paid $100,000 to find the next largest prime, since 2^a_n - 1 where an is some arbitrarily large prime in that sequence is prime.... we could theoretically have infinitely many large primer numbers, bigger than the largest known prime number.... unless my logic doesnt follow

But what you might say is that youre looking for an upper bound on n for which this statement holds true?

In that case, run a fast fourier transform primality test on a supercomputer with this progession, and hope there exists an n which breaks this progression