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:

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)
);
v
};
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]
`