Re: Primes (again)

• To: mathgroup at smc.vnet.net
• Subject: [mg53042] Re: [mg53024] Primes (again)
• From: DrBob <drbob at bigfoot.com>
• Date: Tue, 21 Dec 2004 05:19:20 -0500 (EST)
• References: <200412201134.GAA02633@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```> this is probably a naive question, but how does Mathematica give the result of
> Prime[k]? Since the numbers are not stored anywhere, and there is no
> algorithm to "compute" them, how does Mathematica produce them?

OF COURSE there's an algorithm to compute primes (the Sieve of Eratosthenes, for instance), and how do you KNOW they're not stored anywhere? I have quite a few stored here and there, and probably Mathematica does, too.

In fact, according to implementation notes in Help:

"Prime and PrimePi use sparse caching and sieving. For large n, the Lagarias-Miller-Odlyzko algorithm for PrimePi is used, based on asymptotic estimates of the density of primes, and is inverted to give Prime."

I think "sparse caching" means that some answers are stored in advance.

Possibly it works something like this:

If we ask for Prime[n] and n ISN'T large in the sense of that paragraph, then {n,Prime[n]} may be pre-stored. If not, the code starts with the nearest pre-stored {k,Prime[k]} and searches (using PrimeQ or NextPrime) until it finds Abs[n-k] consecutive primes. (The same method is used to compute PrimePi in that range, I suppose.)

If n is large, an asymptotic estimate of Prime[n] is computed (which may not be prime), a nearby prime p is found (using PrimeQ or NextPrime), and PrimePi is used to find k so that Prime[k] = p. Then, as before, the code has to find Abs[n-k] consecutive primes.

Here's a link to what I suppose is the Lagarias-Miller-Odlyzko algorithm:

Enjoy!

Bobby

On Mon, 20 Dec 2004 06:34:46 -0500 (EST), George Szpiro <george at netvision.net.il> wrote:

> this is probably a naive question, but how does Mathematica give the result of
> Prime[k]? Since the numbers are not stored anywhere, and there is no
> algorithm to "compute" them, how does Mathematica produce them?
>
> Thanks to everybody, especially to Dr Bob and Yehuda Ben-Shimol, for
>
> Best regards,
> George
>

--
DrBob at bigfoot.com
www.eclecticdreams.net

```

• References:
• Prev by Date: Re: All Factors of a number
• Next by Date: Re: GUIKit - ScrollPane Tables within Wizard
• Previous by thread: Primes (again)
• Next by thread: Re: Primes (again)