C-Code for Merten's Function

The C-Code for Merten's function proceeds much in the same way as that of Totient Summatory function and uses the formula derived in Merten's function. This code evaluates the value of $M(10^{11})$ in approx. $8$ seconds and $M(10^{12})$ in approx. $80$ seconds. Here is the code.

#include<stdio.h>
#include<math.h>

#define M 60000000
#define Mod 1000000007

int MertCache[M+1], Mert[M+1];
char Mu[M+1], flag[M+1];

void precalc()
{
    int i, j;
    Mu[1] = 1;
    Mert[1] = 1;
    MertCache[1] = 56789;
    for(i = 2; i <= M; i++) {
        if(!flag[i])
            for(j = i; j <= M; j += i) {
                if( !flag[j] )
                    Mu[j] = 1;
                if(j/i%i == 0)
                    Mu[j] = 0;
                else
                    Mu[j] = -Mu[j];
                flag[j] = 1;
        }
        Mert[i] = Mert[i-1] + Mu[i];
        MertCache[i] = 56789;
    }
}

long long Merten(long long n, long long k)
{
    long long m = n/k;
    if(m <= M)
        return Mert[m];
    else if(MertCache[k] != 56789)
        return MertCache[k];
    long long p = sqrt(m), q = m/(p+1), i, res = 0;
    for(i = 2; i <= p; i++)
        res += Merten(n, k*i);
    for(i = 1; i <= q; i++)
        res = res + (m/i) * Mu[i];
    res = 1 - res;
    res += p * Merten(n, k*(p+1));
    return MertCache[k] = res;
}

int main()
{
    precalc();
    printf("%lld", Merten(100000000000LL,1));
    return 0;
}

Note: $\text{Merten}(n,k) = M\left(\left\lfloor\dfrac{n}{k}\right\rfloor\right)$ in the code.

This code doesn't include the Phi function at all. But if you plan to use both the Totient summatory function and the Merten's function in the same code, I think code may slow down. I'vnt tried it yet but I'll also post the code that uses both the functions.

UPDATE (13 May 2017): As in Totient Summatory function, I made an iterative version of the Merten's function. You can check the performance of the code in this Online IDE.

from timeit import default_timer

start = default_timer()

n = 10 ** 6
s = int(n ** 0.5)


def sieve():
    Lows, Flag = [0] + [1] * s, [0] * (1 + s)
    Lows[1] = 1
    for i in range(2, 1 + s):
        if Flag[i] == 0:
            for j in range(i, 1 + s, i):
                Flag[j] = 1
                if (j // i % i) == 0:
                    Lows[j] = 0
                else:
                    Lows[j] *= -1
        Lows[i] += Lows[i - 1]
    return Lows


Lows = sieve()
Highs = [0] * (1 + s)

for k in range(s, 0, -1):
    tempn = n // k
    u = int(tempn ** 0.5)
    v = tempn // (1 + u)
    res = 1
    for i in range(1, 1 + v):
        res -= (Lows[i] - Lows[i - 1]) * (tempn // i)
    for i in range(2, 1 + u):
        res -= Highs[k * i] if k * i <= s else Lows[tempn // i]
    i = 1 + u
    res += Lows[tempn // i] * u
    Highs[k] = res

print(Highs[1])
print(default_timer() - start)

Note: $\text{Highs}[k] = M\left(\left\lfloor\dfrac{n}{k}\right\rfloor\right)$ in the code. Also, the value $-962982$ is purely arbitrary just to make sure that value has not been touched yet.


Until then
Yours Aye
Me

C Code for Totient Summatory function

I thought of creating a post on Dirichlet Generating functions which would be right continuation of the direction my blog is heading. But this post is about the C code for Totient Summatory function.

The code uses the algorithm described in Totient Summatory function. If you haven't visited that post, I suggest you to do so. The code computes the answer for $10^{11}$ in approx. $7$ seconds and for $10^{12}$ in approx. $25$ seconds. Not bad compared to Mathematica. Here's the code for you.

#include<stdio.h>
#include<math.h>

#define M 60000000
#define Mod 1000000007

int Phi[M+1], SumPhi[M+1], TotCache[M+1];

void precalc()
{
    int i, j;
    Phi[1] = 1;
    SumPhi[1] = 1;
    for(i = 2; i <= M; i++) {
        if(!Phi[i])
            for(j = i; j <= M; j += i) {
                if(!Phi[j])
                    Phi[j] = j;
                Phi[j] = (Phi[j] / i) * (i - 1); }
        SumPhi[i] = (SumPhi[i-1] + Phi[i]) % Mod; }
}

long long SumNat(long long n)
{
    long long p = n, q = n+1;
    if(p%2)
        q /= 2;
    else
        p /= 2;
    return (p % Mod) * (q % Mod) % Mod;
}

long long TotientSum(long long n, long long k)
{
    long long m = n / k;
    if(m <= M)
        return SumPhi[m];
    else if(TotCache[k] > 0)
        return TotCache[k];
    long long p = sqrt(m), q = m / (p+1), i, res = 0;
    for(i = 2; i <= p; i++) {
        res += TotientSum(n, k * i);
        if(res >= Mod)
            res %= Mod;
    }
    for(i = 1; i <= q; i++) {
        res = res + ((m / i) % Mod * Phi[i]) % Mod;
        if(res >= Mod)
            res %= Mod;
    }
    res = SumNat(m) - res;
    res += (p % Mod) * TotientSum(n, k * (p + 1));
    res %= Mod;
    TotCache[k] = res;
    return res;
}

int main()
{
    precalc();
    printf("%lld",TotientSum(1000000000000LL,1));
    return 0;
}

Note: $\text{TotientSum}(n,k)=\Phi\left(\left\lfloor\dfrac{n}{k}\right\rfloor\right)$ in the code.

Just posting a code wouldn't do much good either for the blogger or the reader I think from the experience I've had myself. But am not gonna no through the complete code. Just a few details which we should be paying attention to.

First, the 'precalc' function. It's just a word-by-word translation of the algorithm that we saw on Optimized Precomputation.

Second is the 'SumNat' function. The important thing about this function is that we ought to keep the values from overflowing. For example, I first did $\text{(p%Mod * q%Mod)%Mod}$ which was perfectly okay looking except that it overflows.

Third, the 'TotientSum' function, is pure memoization. It'll take a separate post to completely explain it. Maybe I'll do that later. But for now I think this should suffice. I'll try to come up with the C-code for Merten's function in the next post.

Last is the limit you choose to sieve. That's the real trade-off you have to make between space and time. If you choose to sieve more, it's gonna take more space but the final result will be quick, whereas if you choose to memoize more you consume less space at cost of being time expensive. I made some trial and error to arrive at the above sieve limit which kinda minimized the computation time.

UPDATE(13 Mar 2017): I made an iterative version of the Totient summartory function in Python. You can check it out in this Online IDE.

from timeit import default_timer

start = default_timer()

n = 1000000000
s = int(n ** 0.5)
LowPhis = [k for k in range(1 + s)]
HiPhis = [0] * (1 + s)

for p in range(2, 1 + s):
    if p == LowPhis[p]:
        for k in range(p, 1 + s, p):
            LowPhis[k] = LowPhis[k] - LowPhis[k] // p
    LowPhis[p] += LowPhis[p - 1]

for k in range(s, 0, -1):
    tempn = n // k
    res = tempn * (1 + tempn) // 2
    u = int(tempn ** 0.5)
    v = tempn // (1 + u)
    for i in range(1, 1 + v):
        res -= (tempn // i) * (LowPhis[i] - LowPhis[i - 1])
    for i in range(2, 1 + u):
        res -= (HiPhis[i * k] if i * k <= s else LowPhis[tempn // i])
    i = 1 + u
    res += u * LowPhis[tempn // i]
    HiPhis[k] = res

print(HiPhis[1])
print(default_timer() - start)

Note: $\text{HiPhis}[k]=\Phi\left(\left\lfloor\dfrac{n}{k}\right\rfloor\right)$ in the code.

I like iterative versions in that they don't suffer from the annoying maximum-recursion-depth error. I think this is a little slower than the recursive version but looks well nonetheless in Python.


Until then
Yours Aye
Me

An Optimized Pre Computation

This post is an extension to make an optimization in precomputing the values of Totient and Mobius function. So make sure you first go through the previous post.

The extra initialization required for Algorithm 2 made me think for a while to eliminate the 'initializing' for loop. So I made (or atleast tried to make) a little optimization there. I realized that we don't need that loop. Instead, I initialized the values in the for loop only when the EulerPhi was zero. In other words, when we first reach a number, we do the initialization which should be sufficient enough. The following algorithm do that.

Algorithm 3

function PRECOMPUTATION(n)

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

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

            Mu $\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] = 1

                                                if EulerPhi[j] = 0 then

                                                            EulerPhi[j] $\gets$ j

                                                            Mu[j] $\gets$ 1

                                                endif

                                                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 pretty much completes our discussion of Precomputations. These algorithms can be effectively converted into codes in a programming language of your choice.

Yours Aye

Me

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

Liouville Summatory function

The Liouville Summatory function starts with the following well known identity

$\lambda*1=\epsilon_2$

where $\lambda$ is the Liouville's function and $\epsilon_2$ is the characteristic function of squares.

Like in the case of Merten's function, this property simplifies $\hat{F}(n)$ to a simple value.

Let $f(n)=\lambda(n)$. Then,

$F(n)=\displaystyle\sum\limits_{i=1}^n\lambda(i)=L(n)$ and $\hat{F}(n)=\displaystyle\sum\limits_{i=1}^n\sum_{d|i}\lambda(d)=\lfloor\sqrt n\rfloor$

Using these values in A special case of Dirichlet's Hyperbola method, we have

$\lfloor\sqrt n\rfloor=\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \lambda(i) + \sum_{d=1}^u L\left(\left\lfloor\frac{n}{d}\right\rfloor\right) -u^{\text{ }}L\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$, $u=\lfloor \sqrt{n}\rfloor$

Solving for the first term of the right summation,

$L(n)=\lfloor\sqrt n\rfloor-\displaystyle\sum\limits_{i=1}^{n/(u+1)} \left\lfloor\frac{n}{i}\right\rfloor \lambda(i) - \sum_{d=2}^u L\left(\left\lfloor\frac{n}{d}\right\rfloor\right) +u^{\text{ }}L\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$, $u=\lfloor \sqrt{n}\rfloor$

We can use the intermediate result we obtained in Dirichlet's hyperbola method to write

$\lfloor\sqrt n\rfloor=\displaystyle\sum\limits_{k=1}^nL\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$

$L(n)=\lfloor\sqrt n\rfloor-\displaystyle\sum\limits_{k=2}^nL\left(\left\lfloor\frac{n}{k}\right\rfloor\right)$


Yours Aye
Me

Moment of a function

Define the $m$th moment of a function $f(n)$ as

$F_{(m)}(n)=\displaystyle\sum\limits_{k=1}^n k^mf(k)$

Now the same procedure also relates the moments of the three functions, since

$f(n)*g(n)=h(n)\implies n^mf(n)*n^mg(n)=n^mh(n)$

For example, since we know that $\varphi(n)*1=n$, we can use this to calculate the Summatory Totient moments.

Choosing $f(n)=\varphi(n)$ and $g(n)=1$, we have $n^k\varphi(n)*n^k=n^{k+1}$. The corresponding summation functions are

$F_k(n)=\displaystyle\sum\limits_{m=1}^n m^k\varphi(m)$, $G(n)=S_k(n)$ and $H(n)=S_{k+1}(n)$. The corresponding results are

$F_k(n)=S_{k+1}(n)-\displaystyle\sum\limits_{m=2}^n m^k F_k\left(\left\lfloor\frac{n}{m}\right\rfloor\right)$

$F_k(n)=S_{k+1}(n)-\displaystyle\sum\limits_{m=1}^{n/(u+1)}m^k\varphi(m)S_k\left(\left\lfloor\frac{n}{m}\right\rfloor\right)-\sum_{m=2}^u m^kF_k\left(\left\lfloor\frac{n}{m}\right\rfloor\right)+S_k(u)F_k\left(\left\lfloor\frac{n}{u+1}\right\rfloor\right)$


Yours Aye
Me