A convolução de Dirichlet é um tipo especial de convolução que aparece como uma ferramenta muito útil na teoria dos números. Opera no conjunto de funções aritméticas .
Desafio
Dadas duas funções aritméticas (ou seja, funções ) calcule a convolução do Dirichlet conforme definido abaixo.
Detalhes
- Usamos a convenção .
- A convolução de Dirichlet de duas funções aritméticas f, g é novamente uma função aritmética e é definida como (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). (Ambas as somas são equivalentes. A expressão d | n significa d \ in \ mathbb N divide n , portanto, a soma está acima dos divisores naturais de n . Da mesma forma, podemos substituir i = \ frac {n} {d} \ in \ mathbb N, j = d \ in \ mathbb Ne temos a segunda formulação equivalente. Se você não está acostumado a essa notação, há um exemplo passo a passo a seguir.) Apenas para elaborar (isso não é diretamente relevante para este desafio): A definição vem do cálculo do produto da série Dirichlet :
- A entrada é fornecida como duas funções de caixa preta . Como alternativa, você também pode usar uma lista infinita, um gerador, um fluxo ou algo semelhante que possa produzir um número ilimitado de valores.
- Existem dois métodos de saída: Uma função é retornada ou, como alternativa, você pode pegar uma entrada adicional e retornar diretamente.
- Para simplificar, você pode assumir que todos os elementos de podem ser representados com, por exemplo, um int positivo de 32 bits.
- Para simplificar, você também pode assumir que cada entrada pode ser representada por, por exemplo, um único número de ponto flutuante real.
Exemplos
Vamos primeiro definir algumas funções. Observe que a lista de números abaixo de cada definição representa os primeiros valores dessa função.
- a identidade multiplicativa ( A000007 )
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
- a função da unidade constante ( A000012 )
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
- a função de identidade ( A000027 )
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
- a função Möbius ( A008683 )
1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, ...
- a função totiente de Euler ( A000010 )
1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ...
- a função Liouville ( A008836 )
que é o número de fatores primos de contados com multiplicidade
1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...
- a função de soma do divisor ( A000203 )
1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ...
- a função de contagem do divisor ( 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, ...
- a função característica dos números quadrados ( 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, ...
Então, temos os seguintes exemplos:
- σ = i d * 1 e
- λ = μ ∗ s q e
- 1 = τ * μ e
- e
O último para é uma consequência da inversão de Möbius : Para qualquer a equação é equivalente a .
Exemplo passo a passo
Este é um exemplo calculado passo a passo para aqueles que não estão familiarizados com a notação usada na definição. Considere as funções e . Vamos agora avaliar sua convolução em . Seus primeiros termos estão listados na tabela abaixo.
A soma itera sobre todos os números naturais que dividem , assim assume todos os divisores naturais de . Estes são . Em cada soma, avaliamos em e multiplicamos por avaliado em . Agora podemos concluir
fun
?cond
salvar 5 bytes #Haskell , 46 bytes
Experimente online!
Graças ao flawr por -6 bytes e um grande desafio! E obrigado a H.PWiz por mais -6!
fonte
Python 3 , 59 bytes
Experimente online!
fonte
//
realmente necessário em vez de/
?/
produziria carros alegóricos certo?d
é um divisor de,n
por definição, a parte fracionária den/d
é zero; portanto, não deve haver problemas com a aritmética de ponto flutuante. Flutuadores com parte zero fracionária são próximos o suficiente de entradas para fins de Python, e a saída da função é um número real, portanto, fazer isso emn/d
vez den//d
deve ser bom.Wolfram Language (Mathematica) , 17 bytes
Claro que o Mathematica possui um built-in. Também acontece de conhecer muitas das funções de exemplo. Eu incluí alguns exemplos de trabalho.
Experimente online!
fonte
Adicionar ++ , 51 bytes
Experimente online!
Toma duas funções predefinidas como argumentos, mais , e saídasn (f∗g)(n)
Como funciona
fonte
R , 58 bytes
Experimente online!
Toma
n
,f
eg
. Felizmente, onumbers
pacote já possui algumas das funções implementadas.Se houvesse versões vetorizadas disponíveis, o que é possível agrupando cada uma delas
Vectorize
, é possível a seguinte versão de 45 bytes:R , 45 bytes
Experimente online!
fonte
Geléia , 9 bytes
Experimente online!
A linha no topo é a linha principal de , a linha no fundo é a linha principal de . é passado como argumento para esta função.f g n
fonte
Swift 4 ,
74 7054 bytesExperimente online!
fonte
JavaScript (ES6), 47 bytes
Toma entrada como
(f)(g)(n)
.Experimente online!
Exemplos
fonte
APL (Dyalog Classic) , 20 bytes
com
⎕IO←1
Experimente online!
Fácil de resolver, difícil de testar - geralmente não é o meu tipo de desafio. No entanto, eu gostei muito deste!
{
}
define um operador diádico cujos operandos⍺⍺
e⍵⍵
são as duas funções que estão sendo convoluídas;⍵
é o argumento numérico∪⍵∨⍳⍵
são os divisores de⍵
em ordem crescente, ou seja, únicos (∪
) dos LCMs (∨
) de⍵
com todos os números naturais até ele (⍳
)⍵⍵¨
aplique o operando certo a cada⍺⍺¨∘⌽
aplique o operando esquerdo a cada um no sentido inverso+.×
produto interno - multiplique os elementos correspondentes e a somaO mesmo em ngn / apl parece melhor por causa dos identificadores Unicode, mas ocupa 2 bytes adicionais por causa da indexação 1.
fonte
C (gcc) , 108 bytes
Implementação direta, descaradamente roubada da resposta Python do Leaky Nun .
Ungolfed:
Experimente online!
fonte
F #, 72 bytes
Toma as duas funções
f
eg
e um número naturaln
. Filtra os valoresd
que não se dividem naturalmenten
. Em seguida, avaliaf(n/d)
eg(d)
multiplica-os e soma os resultados.fonte
Pari / GP , 32 bytes
Experimente online!
Existe uma
dirmul
função interna, mas suporta apenas sequências finitas .fonte