Karim BELABAS on Mon, 9 Dec 2002 15:07:38 +0100 (MET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

 Re: primetables SEGV

On Mon, 9 Dec 2002, John Cremona wrote: [ directly to me, not to pari-dev ]
> While you are working on the prime functions, can I remind you that it
> is often useful to have the inverse function which given p returns i
> such that p=prime(i), as in the following:
[...]
> pith(x) =
> {
>   local(l,r,lx);
>   if (x <= 2, return (x==2));
>   lx = log(x);
>   l = floor(x/lx);
>   r = floor(l * (1 + 3/(2*lx)));
>   while (r-l>1,
>     m = (l+r)>>1;
>     if (prime(m)<=x, l=m, r=m));
>   l;
> }

It is already there [ install(pith, lL) ] (written by Bill). Actually this is
the standard \pi(x) = #{p <= x}.

It was not installed by default since we could not find a proper name at the
time (then we forgot about it I'm afraid...).

'pith' is not realy suitable, and 'pi' would be too confusing.

Hum, what about primepi() ?

Karim.

P.S: Both prime() and pith() could use a builtin table [ e.g of
prime(k*10^4), k < 50, then prime(K * 10^6), K < 50 ] to make larger strides.

P.S2: Anybody interested in implementing analytic algorithms for the basic
prime-counting functions ? (M, pi, psi)

@article {MR96d:11139,
AUTHOR = {Del{\'e}glise, M. and Rivat, J.},
TITLE = {Computing {$\pi(x)$}: the {M}eissel, {L}ehmer, {L}agarias,
{M}iller, {O}dlyzko method},
FJOURNAL = {Mathematics of Computation},
VOLUME = {65},
YEAR = {1996},
NUMBER = {213},
PAGES = {235--245},
}

@article {MR98f:11135,
AUTHOR = {Del{\'e}glise, Marc and Rivat, Jo{\"e}l},
TITLE = {Computing the summation of the {M}\"obius function},
FJOURNAL = {Experimental Mathematics},
VOLUME = {5},
YEAR = {1996},
NUMBER = {4},
PAGES = {291--295},
}

@article {MR99a:11147,
AUTHOR = {Del{\'e}glise, Marc and Rivat, Jo{\"e}l},
TITLE = {Computing {$\psi(x)$}},
FJOURNAL = {Mathematics of Computation},
VOLUME = {67},
YEAR = {1998},
NUMBER = {224},
PAGES = {1691--1696},
}
--
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--