Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I wonder if there is any efficient way to calculate Möbius function for a array of number 1:1000000

http://en.wikipedia.org/wiki/M%C3%B6bius_function

share|improve this question

3 Answers 3

up vote 3 down vote accepted

Here are a few papers that might be helpful.

Shallit and Shamir, Number-theoretic functions which are equivalent to number of divisors, Inform. Process. Lett. 20 (1985), no. 3, 151–153, MR0801982 (86k:11076). The review, by Hale Trotter, says $\mu(n)$ can be calculated from a single value $d(n^q)$ where $d$ is the divisor function and $q$ is a prime greater than $1+\log_2n$.

Lioen and van de Lune, Systematic computations on Mertens' conjecture and Dirichlet's divisor problem by vectorized sieving, in From Universal Morphisms to Megabytes: a Baayen Space Odyssey, 421–432, Math. Centrum, Centrum Wisk. Inform., Amsterdam, 1994, MR1490603 (98j:11125). The review, by Jonathan P. Sorenson, says the authors present sieving algorithms for computing $\mu(n)$.

Herman te Riele, Computational sieving applied to some classical number-theoretic problems, in Number Theory in Progress, Vol. 2 (Zakopane-Kościelisko, 1997), 1071–1080, de Gruyter, Berlin, 1999, MR1689561 (2000e:11119). The review, by Marc Deléglise, starts, "This paper is a survey about different applications of sieving in number theory. Finding all the primes belonging to a given interval and computing all the values of the Möbius function on a given interval are obvious examples."

share|improve this answer

You don't need the bigger machinery of a segmented sieve for such a small range. Here is a simple $O(n\log\log n)$ algorithm to calculate all $\mu(i)$ up to $n$ based on the Sieve of Eratosthenes. In fact, the sieve does fully factor all the square-free numbers; it just doesn't do it one at a time.

Depending on your computer, this approach is practical up to around $2^{30}$ at which point you need to start using higher-precision arithmetic and computing a range of $\mu(i)$ values in batches.

public static int[] GetMu(int max)
{
    var sqrt = (int)Math.Floor(Math.Sqrt(max));
    var mu = new int[max + 1];
    for (int i = 1; i <= max; i++)
        mu[i] = 1;
    for (int i = 2; i <= sqrt; i++)
    {
        if (mu[i] == 1)
        {
            for (int j = i; j <= max; j += i)
                mu[j] *= -i;
            for (int j = i * i; j <= max; j += i * i)
                mu[j] = 0;
        }
    }
    for (int i = 2; i <= max; i++)
    {
        if (mu[i] == i)
            mu[i] = 1;
        else if (mu[i] == -i)
            mu[i] = -1;
        else if (mu[i] < 0)
            mu[i] = 1;
        else if (mu[i] > 0)
            mu[i] = -1;
    }
    return mu;
}

Running GetMu(1000000) takes about 10 msec on my computer.

share|improve this answer
    
Doing it the second-most-stupid-way, as described in my answer with Mathematica takes 1sec. I did not try it using Gerhard's extra-stupid way, but it is safe to say that anything works in this range. –  Igor Rivin Jun 14 '12 at 2:04
1  
So, how many different spellings of Eratosthenes can we accumulate in this thread? –  Gerry Myerson Jun 14 '12 at 5:21
    
@Gerry: Thanks. Fixed here ... and in all my other documents. –  Rick Sladkey Jun 14 '12 at 17:42
    
In Rick Sladkey's answer, it seems to me that after running through the sieve, mu[i] should be 0 or +/- i. So why have the extra conditions: else if (mu[i] < 0) mu[i] = 1; else if (mu[i] > 0) mu[i] = -1; ?? –  Steve Robbins Mar 23 at 4:33
    
It's not true that all the prime factors of a number are less than its square root. But, if there is such a factor, there can only be one. –  Rick Sladkey Mar 23 at 14:55

For range 1:1000000 the stupidest possible algorithm (factor each integer, check if it's square free, raise -1 to the right power) will terminate in a blink of an eye. For much larger ranges, an obvious modifican of the sieve of erathsosphenes will be very fast ( just remember to zero every $p$th number at the $p$th step.

share|improve this answer
    
I want to avoid factoring it. I'm also considering Sieve of Eratosthenes –  zimbra314 Jun 13 '12 at 16:53
    
You might consider a wheel method: when you have data for the primes below q, make q^2 copies and modify the concatenation by tweaking every qth entry. Gerhard "Ask Me About System Design" Paseman, 2012.06.13 –  Gerhard Paseman Jun 13 '12 at 17:05
7  
Calling any algorithm the "stupidest possible" underestimates the power of human ingenuity.... –  Greg Martin Jun 13 '12 at 17:34
2  
For calclulating mu(n) when n>1, pick a prime p at random. If n/p is an integer, use (-1) times mu(n/p), taking care to check if p divides n/p. Otherwise go back and try again. There are stupider variations of course. Gerhard "Dare You Double-Dog Dare Me?" Paseman, 2012.06.13 –  Gerhard Paseman Jun 13 '12 at 18:03
1  
Is erathsosphenes what you get when you cross Eratosthenes with Aristophanes? –  Gerry Myerson Jun 13 '12 at 23:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.