# [Maxima] counting primes

Leo Butler l.butler at ed.ac.uk
Sat Apr 3 11:47:16 CDT 2010

```
On Sat, 3 Apr 2010, Stanislav Maslovski wrote:

< Hello,
<
< On Wed, Mar 31, 2010 at 12:38:46PM +0100, Leo Butler wrote:
< > On Wed, 31 Mar 2010, Jean Legeande wrote:
< >
< > < Dear Maxima users,
< > <
< > < What is a good way to code the prime-counting function with Maxima ?
< >
< >
< > pi[n]:=if n = 2 then 1 elseif primep(n) then pi[n-1]+1 else pi[n-1] ;
<
< I tried it out of curiosity and got this:
<
< Maxima 5.20.1 http://maxima.sourceforge.net
< using Lisp GNU Common Lisp (GCL) GCL 2.6.7 (a.k.a. GCL)
< Dedicated to the memory of William Schelter.
< The function bug_report() provides bug reporting information.
<
< (%i1) pi[n]:=if n = 2 then 1 elseif primep(n) then pi[n-1]+1 else pi[n-1]\$
<
< (%i2) pi[100];
< (%o2)                                 25
< (%i3) pi[500];
<
< Maxima encountered a Lisp error:
<
<  Error in PROGN [or a callee]: Bind stack overflow.
<
< Automatically continuing.
< To enable the Lisp debugger set *debugger-hook* to nil.
<
< But if I do it gradually it works:
<
< (%i1) pi[n]:=if n = 2 then 1 elseif primep(n) then pi[n-1]+1 else pi[n-1]\$
<
< (%i2) for n: 100 thru 3000 step 100 do print(pi[n]);
< 25
< 46
< 62
< .
< .
< .
< 407
< 419
< 430
<
< What is the reason?

The Lisp error message tells you the reason: the recursive calls
overflow the stack.

Note that this is dependent on your Lisp. With CMUCL, we can
compute pi[5000] comfortably.

(%i2) pi[n] := if n=2 then 1 elseif symbolp(n) then 'pi[n] elseif
primep(n) then pi[n-1]+1 else pi[n-1];

(%o2) pi[n]:=if n = 2 then 1 elseif symbolp(n) then 'pi[n] elseif
primep(n)
then pi[n-1]+1 else pi[n-1]
(%i3) pi[5000];

(%o3) 669

Leo
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: not available
URL: <http://www.math.utexas.edu/pipermail/maxima/attachments/20100403/d8d82da4/attachment.ksh>
```