Charles Greathouse on Fri, 20 Feb 2015 18:43:21 +0100

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

Re: moebius function

N.B. sum(x=1,n, moebius(x)) is a simpler form for the same computation.

Yes. I tried to do it more cleverly once:

my(v=vectorsmall(n, i, 1));
forprime(p=2, sqrtint(n),
forstep(i=p, n, p, v[i]*=-1);
forstep(i=p^2, n, p^2, v[i]=0)
forprime(p=sqrtint(n)+1, n,
forstep(i=p, n, p, v[i]*=-1)
Mertens(n, M=0)={
if(n<4, return(2-n));
for(i=2, #M, M[i]+=M[i-1])
my(cross1=n\(#M-1), cross2=n\(sqrtint(n)+1));
1-sum(d=2, min(cross1, cross2),
Mertens(n\d, M)
)-sum(d=cross1+1, cross2,
)-sum(k=1, sqrtint(n),

but it ended up being slower than the naive sum(k=1,n,moebius(k)). Sad.

Charles Greathouse
Case Western Reserve University

On Fri, Feb 20, 2015 at 3:55 AM, Karim Belabas <> wrote:
* Chris De Corte [2015-02-20 04:21]:
> I am doing tests on the moebius.It went well for a few days until
> tonight when It gave an error.A printscreen is attached.What is the
> problem?

Something went wrong during a factorization (while trying to rename a file
in the MPQS factorizer).

This is a recurrent problem on Windows, that we tried to fix a few
times; pari-2.5.5 is old now (codebase from 2011 or so), try to update
to 2.7.3 !

> Is the m on the screen reliable?

No, the computation was stopped before completion.

You should have typed 'x' while still in the debugger (break loop),
*before typing 'break' to see up to which value the sum had run.

N.B. sum(x=1,n, moebius(x)) is a simpler form for the same computation.


Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation
Talence (France)  [PARI/GP]