MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: PrimePi and limit of argument

  • To: mathgroup at smc.vnet.net
  • Subject: [mg78133] Re: [mg78087] Re: [mg77911] PrimePi and limit of argument
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Sat, 23 Jun 2007 07:18:27 -0400 (EDT)
  • References: <7566193.1182423757619.JavaMail.root@m35> <200706221049.GAA16611@smc.vnet.net> <25396560.1182560007011.JavaMail.root@m35> <op.tucso6nsqu6oor@monster.ma.dl.cox.net>

Yes, indeed, but there is a subtle difference between what is  
mathematically impossible, what is mathematically possible but not  
possible in a particular implementation and what is mathematically  
possible but impossible in any implementation.
  In this particular case the problem is only with the  
implementation. Values of PrimePi for much larger arguments can be  
computed by other programs and perhaps even by Mathematica, although  
the built-in function PrimePi will notdo it for you automatically.

On the other hand, there are cases, like the famous theorem of Meyer  
and Stockmeyer, which states that a certain mathematically well  
defined algorithm can never be implmented on any computer,  because  
any implementation woud require more parts than there are atoms in  
the universe. That is a real (-istic)  limitation.

Of course, how much this has to do with 64 bit vs. 32 bit computing  
is a somewhat different issue.

Andrzej Kozlowski


On 23 Jun 2007, at 11:47, DrMajorBob wrote:

> My point was that increasing the address space -- like getting a  
> bigger piece of paper -- doesn't solve every big problem, as if by  
> magic.
>
> "Look! I can calculate 500 factorial! So I can solve equations in  
> that many unknowns, too, right? I can find the 500 factorial-th  
> prime, right?"
>
> Well... no. Sorry.
>
> Mathematica will, for the most part, solve the same problems on a  
> 64-bit machine as it does on a 32-bit machine. It won't run out of  
> memory as often, perhaps, but the algorithms don't suddenly change.
>
> Bobby
>
> On Fri, 22 Jun 2007 19:40:56 -0500, Andrzej Kozlowski  
> <akoz at mimuw.edu.pl> wrote:
>
>> *This message was transferred with a trial version of CommuniGate 
>> (tm) Pro*
>> That's not quite right: in the case of solving polynomial  
>> equations in terms of radicals there is a mathematical limitation,  
>> in the other case there is a limitation of the particualr  
>> implementation. The value of PrimePi[10^15]  is well known, in  
>> fact it is:
>>
>> 29844570422669
>>
>> In Mathemaitca you can get a pretty good approximation by evaluating:
>>
>>
>> Round[LogIntegral[10^15]]
>> 29844571475288
>>
>>
>> Andrzej Kozlowski
>>
>>
>> On 22 Jun 2007, at 19:49, DrMajorBob wrote:
>>
>>> If you decide to compute PrimePi[100] by hand, you might take a  
>>> piece of
>>> paper and write down the primes up to 97, then count them. If you  
>>> try the
>>> same method for PrimePi[10^15], you'll need a bigger piece of paper.
>>>
>>> But you'll need a lot MORE than a bigger piece of paper -- you'll  
>>> need a
>>> smarter algorithm, or you'll never live long enough. And that's what
>>> Mathematica is telling you; the PrimePi method has an upper ceiling,
>>> independent of how big your machine might be.
>>>
>>> You may as well demand a general solution in radicals for 7th-degree
>>> polynomials.
>>>
>>> 7 isn't a large number, but even so, it can't be done... even if  
>>> your
>>> machine is bigger than the universe.
>>>
>>> Bobby
>>>
>>> On Tue, 19 Jun 2007 05:47:55 -0500, Robert Pigeon
>>> <robert.pigeon at videotron.ca> wrote:
>>>
>>>> Hello all,
>>>>
>>>>   I was playing around with the function PrimePi[] and trying  
>>>> different
>>>> arguments. When I tried PrimePi[10^15] I got the error message  
>>>> saying
>>>> that
>>>> the argument is too large for this implementation. I know that  
>>>> it is a
>>>> large
>>>> number.! When I use 10^14 as the argument I get an answer, it  
>>>> takes a
>>>> while
>>>> but I get an answer.
>>>>
>>>>  I tried this on a PC running Vista Home Premium 64-bit with  
>>>> Mathematica
>>>> 6.
>>>> Then I tried the same thing under Windows XP 32-bit. There was no
>>>> difference, I got an answer for 10^14 and same error message  
>>>> with 10^15.
>>>>
>>>>
>>>> My question is: I thought that with a 64-bit computer I could  
>>>> use larger
>>>> numbers.! Maybe I am misunderstanding something here, so please  
>>>> help me
>>>> understand J
>>>>
>>>>
>>>> Thanks,
>>>>
>>>>
>>>> Robert
>>>>
>>>>
>>>> Robert Pigeon
>>>>
>>>>
>>>
>>>
>>>
>>> --DrMajorBob at bigfoot.com
>>>
>>
>>
>
>
>
> -- 
> DrMajorBob at bigfoot.com



  • Prev by Date: Re: : 6.0 Get Graphics Coordinates...
  • Next by Date: Re: Re: My problem when solving a system of equations
  • Previous by thread: Re: Re: PrimePi and limit of argument
  • Next by thread: Substitutions