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:

muTable(n)={

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));

if(!M,

M=muTable(sqrtint(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,

M[n\d]

)-sum(k=1, sqrtint(n),

(n\k-n\(k+1))*M[k]

)

};

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

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Fri, Feb 20, 2015 at 3:55 AM, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> 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.

Cheers,

K.B.
--
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 http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France) http://pari.math.u-bordeaux.fr/ [PARI/GP]
`