How to get decimal form of largest known prime?

Tim Peters tim.one at comcast.net
Fri Jun 11 01:56:16 CEST 2004


[Claudio Grondi]
> According to latest news the largest known prime is:
>                   2**24036583 - 1
> (right?)
>
> Do someone of you know how long would it take on a 2.8 GHz Pentium 4
> machine to write a  _decimal_  form (hexadecimal form can be written in
> less than one second) of this prime to a file and what should be the
> Python code to use for it?

binary -> hex conversion takes time linear in the number of bits (Python
longs are stored internally in a form of binary representation).  binary ->
decimal conversion takes time quadratic in the number of bits, so is an
enormously slower process for large numbers.  You've got about 7 million
decimal digits here.  That's a lot <wink>.  You could estimate the required
time by measuring how long it takes to print smaller decimal numbers, then
approximately quadruple the time for each doubling of the number of decimal
digits.

If you only want the first or last N decimal digits, there are reasonably
efficient ways to do that for small N.  For example, here are the last 6
digits, in much less than an eyeblink:

>>> print pow(2, 24036583, 1000000) - 1
969407
>>>

In more than an eyeblink, here's a way to print it "from the right", 6
digits at a time:

>>> x = 2**24036583 - 1
>>> while x:
...     x, r = divmod(x, 1000000)
...     print ("000000" + str(r))[-6:],
...
969407 882733 436921 915067 118412 031269 800556 687039 526858 ...

The digits come faster the longer it runs, but you're still going to wait a
long time for more than a million 6-digit blocks to get displayed.






More information about the Python-list mailing list