## Programming Multiplicative Functions

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 = *p*^{a} *q*^{b} …, then f(n) = f(*p*^{a}) f(*q*^{b}) …

Lets take an example. If we need to calculate the divisor of 12 then div(12) = div(*2*^{2}*3*^{1}) or div(*2*^{2})div(*3*^{1}). If we are calculating it for a range then it becomes even more easier. We only need to calculte the div(*2*^{2})part because the div(*3*^{1}) 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 :

or-fR0DDY

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” ]

SteveOctober 31, 2009 at 8:26 AM

Thanks Steve for the correction.

fR0DOctober 31, 2009 at 8:43 AM

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 MittalNovember 16, 2013 at 1:03 AM

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

KenMarch 4, 2014 at 3:23 AM

Sigma1 is also a multiplicative function.

fR0DDYMarch 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.

KenMarch 4, 2014 at 6:06 PM

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

fR0DDYMarch 4, 2014 at 7:17 PM

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,

KenMarch 5, 2014 at 3:06 AM

What is the algorithm behind LCM SUM spoj problem?Hint: Read about multiplicative functions. https://comeoncodeon.wordpress.com/2009/04/13/programming-multiplicative-functions/

QuoraSeptember 26, 2015 at 4:47 PM