COME ON CODE ON

A blog about programming and more programming.

Programming Multiplicative Functions

with 9 comments

In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then f(ab) = f(a)f(b).

This type of functions can be programmed in quick time using the multiplicative formmula. Examples of multiplicative functions include Euler’s totient function, Möbius function and divisor function.

A multiplicative function is completely determined by its values at the powers of prime numbers, a consequence of the fundamental theorem of arithmetic. Thus, if n is a product of powers of distinct primes, say n = pa qb …, then f(n) = f(pa) f(qb) …

Lets take an example. If we need to calculate the divisor of 12 then div(12) = div(2231) or div(22)div(31). If we are calculating it for a range then it becomes even more easier. We only need to calculte the div(22)part because the div(31) part will already be present in the array. So lets look at an sample code for calculating the divisor of all numbers from 1 to 10000000.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int A[10000000]={0};
int main()
{ 

    int isprime[3163],d,n,e,p,k,i;

    for (n=2;n<3163;n++)
        isprime[n]=1;

    //Sieve for Eratosthenes for Prime
    //Storing the smallest prime which divides n.
    //If A[n]=0 it means it is prime number.
    for(d=2;d<3163;d++)
    {
        if(isprime[d])
        {
            for (n=d*d;n<3163;n+=d)
            {
                isprime[n]=0;
                A[n]=d;
            }
            for (;n<=10000000;n+=d)
                A[n]=d;
        }
    }

    //Applying the formula
    //Divisor(N)=Divisors(N/p^f(N,p))*(f(N,p)+1)
    A[1]=1;
    for(n=2;n<=10000000;n++)
    {
        if (A[n]==0)
           A[n]=2;
        else
        {
           p=A[n],k=n/p,e=2;
           while (k%p==0)
                 k/=p,e++;
           A[n]=A[k]*e;
        }
    }
    printf("time=%.3lf sec.\n",
    (double) (clock())/CLOCKS_PER_SEC);
    while (scanf("%d",&i),i)
    {
          printf("%d\n",A[i]);
    }
    return 0;
}

If you run the above program you will be able to see how fast have we made this program. Similar techniques can be used to calculate the divisor function or the sum of squares of divisors which is also called sigma2. The general formula for calculating sigma function is :

sigma_x

sigma_x

or sigma_x

-fR0DDY

Advertisements

Written by fR0DDY

April 13, 2009 at 6:31 AM

9 Responses

Subscribe to comments with RSS.

  1. Nice article. I had read about multiplicative functions before, but did not really understand the idea until I read this.

    [small correction:
    “calculte the div(2^3) part” should be
    “calculate the div(2^2) part” ]

    Steve

    October 31, 2009 at 8:26 AM

    • Thanks Steve for the correction.

      fR0D

      October 31, 2009 at 8:43 AM

  2. Another correction:
    While sieving A[n] does not always store the ‘smallest’ prime number which divides n..
    for eg: A[18] stores 3 while it should store 2.

    Chandan Mittal

    November 16, 2013 at 1:03 AM

  3. Given your method of storing the last found factor, what changes sis you have in mind to compute sigma1?

    Ken

    March 4, 2014 at 3:23 AM

    • Sigma1 is also a multiplicative function.

      fR0DDY

      March 4, 2014 at 8:31 AM

      • Of course. I was meaning that lines 41 to 43 will need to be changed. In my experimentation with changes, it seems that the k value is one step too low for the formula for sigma 1 when line 43 is reached. Did you have a way in mind to get sigma1 when you made the original program? BTW I like the method you show here.

        Ken

        March 4, 2014 at 6:06 PM

      • Yes, it will be one step less, you can easily modify it to get correct result for sigma1.

        fR0DDY

        March 4, 2014 at 7:17 PM

  4. So true. Perhaps you would post a modified version of this that would take a value x at start and then calculate the array based on sigmax(n). Would be interesting to look at time comparisons given your approach to building the array. Thanks,

    Ken

    March 5, 2014 at 3:06 AM

  5. What is the algorithm behind LCM SUM spoj problem?

    Hint: Read about multiplicative functions. https://comeoncodeon.wordpress.com/2009/04/13/programming-multiplicative-functions/

    Quora

    September 26, 2015 at 4:47 PM


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: