What Do Digit Counts Mean in Prime Number Tables?

[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... can't 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]

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

how come... can't 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?

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

 

[shmoe]

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

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]

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).

$$2^{25,964,951}-1$$

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

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

 

[Zurtex]

$$2^{225,964,951}-1$$

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

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

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 is it yet impossible to devise a function which correlates a number with a prime number?

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]

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

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 interesting, none really computationally friendly. Here's a nice collection from mathworld:

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

 

[Galileo]

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.

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]

10 millions characters.

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

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/crackingthecode/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]

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

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

 

[mathwonk]

We have to also realize that code crackers are clever people, and if they know or suspect that two 100 digit numbers were used to generate the 200 digit product, it narrows down their search for factors. i.e. factoring a 200 digit number that was generated by msomeone purposely from two 100 digit numbers, is not as difficult as factoring an arbitrary 200 digit number. this is a current topic of research.

What Robert is saying is that if they also know the number is a Mersenne number, then the job of factoring it is even more restricted.

In fact 10 or 20 years ago, even factoring special 100 digit numebrs was pretty tough. But one of my friends programmed a chain of PC's to do it in a few months, working entirely at night when the PC's were not in use.

You also need to realize that the difficulty of proving a big number is prime is much much less than that of factoring a non prime number.

I.e. there are tests for primality that run hugely faster than factoring algorithms, due to special proeprties of primes numbers like the "Fermat little theorem". This particular property does not quite characterize primes, since some non prime numbers also obey the conclusion of fermats little theorem, but a small enhancement of it does so.

now there are much faster algortihms using elliptic curves, etc... that detect prime numbers.

so the job of proving a certain mersenne number is prime is nothing like the task of factoring one that is not prime.

 

[robert Ihnot]

Most people have difficulity understanding the vastness of numbers like a google. A 200 digit number is a google squared, not two google.

Suppose, we can check one number every second for primality of a 100 digit number, and say we check every 10th number, or better yet, every 100th number to use a figure, we would, using 365 days/yr, be working for 3.17 x 10^89 YEARS to check every such number for primality!

That's 10^99/(60x60x24x365x100) = 3.17x10^89!

 

[Hurkyl]

There are less naive tests for primality, though. The best run in time that is polynomial in the number of digits, not in the number's size.

 

[mathwonk]

here is a site where one can download a pdf article on primality testing, by andrew granville.

http://www.math.gatech.edu/~mbaker/Math4150.html

 

[CrankFan]

There are less naive tests for primality, though. The best run in time that is polynomial in the number of digits, not in the number's size.

I think it's been accepted for a few years now that primality testing is in P.

http://www.cse.iitk.ac.in/news/primality.html

There are two pdfs available from the website above which discuss the method. Note that theorem 5.1 in either the original or revised paper suggest an upper bound of $$\log^{12} n$$

Unfortunately I can't understand the number theory


EDIT: You know, on second thought, it seems like you may already be aware of that link/result; in which case, just ignore it. But I don't follow you when you say that the best algorithms run in time polynomial in the number of digits, but not in the number's size. That's what kind of threw me.

I'll leave the "primes in P" link stuff up just in case anyone else is interested.

 

[shmoe]

EDIT: You know, on second thought, it seems like you may already be aware of that link/result; in which case, just ignore it. But I don't follow you when you say that the best algorithms run in time polynomial in the number of digits, but not in the number's size. That's what kind of threw me.

I'll leave the "primes in P" link stuff up just in case anyone else is interested.

This is exactly the type of result Hurkyl is referring to. Think of the naive method of testing primality of an integer n, you can do trial division by every interger less than $\sqrt{n}$, so this takes $\sqrt{n}$ steps. If d is the number of digits of n, this is about $10^{d/2}$ steps. So this algorithm would be considered polynomial time in the size (or absolute value) of n, but exponential in the number of digits. (note log(n) is proportional to d). The original AKS algorithm runs in time $d^{12}$, polynomial time in the number of digits of n. (the exponent 12 is down to 6 I believe, due to refinements by Lenstra and Pomerance, see the article by A.Granville for a nice survey)

 

[CrankFan]

This is exactly the type of result Hurkyl is referring to. Think of the naive method of testing primality of an integer n, you can do trial division by every interger less than $\sqrt{n}$, so this takes $\sqrt{n}$ steps. If d is the number of digits of n, this is about $10^{d/2}$ steps. So this algorithm would be considered polynomial time in the size (or absolute value) of n, but exponential in the number of digits.

Right, but in that case we don't have an algorithm that is polynomial in log n and not polynomial in n.

But I now see what he meant. If I put a "just" between "not" and "in", it all makes sense: "The best run in time that is polynomial in the number of digits, not [just] in the number's size."

 

[abertram28]

Right now binary factorization is making some huge progress, so id stop short of saying there were ANY practical limits to factorizations. especially with how commonly computers make huge advances in processing power and memory size.

right now, there are no algorithmic methods of calculating primes, or obviously, we could just generate the largest ones quickly. the fact that these numbers obey no known pattern besides a general one of becoming less frequent when distributed against the integer set from 0 on. that comparison is pointless, since the composite numbers don't belong with the primes in a set used for finding JUST PRIMES through algorithm.

wasnt there a proof that mersenne primes had to have a prime as an exponent? i can't remember where i saw that, but I am pretty sure its true. this means that only primes are used in generating mersenne primes, but they still produce composite numbers. so, we get closer, but...

its interesting that when fermat found his first numbers F0-F4 he assumed, incorrectly, that all Fn would be primes, since the first 4 were prime.

its also interesting that in the 1900s factorization algorithms had to still be done by hand, and one guy who factored M67, previously thought to be factorable by the famous Edouard Lucas, whos algorithms for finding factorability, not the actual factors, are still used in Prime95 today. The guy, named Frank Cole, did the factoring by hand, over the course of 20 years of sunday afternoons. the factors of M67 are 193,707,721 x 761,838,257,287. that's huge.

T Rex> Mx isn't the xth mersenne prime, x is the exponent. Mx means (2^x)-1

 

[shmoe]

right now, there are no algorithmic methods of calculating primes, or obviously, we could just generate the largest ones quickly.

What do you mean by "calculate primes" here? There are plenty of agorithms that produce primes, maybe not as fast as we'd like but they are there.

wasnt there a proof that mersenne primes had to have a prime as an exponent? i can't remember where i saw that, but I am pretty sure its true.

Yes, if the exponent is composite, say nm, just factor $$2^{nm}-1=(2^m)^n-1=(2^m-1)(2^{m(n-1)}+2^{m(n-2)}+\ldots+2^m+1)$$

 

[abertram28]

there are algorithms that plug in single integers and ALWAYS produce primes? could you provide an example? I am having trouble seeing that one being possible. i mean, i believe that one might be possible using a table of primes as input, but that isn't really an algorthim, unless the algorithm also produced those primes by the same process, starting with just 2 and 3. if so, id be very interested to play with it! does 1 count as a prime when starting these sequences? is 1 prime? I am dumb.

ah, yes, I've actually used that factorization on the forms of the "odd perfect numbers", should they ever exist. thanks for that one.

 

[Hurkyl]

Of course. For example, there is the algorithm that always returns "2". Another example is one that, given a positive integer n, it iterates through the integers bigger than n, testing each for primality, and returns the first that passes the test.

 

[shmoe]

there are algorithms that plug in single integers and ALWAYS produce primes?

There are many, see http://mathworld.wolfram.com/PrimeFormulas.html for a few different ones. Some give only a subset of the primes, some give all primes. None are really convenient to work with though.

1 is generally not considered a prime these days.

 

[abertram28]

ah, i see. none of these are basic algebraic algorithms. none of them are algebraic and use even a restricted input set! the iterative ones arent really even producing the prime, they are producing forms and testing for primality, its really a multifunction program rather than a single algorithm. but it still is an algorithm all on its own too. these really digress to the simple algorithm, if p=1, then n is prime; p=1 if n-PHI(n)=1. this is meaningless though, since its just a simple definition with a number theoretic function.

on 200 digit numbers, my calculator, TI-89 ti, displays F9 in raw data. its 155 digits or something. it also factors F6 pretty quickly. i mean, quickly for a handheld battery powered machine!

thanks for the prime formulas, ill be sure to print some of them and take them on my spring break road trip. it sucks that none of these are really useful. that's what i expected. none of these algorithms are really generators of primes, rather just indicators. i mean, as far as useful ones go. the simple number "2" being an algorithm is useless, though it might fit some arbitrary definition of algorithm.