Prime Numbers

endfx

So I just heard about the new prime number that was discovered and for some reason got kind of interested in it.

So I'm looking at prime number tables on various webpages that show the prime numbers, dates discovered, etc.

I'm confused on what the "digits" column in these tables means.

For example, the prime number 5 has 2 digits, and the prime number 13 has 4 digits. What are these digit numbers?
How do you get 2 digits from the prime number 5?

Thanks.

Muzza

Was this the list you were looking at? It doesn't say that 5 has 2 digits or that 13 has 4 digits, it says that 2^5 - 1 (i.e. 31) has 2 digits and that 2^13 - 1 (i.e. 8191) has 4 digits.

endfx

The tables I was looking at were like that, but that wasn't the particular page I was viewing. But thanks for explaining it to me, as well, thanks a lot for that link. It like how it explains the history of primes and why they are imporant.

Gokul43201

endfx, you might want to Google "Mersenne Primes"

strid

just read a on the net that there are only 41 such numbers!!

how come... cant you just insert any prime number into 2^p -1??

so if we want to find a BIG one we can take the present biggest and insert it into 2^p-1....or?

Gokul43201

Not all prime p in the above formula give Mersenne Primes. For instance (2^11)-1 = 2047 = 23*89

shmoe

42 known now, see the GIMPS webpage (there's a recent post in this forum about it too). The known is an important distinction, there may be many more (possibly infinitely many).

Galileo

[tex]2^{25,964,951}-1[/tex]

It has 7,816,230 digits......yikes!

You can fill a phone book with it (I think).

Zurtex

I think you'll find you've added an extra 2 there and I really doubt it about the phone book, consider in England, way way over 1 million people have phones and we all have 11 digits (including area code).

Icebreaker

Why is it yet impossible to devise a function which correlates a number with a prime number?

shmoe

Why do you say it's impossible? let p(n)=the nth prime number, there's your function. There are also plenty of formulas that spit out primes, none really computationally useful though.


I took a look at my local phonebook (Toronto area) and it appears to hold something like 25,000 characters per page (roughly 200 across and 125 lines per page). So this new Mersenne prime would be over 300 pages, but the book itself has over 2000 pages. So it falls shot of the toronto phonebook size, but it's probably on par with some smaller canadian cities.

Icebreaker

let p(n) = the nth prime number is useless in predicting the nth prime, if n > the largest prime we know

shmoe

It's worse than that. We don't come anywhere near knowing all the primes less than the largest known one. My point was there are functions that map the naturals to the primes, there are even ones that look less cheap then my p(n) one. There are also asymptotics for p(n), and other formulas who output only primes, and that nasty polynomial in many (26?) variables whose positive values equals the set of primes. All are intersting, none really computationally friendly. Here's a nice collection from mathworld:

http://mathworld.wolfram.com/PrimeFormulas.html

Galileo

Dutch phonebooks aren't that big
I checked. About 6000 numbers will fit per page and we have about 1000 pages. So roughly 6,000,000 digits will fit.
So in retrospect, the new Mersenne prime will fill a dutch phone book.

T.Rex

Since there is a prize of $ 100.000 for the discoverer of a Mersenne prime number of more than 10 millions characters, GIMPS addicts are now searching with exponents larger than 34.000.000 . So, maybe M43 (or M44) could not fit in any phonebook on earth ...
See: Internet PrimeNet Server and : GIMPS .
Tony

robert Ihnot

I think it useful to discuss what are the general capacities of "code crackers" to find prime factors in "large numbers." Well, about 20 years ago it was generally thought that if two 100 digit primes were multiplied together it was as a practical matter impossible to factor this 200 digit number. This fact was used in constructing secret codes.

Well, today on the internet I found this: This function creates keys using the method described in the Procedure section. It first generates two 100-digit prime numbers p and q by initializing them both to 10100 and incrementing them by 1 and -1, respectively. Each time they are incremented, they are tested for primality. In this way, p and q were found to be:....

The writer then is suggesting that as a general rule such 200 digit numbers can not be factored as a practical matter. http://ashvin.flatirons.org/projects...e/results.html

You have to understand that a Mersenne prime is a special case where mathematicians and programmers use special criterion to work with.

T.Rex

True. But the Maths used for proving the primality of Mersenne numbers can be used for proving the primality of other kinds of numbers, like Fermat numbers, or many other numbers. But this kind of Maths seems to be less and less used and teached, as far as I know (but I'm NOT a mathematician). Don't know why.
Tony