Dirichlet convolution is a mathematical operation that combines two arithmetic functions to create a third function. It is named after the mathematician Peter Gustav Lejeune Dirichlet and is closely related to the concept of convolution in signal processing.
In mathematics, an arithmetic function is a function that takes positive integers as input and returns a number as output. The most well-known example of an arithmetic function is the divisor function, which counts the number of positive divisors a given number has.
The Dirichlet convolution of two arithmetic functions f and g is denoted by (f * g) and is defined as:
(f * g)(n) = ∑f(d) * g(n/d)
where the sum is taken over all positive divisors d of n.
Examples:
One example of a Dirichlet convolution is the convolution of the divisor function with itself, denoted by (φ * φ). This results in the Euler totient function, which is defined as:
φ(n) = ∑φ(d) * φ(n/d)
where φ(n) is the number of positive integers less than n that are relatively prime to n.
Another example of a Dirichlet convolution is the convolution of the divisor function with the function that returns 1 for all input values. This results in the identity function, which is defined as:
id(n) = ∑φ(d) * 1(n/d)
where id(n) is the function that returns n for all input values.
- Dirichlet convolution can be used to calculate various arithmetic functions, including the number of divisors and the sum of a given number’s divisors.
- It can also be used to find the inverse of an arithmetic function, which is a function that undoes the operation of the original function.
Approaches:
There are several approaches to implementing Dirichlet convolution, depending on the specific requirements of the application.
One simple approach is to use a brute-force method, which involves iterating over all positive divisors of the input value and summing the results of the arithmetic functions at each divisor. This approach has a time complexity of O(n), where n is the input value.
A more efficient approach is to use a sieve algorithm, which pre-calculates the values of the arithmetic functions for all integers up to a certain maximum value and stores them in an array. The Dirichlet convolution can then be calculated by simply multiplying and summing the values in the array. This approach has a time complexity of O(max), where max is the maximum value for which the arithmetic functions are pre-calculated.
Implementation of the Dirichlet convolution in Python:
C++14
// C++ code for the above approach // This function counts the number of // positive divisors of a given number #include<bits/stdc++.h> using namespace std; // This function calculates the greatest // common divisor of two numbers int gcd( int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // This function calculates the Euler // totient function of a given number int eulerTotient( int n) { int result = 0; for ( int i = 1; i <= n; i++) { // If i is relatively prime to n, // increment the result if (gcd(i, n) == 1) { result++; } } return result; } // This function counts the number of // positive divisors of a given number int divisorFunction( int n) { int result = 0; for ( int d = 1; d <= n; d++) { // If d is a divisor of n, // increment the result if (n % d == 0) { result++; } } return result; } // This function performs the Dirichlet // convolution of two arithmetic functions int dirichletConvolution( int n) { int result = 0; for ( int d = 1; d <= n; d++) { // If d is a divisor of n, // add f(d) * g(n//d) to the result if (n % d == 0) { result += divisorFunction(d) * eulerTotient(n / d); } } return result; } int main(){ for ( int i = 1; i <= 10; i++) { cout<< "φ(" << i << ") = " << eulerTotient(i)<<endl; } } // This code is contributed by poojaagarwal2. |
Java
// Java code for the above approach // This function counts the number of // positive divisors of a given number import java.io.*; class GFG { // This function counts the number of // positive divisors of a given number public static int divisorFunction( int n) { int result = 0 ; for ( int d = 1 ; d <= n; d++) { // If d is a divisor of n, // increment the result if (n % d == 0 ) { result++; } } return result; } // This function performs the Dirichlet // convolution of two arithmetic functions public static int dirichletConvolution( int n) { int result = 0 ; for ( int d = 1 ; d <= n; d++) { // If d is a divisor of n, // add f(d) * g(n//d) to the result if (n % d == 0 ) { result += divisorFunction(d) * eulerTotient(n / d); } } return result; } // This function calculates the greatest // common divisor of two numbers public static int gcd( int a, int b) { while (b != 0 ) { int temp = b; b = a % b; a = temp; } return a; } // This function calculates the Euler // totient function of a given number public static int eulerTotient( int n) { int result = 0 ; for ( int i = 1 ; i <= n; i++) { // If i is relatively prime to n, // increment the result if (gcd(i, n) == 1 ) { result++; } } return result; } public static void main(String[] args) { for ( int i = 1 ; i <= 10 ; i++) { System.out.println( "φ(" + i + ") = " + eulerTotient(i)); } } } // This code is contributed by lokesh. |
Python3
# This function counts the number of # positive divisors of a given number def divisor_function(n): result = 0 for d in range ( 1 , n + 1 ): # If d is a divisor of n, # increment the result if n % d = = 0 : result + = 1 return result # This function performs the Dirichlet # convolution of two arithmetic functions def dirichlet_convolution(f, g, n): result = 0 for d in range ( 1 , n + 1 ): # If d is a divisor of n, # add f(d) * g(n//d) to the result if n % d = = 0 : result + = f(d) * g(n / / d) return result # This function calculates the greatest # common divisor of two numbers def gcd(a, b): while b ! = 0 : a, b = b, a % b return a # This function calculates the Euler # totient function of a given number def euler_totient(n): result = 0 for i in range ( 1 , n + 1 ): # If i is relatively prime to n, # increment the result if gcd(i, n) = = 1 : result + = 1 return result # Print the values of the Euler totient # function for the integers 1 through 10 for i in range ( 1 , 11 ): print (f "φ({i}) = {euler_totient(i)}" ) |
C#
// C# code for the above approach // This function counts the number of // positive divisors of a given number using System; public class GFG { // This function counts the number of // positive divisors of a given number public static int divisorFunction( int n) { int result = 0; for ( int d = 1; d <= n; d++) { // If d is a divisor of n, // increment the result if (n % d == 0) { result++; } } return result; } // This function performs the Dirichlet // convolution of two arithmetic functions public static int dirichletConvolution( int n) { int result = 0; for ( int d = 1; d <= n; d++) { // If d is a divisor of n, // add f(d) * g(n//d) to the result if (n % d == 0) { result += divisorFunction(d) * eulerTotient(n / d); } } return result; } // This function calculates the greatest // common divisor of two numbers public static int gcd( int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // This function calculates the Euler // totient function of a given number public static int eulerTotient( int n) { int result = 0; for ( int i = 1; i <= n; i++) { // If i is relatively prime to n, // increment the result if (gcd(i, n) == 1) { result++; } } return result; } static public void Main() { // Code for ( int i = 1; i <= 10; i++) { Console.WriteLine( "φ(" + i + ") = " + eulerTotient(i)); } } } /* Note: When you compile this C# program, you may notice that 'φ' symbol not being printed. That's because of the console. */ // This code is contributed by lokeshmvs21. |
Javascript
<script> //JavaScript code for the above approach // This function counts the number of // positive divisors of a given number function divisorFunction(n) { let result = 0; for (let d = 1; d <= n; d++) { // If d is a divisor of n, // increment the result if (n % d === 0) { result++; } } return result; } // This function performs the Dirichlet // convolution of two arithmetic functions function dirichletConvolution(f, g, n) { let result = 0; for (let d = 1; d <= n; d++) { // If d is a divisor of n, // add f(d) * g(n//d) to the result if (n % d === 0) { result += f(d) * g(Math.floor(n / d)); } } return result; } // This function calculates the greatest // common divisor of two numbers function gcd(a, b) { while (b !== 0) { [a, b] = [b, a % b]; } return a; } // This function calculates the Euler // totient function of a given number function eulerTotient(n) { let result = 0; for (let i = 1; i <= n; i++) { // If i is relatively prime to n, // increment the result if (gcd(i, n) === 1) { result++; } } return result; } // Print the values of the Euler totient // function for the integers 1 through 10 for (let i = 1; i <= 10; i++) { document.write(`φ(${i}) = ${eulerTotient(i)} <br>`); } // This code is contributed by Potta Lokesh </script> |
φ(1) = 1 φ(2) = 1 φ(3) = 2 φ(4) = 2 φ(5) = 4 φ(6) = 2 φ(7) = 6 φ(8) = 4 φ(9) = 6 φ(10) = 4
Complexity analysis:
Time Complexity: In terms of complexity analysis, the time complexity of Dirichlet convolution depends on the specific implementation used. As mentioned earlier, the brute-force method has a time complexity of O(n), while the sieve algorithm has a time complexity of O(max).
Auxiliary Space: The space complexity of both approaches is O(n), as the values of the arithmetic functions must be stored for all positive integers up to the input value.
Optimization technique:
An optimization technique that can be used to improve the performance of Dirichlet convolution is memoization, which involves storing the results of the arithmetic functions in a cache so that they can be quickly retrieved when needed. This can greatly reduce the time required to perform the convolution, especially for large input values.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!