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.
Detalles
- Usamos la convención .
- 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 Ny 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 :
- 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.
- Para simplificar, puede suponer que cada elemento de puede representarse con, por ejemplo, un int positivo de 32 bits.
- Para simplificar, también puede suponer que cada entrada puede representarse, por ejemplo, con un solo número de punto flotante real.
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 )
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, 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 )
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
- la función Möbius ( A008683 )
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 )
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
1, -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 )
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 )
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 )
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:
- y
- y
- y
- y
Los últimos son consecuencia de la inversión de Möbius : para cualquier , la ecuación es equivalente a .
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 y . Ahora evaluaremos su convolución en . Sus primeros términos se enumeran en la tabla a continuación.
La suma itera sobre todos los números naturales que dividen , por lo tanto asume todos los divisores naturales de . Estos son . En cada sumando, evaluamos en y lo multiplicamos por evaluado en . Ahora podemos concluir
fun
?cond
guardar 5 bytesHaskell , 46 bytes
Pruébalo en línea!
¡Gracias a flawr por -6 bytes y un gran desafío! ¡Y gracias a H.PWiz por otro -6!
fuente
Python 3 , 59 bytes
Pruébalo en línea!
fuente
//
realmente necesario en lugar de/
?/
produciría flotadores, ¿verdad?d
es un divisor de,n
por definición, la parte fraccional den/d
es 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 enn/d
lugar den//d
debería estar bien.Wolfram Language (Mathematica) , 17 bytes
Por supuesto, Mathematica tiene una función incorporada. También sucede que conoce muchas de las funciones de ejemplo. He incluido algunos ejemplos de trabajo.
Pruébalo en línea!
fuente
Agregar ++ , 51 bytes
Pruébalo en línea!
Toma dos funciones predefinidas como argumentos, másnorte y salidas ( f∗ g) ( n )
Cómo funciona
fuente
R , 58 bytes
Pruébalo en línea!
Toma
n
,f
yg
. Afortunadamente, elnumbers
paquete 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
Pruébalo en línea!
fuente
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 sumaLo mismo en ngn / apl se ve mejor debido a los identificadores Unicode, pero toma 2 bytes adicionales debido a la indexación 1.
fuente
Jalea , 9 bytes
Pruébalo en línea!
La línea en la parte superior es la línea principal deF , la línea en la parte inferior es la línea principal de sol . norte se pasa como argumento a esta función.
fuente
Swift 4 ,
74 7054 bytesPruébalo en línea!
fuente
JavaScript (ES6), 47 bytes
Toma entrada como
(f)(g)(n)
.Pruébalo en línea!
Ejemplos
fuente
C (gcc) , 108 bytes
Implementación directa, descaradamente robada de la respuesta Python de Leaky Nun .
Sin golf:
Pruébalo en línea!
fuente
F #, 72 bytes
Toma las dos funciones
f
yg
y un número naturaln
. Filtra los valoresd
que no se dividen naturalmente enn
. Luego evalúaf(n/d)
yg(d)
, los multiplica, y suma los resultados.fuente
Pari / GP , 32 bytes
Pruébalo en línea!
Hay una
dirmul
función incorporada, pero solo admite secuencias finitas .fuente
APL (NARS), 47 caracteres, 94 bytes
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:
si uno tiene que calcular algún otro valor:
Se puede ver si, por ejemplo, el primer número 2000 del resultado de la función es la identidad
fuente