Re: moebius function

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Charles Greathouse [2015-02-20 18:43]:
> > 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:
[...]
> 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.

The O(n^(1/2)) small values of d in the first inner sum kill you
(=> O~(n) algorithm). You can easily improve on this:

  http://projecteuclid.org/download/pdf_1/euclid.em/1047565447

(=> O~(n^(2/3)) algorithm)

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]
`