Pre Computation

The pre-computation of Totient function and Mobius function is one of the prerequisites of all the algorithms that we have seen so far. In fact, this pre-computation would form an excellent exercise in understand the standard Sieve of Erasthones.  In our sieving, we'll not only find the primes, but also the two aforementioned functions.

Let's first see the algorithm for Erasthones' sieve. It's not difficult understand or code. From there we'll build our Totient and Mobius functions.

Algorithm 1

function PRIMES(n)

            flag  $\gets$ [0] * (n)

            Primes $\gets$ [0] * (n)

            pos $\gets$ 1

            for i = 2 to n do

if flag[i] = 0 then

                                    for j = i to n do

                                                flag[j] $\gets$ 1
                                                j $\gets$ j + i
                                    end for

                                    Primes[pos] $\gets$ i

                                    pos $\gets$ pos +1

                           end if

            end for

            return Primes

end function

As you can see here, we start our algorithm by initializing a flag of 0's. Starting from 2, whenever we first encounter a 0, we label it as a prime. We then mark it's multiples as composites by changing their flags to 1. We then move on to find the next 0 and repeat the process.

Well, in order to bring in the totient function, we first note that the totient function of a particular number $n$ is set to its own value and changes only by its prime factorization. We encounter all the multiples of a prime in the inner for loop and use this loop to change the totient value as appropriate.

The logic applies to Mobius function as well. We initially set the value to be 1 and multiply it by -1 whenever we reach a number by a different prime. In addition, for Mobius we also have to check if its divisible by a square, and if it is, we change it to 0.

Algorithm 2

function PRECOMPUTATION(n)

            flag  $\gets$ [0] * (n)                                                                                            

            EulerPhi  $\gets$ [0, 1, 2, …, n]

            Mu  $\gets$ [1] * (n)

            Primes  $\gets$ [0] * (n)

            pos  $\gets$ 1

            for i = 2 to n do

if flag[i] = 0 then

                                    for j = i to n do

                                                flag[j]  $\gets$ 1

                                                EulerPhi[j]  $\gets$ ( EulerPhi[j] / i ) * ( i– 1 )

                                                if  j/i%i = 0 then

                                                            Mu[j]  $\gets$ 0

                                                else

                                                            Mu[j]  $\gets$ Mu[j] * (-1)

                                                end if

                                                j $\gets$ j + i

                                    end for

                                    Primes[pos]  $\gets$ i

                                    pos  $\gets$ pos +1

                           end if

          end for

          return Primes

          return EulerPhi

          return Mu

end function

This should be the end of this discussion. But I noted that it is as easy to initiate an array full of 1's (or any other value for that matter) as it is to initiate with 0. For example, when I tried to program the above algorithm in C, I first had to run the loop for the entire value of $n$, just to initialize the EulerPhi and Mobius function values. I therefore made a small optimization to the above algorithm which you can see here.

UPDATE (17/Nov/2019): Yet another interesting, and possibly faster, sieve is described in the Codeforces blog: Math note - linear sieve.

Yours Aye
Me