La convolution de Dirichlet est un type spécial de convolution qui apparaît comme un outil très utile dans la théorie des nombres. Il opère sur l'ensemble des fonctions arithmétiques .

Défi

Étant donné deux fonctions arithmétiques $f,g$ (c'est-à-dire les fonctions ), calculer la convolution de Dirichlet comme défini ci-dessous. $f,g: \mathbb N \to \mathbb R$ $(f * g): \mathbb N \to \mathbb R$

Détails

On utilise la convention $0 \notin \mathbb N = \{1,2,3,\ldots \}$ .
La convolution de Dirichlet $f*g$ de deux fonctions arithmétiques $f,g$ est à nouveau une fonction arithmétique, et elle est définie comme $(f * g) (n) = \sum_{d | n} f (\frac{n}{d}) \cdot g (d) = \sum_{i \cdot j = n} f (i) \cdot g (j) .$ $(f * g)(n) = \sum_\limits{d|n} f\left(\frac{n}{d}\right)\cdot g(d) = \sum_{i\cdot j = n} f(i)\cdot g(j).$ (Les deux sommes sont équivalentes. L'expression $d|n$ signifie que $d \in \mathbb N$ divise $n$ , donc la somme est sur lesdiviseursnaturelsde $n$ . De même, nous pouvons substituer $i = \frac{n}{d} \in \mathbb N, j =d \in \mathbb N$ et nous obtenons la deuxième formulation équivalente. Si vous n'êtes pas habitué à cette notation, il y a un exemple étape par étape ci-dessous.) Juste pour élaborer (ce n'est pas directement pertinent pour ce défi): La définition vient du calcul du produit de lasérie Dirichlet: $(\sum_{n \in N} \frac{f (n)}{n^{s}}) \cdot (\sum_{n \in N} \frac{g (n)}{n^{s}}) = \sum_{n \in N} \frac{(f * g) (n)}{n^{s}}$ $\left(\sum_{n\in\mathbb N}\frac{f(n)}{n^s}\right)\cdot \left(\sum_{n\in\mathbb N}\frac{g(n)}{n^s}\right) = \sum_{n\in\mathbb N}\frac{(f * g)(n)}{n^s}$
L'entrée est donnée sous forme de deux fonctions de boîte noire . Alternativement, vous pouvez également utiliser une liste infinie, un générateur, un flux ou quelque chose de similaire qui pourrait produire un nombre illimité de valeurs.
Il existe deux méthodes de sortie: Soit une fonction $f*g$ est retournée, soit vous pouvez prendre une entrée supplémentaire $n \in \mathbb N$ et renvoyer $(f*g)(n)$ directement.
Pour simplifier, vous pouvez supposer que chaque élément de $\mathbb N$ peut être représenté avec, par exemple, un entier 32 bits positif.
Pour simplifier, vous pouvez également supposer que chaque entrée $\mathbb R$ peut être représentée par exemple par un seul nombre réel à virgule flottante.

Exemples

Définissons d'abord quelques fonctions. Notez que la liste des nombres sous chaque définition représente les premières valeurs de cette fonction.

l'identité multiplicative ( A000007 ) $ϵ (n) = {\begin{cases} 1 & n = 1 \\ 0 & n > 1 \end{cases}$ $\epsilon(n) = \begin{cases}1 & n=1 \\ 0 & n>1 \end{cases}$ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
la fonction d'unité constante ( A000012 ) $1 (n) = 1 \forall n$ $\mathbb 1(n) = 1 \: \forall n$ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
la fonction d'identité ( A000027 ) $i d (n) = n \forall n$ $id(n) = n \: \forall n$ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
la fonction de Möbius ( A008683 ) $μ (n) = {\begin{cases} (- 1)^{k} & if n is squarefree and k is the number of Primefactors of n \\ 0 & otherwise \end{cases}$ $\mu(n) = \begin{cases} (-1)^k & \text{ if } n \text{ is squarefree and } k \text{ is the number of Primefactors of } n \\ 0 & \text{ otherwise } \end{cases}$ 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, ...
la fonction de totient d'Euler ( A000010 ) $φ (n) = n \prod_{p | n} (1 - \frac{1}{p})$ $\varphi(n) = n\prod_{p|n} \left( 1 - \frac{1}{p}\right)$ 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ...
la fonction de Liouville ( A008836 ) $λ (n) = (- 1)^{k}$ $\lambda (n) = (-1)^k$ où $k$ est le nombre de facteurs premiers de $n$ comptés avec multiplicité 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...
la fonction de somme des diviseurs ( A000203 ) $σ (n) = \sum_{d | n} d$ $\sigma(n) = \sum_{d | n} d$ 1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ...
la fonction de comptage des diviseurs ( A000005 ) $τ (n) = \sum_{d | n} 1$ $\tau(n) = \sum_{d | n} 1$ 1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, ...
la fonction caractéristique des nombres carrés ( A010052 ) $s q (n) = {\begin{cases} 1 & if n is a square number \\ 0 & otherwise \end{cases}$ $sq(n) = \begin{cases} 1 & \text{ if } n \text{ is a square number} \\ 0 & \text{otherwise}\end{cases}$ 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

Ensuite, nous avons les exemples suivants:

$\epsilon = \mathbb 1 * \mu$
$f = \epsilon * f \: \forall f$
$\epsilon = \lambda * \vert \mu \vert$
$\sigma = \varphi * \tau$
$id = \sigma * \mu$ et $\sigma = id * \mathbb 1$
$sq = \lambda * \mathbb 1$ et $\lambda = \mu * sq$
$\tau = \mathbb 1 * \mathbb 1$ et $\mathbb 1 = \tau * \mu$
$id = \varphi * \mathbb 1$ et $\varphi = id * \mu$

Les derniers pour sont une conséquence de l' inversion de Möbius : pour tout $f,g$ l'équation $g = f * 1$ est équivalente à $f = g * \mu$ .

Exemple étape par étape

Il s'agit d'un exemple calculé étape par étape pour ceux qui ne connaissent pas la notation utilisée dans la définition. Considérons les fonctions $f = \mu$ et $g = \sigma$ . Nous allons maintenant évaluer leur convolution $\mu * \sigma$ à $n=12$ . Leurs premiers termes sont répertoriés dans le tableau ci-dessous.

\begin{array}{cccccccccccccc} f & f (1) & f (2) & f (3) & f (4) & f (5) & f (6) & f (7) & f (8) & f (9) & f (10) & f (11) & f (12) \\ μ & 1 & - 1 & - 1 & 0 & - 1 & 1 & - 1 & 0 & 0 & 1 & - 1 & 0 \\ σ & 1 & 3 & 4 & 7 & 6 & 12 & 8 & 15 & 13 & 18 & 12 & 28 \end{array}

$\begin{array}{c|ccccccccccccc} f & f(1) & f(2) & f(3) & f(4) & f(5) & f(6) & f(7) & f(8) & f(9) & f(10) & f(11) & f(12) \\ \hline \mu & 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 \\ \sigma & 1 & 3 & 4 & 7 & 6 & 12 & 8 & 15 & 13 & 18 & 12 & 28 \\ \end{array}$

La somme itère sur tous les nombres naturels $d \in \mathbb N$ qui divisent $n=12$ , donc $d$ suppose tous les diviseurs naturels de $n=12 = 2^2\cdot 3$ . Ce sont $d =1,2,3,4,6,12$ . Dans chaque somme, nous évaluons $g= \sigma$ en $d$ et le multiplions par $f = \mu$ évalué en $\frac{n}{d}$ . Nous pouvons maintenant conclure

\begin{aligned} (μ * σ) (12) & = μ (12) σ (1) & + μ (6) σ (2) & + μ (4) σ (3) & + μ (3) σ (4) & + μ (2) σ (6) & + μ (1) σ (12) \\ = 0 \cdot 1 & + 1 \cdot 3 & + 0 \cdot 4 & + (- 1) \cdot 7 & + (- 1) \cdot 12 & + 1 \cdot 28 \\ = 0 & + 3 & 10 & - 7 & - 12 & + 28 \\ = 12 \\ = i d (12) \end{aligned}

$\begin{array}{rlccccc} (\mu * \sigma)(12) &= \mu(12)\sigma(1) &+\mu(6)\sigma(2) &+\mu(4)\sigma(3) &+\mu(3)\sigma(4) &+\mu(2)\sigma(6) &+\mu(1)\sigma(12) \\ &= 0\cdot 1 &+ 1\cdot 3 &+ 0 \cdot 4 &+ (-1)\cdot 7 &+ (-1) \cdot 12 &+ 1 \cdot 28 \\ &= 0 & + 3 & 1 0 & -7 & - 12 & + 28 \\ &= 12 \\ & = id(12) \end{array}$

code-golf math arithmetic number-theory functional-programming flawr
la source

5

Lean , 108 100 95 78 75 octets

def d(f g:_->int)(n):=(list.iota n).foldr(λd s,ite(n%d=0)(s+f d*g(n/d))s)0

Essayez-le en ligne!

Plus de tests avec toutes les fonctions.

Leaky Nun
la source

est lambda vraiment plus cher que quatre octets fun ?

Mario Carneiro

lambda est de trois octets, je suppose

Leaky Nun

Je pense que c'est deux en UTF8 (le grec est unicode assez bas)

Mario Carneiro

Tu as raison. J'ai également joué à l'importation

Leaky Nun

J'ai également utilisé condpour économiser 5 octets

Leaky Nun

4

Haskell , 46 octets

(f!g)n=sum[f i*g(div n i)|i<-[1..n],mod n i<1]

Essayez-le en ligne!

Merci à flawr pour -6 octets et un grand défi! Et merci à H.PWiz pour un autre -6!

Mego
la source

Plus simple est plus court ici

H.PWiz

@ H.PWiz C'est assez intelligent - je n'ai même pas pensé à le faire de cette façon!

Mego

3

Python 3 , 59 octets

lambda f,g,n:sum(f(d)*g(n//d)for d in range(1,n+1)if 1>n%d)

Essayez-le en ligne!

Leaky Nun
la source

Est-ce //vraiment nécessaire au lieu de /?

M. Xcoder

/produirait des flotteurs à droite?

Leaky Nun

Parce que dc'est un diviseur de npar définition, la partie fractionnaire de n/dest zéro, donc il ne devrait pas y avoir de problème avec l'arithmétique à virgule flottante. Les flottants avec une partie fractionnaire nulle sont assez proches des ints à des fins Pythoniques, et la sortie de la fonction est un nombre réel, donc faire n/dau lieu de n//ddevrait être bien.

Mego

3

Wolfram Language (Mathematica) , 17 octets

Bien sûr, Mathematica a une fonction intégrée. Il arrive également de connaître de nombreuses fonctions d'exemple. J'ai inclus quelques exemples de travail.

DirichletConvolve

Essayez-le en ligne!

Kelly Lowder
la source

2

Ajouter ++ , 51 octets

D,g,@~,$z€¦~¦*
D,f,@@@,@b[VdF#B]dbRzGb]$dbL$@*z€g¦+

Essayez-le en ligne!

Prend deux fonctions prédéfinies comme arguments, plus $n$ et sorties $(f * g)(n)$

Comment ça fonctionne

D,g,		; Define a helper function, $g
	@~,	; $g takes a single argument, an array, and splats that array to the stack
		; $g takes the argument e.g. [[τ(x) φ(x)] [3 4]]
		; STACK : 			[[τ(x) φ(x)] [3 4]]
	$z	; Swap and zip:			[[3 τ(x)] [4 φ(x)]]
	€¦~	; Reduce each by execution:	[[τ(3) φ(4)]]
	¦*	; Take the product and return:	τ(3)⋅φ(4) = 4

D,f,		; Define the main function, $f
	@@@,	; $f takes three arguments: φ(x), τ(x) and n (Let n = 12)
		; STACK:			[φ(x) τ(x) 12]
	@	; Reverse the stack:		[12 τ(x) φ(x)]
	b[V	; Pair and save:		[12]			Saved: [τ(x) φ(x)]
	dF#B]	; List of factors:		[[1 2 3 4 6 12]]
	dbR	; Copy and reverse:		[[1 2 3 4 6 12] [12 6 4 3 2 1]]
	z	; Zip together:			[[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]]]
	Gb]	; Push Saved:			[[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)]]]
	$dbL	; Number of dividors:		[[[τ(x) φ(x)]] [[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] 6]
	$@*	; Repeat:			[[[1 12] [2 6] [3 4] [4 3] [6 2] [12 1]] [[τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)] [τ(x) φ(x)]]]
	z	; Zip:				[[[τ(x) φ(x)] [1 12]] [[τ(x) φ(x)] [2 6]] [[τ(x) φ(x)] [3 4]] [[τ(x) φ(x)] [4 3]] [[τ(x) φ(x)] [6 2]] [[τ(x) φ(x)] [12 1]]]
	€g	; Run $g over each subarray:	[[4 4 4 6 4 6]]
	¦+	; Take the sum and return:	28

caird coinheringaahing
la source

2

R , 58 octets

function(n,f,g){for(i in (1:n)[!n%%1:n])F=F+f(i)*g(n/i)
F}

Essayez-le en ligne!

Prend n, fet g. Heureusement, le numberspaquet a déjà un certain nombre de fonctions implémentées.

Si des versions vectorisées étaient disponibles, ce qui est possible en enveloppant chacune Vectorize , la version suivante de 45 octets est possible:

R , 45 octets

function(n,f,g,x=1:n,i=x[!n%%x])f(i)%*%g(n/i)

Essayez-le en ligne!

Giuseppe
la source

2

APL (Dyalog Classic) , 20 octets

{(⍺⍺¨∘⌽+.×⍵⍵¨)∪⍵∨⍳⍵}

avec ⎕IO←1

Essayez-le en ligne!

Facile à résoudre, difficile à tester - généralement pas mon type de défi. Pourtant, j'ai beaucoup apprécié celui-ci!

{ }définit un opérateur dyadique dont les opérandes ⍺⍺et ⍵⍵les deux fonctions sont convolués; ⍵est l'argument numérique

∪⍵∨⍳⍵sont les diviseurs de ⍵dans l'ordre croissant, c'est-à-dire unique ( ∪) des LCM ( ∨) de ⍵avec tous les nombres naturels jusqu'à ( ⍳)

⍵⍵¨ appliquer l'opérande droit à chaque

⍺⍺¨∘⌽ appliquer l'opérande gauche à chacun en sens inverse

+.× produit intérieur - multiplier les éléments correspondants et additionner

La même chose dans ngn / apl semble meilleure en raison des identificateurs Unicode, mais prend 2 octets supplémentaires en raison de l'indexation 1.

ngn
la source

Je suis sûr que cela prend 27 octets supplémentaires dans ngn / apl ...

Erik the Outgolfer

1

Gelée , 9 octets

ÆDṚÇ€ḋÑ€Ʋ

Essayez-le en ligne!

La ligne en haut est la ligne principale de $f$ , la ligne en bas est la ligne principale de $g$ . $n$ est passé en argument à cette fonction.

Erik le Outgolfer
la source

1

Swift 4 , 74 70 54 octets

{n in(1...n).map{n%$0<1 ?f(n/$0)*g($0):0}.reduce(0,+)}

Essayez-le en ligne!

M. Xcoder
la source

1

JavaScript (ES6), 47 octets

Prend l'entrée comme (f)(g)(n).

f=>g=>h=(n,d=n)=>d&&!(n%d)*f(n/d)*g(d)+h(n,d-1)

Essayez-le en ligne!

Exemples

liouville =
n => (-1) ** (D = (n, k = 2) => k > n ? 0 : (n % k ? D(n, k + 1) : 1 + D(n / k, k)))(n)

mobius =
n => (M = (n, k = 1) => n % ++k ? k > n || M(n, k) : n / k % k && -M(n / k, k))(n)

sq =
n => +!((n ** 0.5) % 1)

identity =
n => 1

// sq = liouville * identity
console.log([...Array(25)].map((_, n) => F(liouville)(identity)(n + 1)))

// liouville = mobius * sq
console.log([...Array(20)].map((_, n) => F(mobius)(sq)(n + 1)))

Arnauld
la source

1

C (gcc) , 108 octets

#define F float
F c(F(*f)(int),F(*g)(int),int n){F s=0;for(int d=0;d++<n;)if(n%d<1)s+=f(n/d)*g(d);return s;}

Implémentation simple, volée sans vergogne à la réponse Python de Leaky Nun .

Non golfé:

float c(float (*f)(int), float (*g)(int), int n) {
    float s = 0;
    for(int d = 1; d <= n;++d) {
        if(n % d == 0) {
            s += f(n / d) * g(d);
        }
    }
    return s;
}

Essayez-le en ligne!

joH1
la source

1

F #, 72 octets

let x f g n=Seq.filter(fun d->n%d=0){1..n}|>Seq.sumBy(fun d->f(n/d)*g d)

Prend les deux fonctions fet get un nombre naturel n. Filtre les valeurs dqui ne se divisent pas naturellement n. Ensuite, les évalue f(n/d) et les g(d)multiplie et résume les résultats.

Ciaran_McCarthy
la source

0

Pari / GP , 32 octets

(f,g,n)->sumdiv(n,d,f(n/d)*g(d))

Essayez-le en ligne!

Il y a une dirmulfonction intégrée, mais elle ne prend en charge que des séquences finies .

alephalpha
la source

0

APL (NARS), 47 caractères, 94 octets

{(m⍵[1])×n⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}

où m et n sont la fonction que l'on doit utiliser (ceci parce que je ne sais pas comment appeler un tableau de fonction dans une fonction dans APL). En utilisant l'exemple ci-dessus, la multiplication de la fonction Mobius (ici, c'est 12π) et la fonction somme des diviseurs (ici, c'est 11π) pour la valeur 12, cette multiplication serait:

  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}12
12

si l'on doit calculer une autre valeur:

  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}1002
1002
  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}1001
1001
  {(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}20000x
20000

On peut voir si par exemple le premier nombre 2000 le résultat de la fonction est l'identité

  (⍳2000)≡{(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}¨⍳2000
1

RosLuP
la source

Dirichlet Convolution

Défi

Détails

Exemples

Exemple étape par étape

Réponses:

Lean , 108 100 95 78 75 octets

Haskell , 46 octets

Python 3 , 59 octets

Wolfram Language (Mathematica) , 17 octets

Ajouter ++ , 51 octets

Comment ça fonctionne

R , 58 octets

R , 45 octets

APL (Dyalog Classic) , 20 octets

Gelée , 9 octets

Swift 4 , 74 70 54 octets

JavaScript (ES6), 47 octets

Exemples

C (gcc) , 108 octets

F #, 72 octets

Pari / GP , 32 octets

APL (NARS), 47 caractères, 94 octets