Convolución de Dirichlet

20

La convolución de Dirichlet es un tipo especial de convolución que aparece como una herramienta muy útil en la teoría de números. Funciona en el conjunto de funciones aritméticas .

Desafío

Dadas dos funciones aritméticas (es decir, funciones ) calculan la convolución de Dirichlet como se define a continuación.f,gf,g:NR (fg):NR

Detalles

  • Usamos la convención .0N={1,2,3,}
  • La convolución de Dirichlet de dos funciones aritméticas es nuevamente una función aritmética, y se define como(Ambas sumas son equivalentes. La expresión d | n significa d \ in \ mathbb N divide n , por lo tanto, la suma es sobre los divisores naturales de n . De manera similar, podemos sustituir i = \ frac {n} {d} \ in \ mathbb N, j = d \ in \ mathbb Nfgf,g
    (Fsol)(norte)=reEl |norteF(nortere)sol(re)=yoj=norteF(yo)sol(j).
    reEl |norterenortenortenorteyo=norterenorte,j=renortey obtenemos la segunda formulación equivalente. Si no está acostumbrado a esta notación, hay un ejemplo paso a paso a continuación. Solo para elaborar (esto no es directamente relevante para este desafío): la definición proviene de calcular el producto de la serie Dirichlet :
    (nortenorteF(norte)nortes)(nortenortesol(norte)nortes)=nortenorte(Fsol)(norte)nortes
  • La entrada se da como dos funciones de recuadro negro . Alternativamente, también podría usar una lista infinita, un generador, una secuencia o algo similar que podría producir un número ilimitado de valores.
  • Hay dos métodos de salida: se devuelve una función o, alternativamente, puede tomar una entrada adicional y devolver directamente.Fsolnortenorte(Fsol)(norte)
  • Para simplificar, puede suponer que cada elemento de puede representarse con, por ejemplo, un int positivo de 32 bits.norte
  • Para simplificar, también puede suponer que cada entrada puede representarse, por ejemplo, con un solo número de punto flotante real.R

Ejemplos

Primero definamos algunas funciones. Tenga en cuenta que la lista de números debajo de cada definición representa los primeros valores de esa función.

  • la identidad multiplicativa ( A000007 )
    ϵ(n)={1n=10n>1
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
  • la función de unidad constante ( A000012 )
    1(n)=1n
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
  • la función de identidad ( A000027 )
    id(n)=nn
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
  • la función Möbius ( A008683 )
    μ(n)={(1)k if n is squarefree and k is the number of Primefactors of n0 otherwise 
    1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, ...
  • la función totient de Euler ( A000010 )
    φ(n)=np|n(11p)
    1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ...
  • la función de Liouville ( A008836 ) donde es el número de factores primos de contados con multiplicidad
    λ(n)=(1)k
    kn1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...
  • la función de suma de divisores ( A000203 )
    σ(n)=d|nd
    1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ...
  • la función de conteo de divisores ( A000005 )
    τ(n)=d|n1
    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 función característica de los números cuadrados ( A010052 )
    sq(norte)={1 Si norte es un número cuadrado0 0de otra manera
    1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

Luego tenemos los siguientes ejemplos:

  • ϵ=1μ
  • F=ϵFF
  • ϵ=λEl |μEl |
  • σ=φτ
  • id=σμ yσ=id1
  • sq=λ1 yλ=μsq
  • τ=11 y1=τμ
  • yore=φ1 yφ=yoreμ

Los últimos son consecuencia de la inversión de Möbius : para cualquier ,F,sol la ecuación sol=F1 es equivalente a F=solμ .

Ejemplo paso a paso

Este es un ejemplo que se calcula paso a paso para quienes no están familiarizados con la notación utilizada en la definición. Considere las funciones F=μ y sol=σ . Ahora evaluaremos su convolución μσ en norte=12 . Sus primeros términos se enumeran en la tabla a continuación.

FF(1)F(2)F(3)F(4 4)F(5 5)F(6 6)F(7 7)F(8)F(9 9)F(10)F(11)F(12)μ1-1-10 0-11-10 00 01-10 0σ134 47 76 6128151318 años1228

La suma itera sobre todos los números naturales dN que dividen n=12 , por lo tanto d asume todos los divisores naturales de n=12=223 . Estos son d=1,2,3,4,6,12 . En cada sumando, evaluamos g=σ en d y lo multiplicamos por f=μ evaluado en nd . Ahora podemos concluir

(μσ)(12)=μ(12)σ(1)+μ(6 6)σ(2)+μ(4 4)σ(3)+μ(3)σ(4 4)+μ(2)σ(6 6)+μ(1)σ(12)=0 01+13+0 04 4+(-1)7 7+(-1)12+128=0 0+310 0-7 7-12+28=12=yore(12)

falla
fuente

Respuestas:

4

Magras , 108 100 95 78 75 bytes

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

Pruébalo en línea!

Más casos de prueba con todas las funciones.

Monja permeable
fuente
¿Es lambda realmente más caro que cuatro bytes fun ?
Mario Carneiro
lambda es de tres bytes, supongo
Leaky Nun
Creo que son dos en UTF8 (el griego es bastante bajo Unicode)
Mario Carneiro
Tienes razón. También jugué golf a la importación
Leaky Nun
También solía condguardar 5 bytes
Leaky Nun
4

Haskell , 46 bytes

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

Pruébalo en línea!

¡Gracias a flawr por -6 bytes y un gran desafío! ¡Y gracias a H.PWiz por otro -6!

Mego
fuente
Más simple es más corto aquí
H.PWiz
@ H.PWiz Eso es bastante inteligente, ¡ni siquiera pensé en hacerlo de esa manera!
Mego
3

Python 3 , 59 bytes

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

Pruébalo en línea!

Monja permeable
fuente
¿Es //realmente necesario en lugar de /?
Sr. Xcoder
/produciría flotadores, ¿verdad?
Leaky Nun
Debido a que des un divisor de, npor definición, la parte fraccional de n/des cero, por lo que no debería haber problemas con la aritmética de coma flotante. Los flotadores con fracción cero fraccionaria están lo suficientemente cerca de los ints para fines pitónicos, y la salida de la función es un número real, por lo que hacerlo en n/dlugar de n//ddebería estar bien.
Mego
2

Agregar ++ , 51 bytes

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

Pruébalo en línea!

Toma dos funciones predefinidas como argumentos, más nortey salidas (Fsol)(norte)

Cómo funciona

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
fuente
2

R , 58 bytes

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

Pruébalo en línea!

Toma n, fy g. Afortunadamente, el numberspaquete ya tiene implementadas algunas de las funciones.

Si las versiones vectorizadas estuvieran disponibles, lo cual es posible envolviendo cada una Vectorize, entonces es posible la siguiente versión de 45 bytes:

R , 45 bytes

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

Pruébalo en línea!

Giuseppe
fuente
2

APL (Dyalog Classic) , 20 bytes

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

con ⎕IO←1

Pruébalo en línea!

Fácil de resolver, difícil de probar, generalmente no es mi tipo de desafío. ¡Sin embargo, disfruté mucho de este!

{ }define un operador diádico cuyos operandos ⍺⍺y ⍵⍵son las dos funciones convolucionadas; es el argumento numérico

∪⍵∨⍳⍵son los divisores de en orden ascendente, es decir, únicos ( ) de los MCM ( ) de con todos los números naturales hasta él ( )

⍵⍵¨ aplicar el operando correcto a cada

⍺⍺¨∘⌽ aplicar el operando izquierdo a cada uno a la inversa

+.× producto interno: multiplica los elementos correspondientes y la suma


Lo mismo en ngn / apl se ve mejor debido a los identificadores Unicode, pero toma 2 bytes adicionales debido a la indexación 1.

ngn
fuente
Bastante seguro de que toma 27 bytes adicionales en ngn / apl ...
Erik the Outgolfer
1

Jalea , 9 bytes

ÆDṚÇ€ḋÑ€Ʋ

Pruébalo en línea!

La línea en la parte superior es la línea principal de F, la línea en la parte inferior es la línea principal de sol. norte se pasa como argumento a esta función.

Erik el Outgolfer
fuente
1

JavaScript (ES6), 47 bytes

Toma entrada como (f)(g)(n).

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

Pruébalo en línea!

Ejemplos

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
fuente
1

C (gcc) , 108 bytes

#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;}

Implementación directa, descaradamente robada de la respuesta Python de Leaky Nun .

Sin 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;
}

Pruébalo en línea!

joH1
fuente
1

F #, 72 bytes

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

Toma las dos funciones fy gy un número natural n. Filtra los valores dque no se dividen naturalmente en n. Luego evalúa f(n/d) y g(d), los multiplica, y suma los resultados.

Ciaran_McCarthy
fuente
0

APL (NARS), 47 caracteres, 94 bytes

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

donde myn son la función que uno tiene que usar (esto porque no sé cómo llamar a una matriz de funciones en una función en APL). Usando el ejemplo anterior, la función de multiplicación de Mobius (aquí es 12π) y la función de suma de divisores (aquí es 11π) para el valor 12, esa multiplicación sería:

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

si uno tiene que calcular algún otro valor:

  {(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 

Se puede ver si, por ejemplo, el primer número 2000 del resultado de la función es la identidad

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