Convolução de Dirichlet

19

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.f,gf,g:NR (fg):NR

Detalhes

  • Usamos a convenção .0N={1,2,3,}
  • 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 Nfgf,g
    (fg)(n)=d|nf(nd)g(d)=ij=nf(i)g(j).
    d|ndNnni=ndN,j=dNe 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 :
    (nNf(n)ns)(nNg(n)ns)=nN(fg)(n)ns
  • 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 fg é retornada ou, como alternativa, você pode pegar uma entrada adicional nN e retornar (fg)(n) diretamente.
  • Para simplificar, você pode assumir que todos os elementos de N podem ser representados com, por exemplo, um int positivo de 32 bits.
  • Para simplificar, você também pode assumir que cada entrada R 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 )
    ϵ(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, ...
  • a função da unidade 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, ...
  • a função de identidade ( A000027 )
    id(n)=nn
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
  • a função 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, ...
  • a função totiente 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, ...
  • a função Liouville ( A008836 ) que é o número de fatores primos de contados com multiplicidade
    λ(n)=(1)k
    kn1, -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 )
    σ(n)=d|nd
    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 )
    τ(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, ...
  • a função característica dos números quadrados ( A010052 )
    sq(n)={1 if n is a square number0otherwise
    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:

  • ϵ=1μ
  • f=ϵff
  • ϵ=λ|μ|
  • σ=φτ
  • id=σμσ = i d * 1 eσ=id1
  • sq=λ1 λ = μ s q eλ=μsq
  • τ=111 = τ * μ e1=τμ
  • id=φ1 eφ=idμ

O último para é uma consequência da inversão de Möbius : Para qualquer a equação é equivalente a .f,gg=f1f=gμ

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.f=μg=σμσn=12

ff(1)f(2)f(3)f(4)f(5)f(6)f(7)f(8)f(9)f(10)f(11)f(12)μ111011100110σ134761281513181228

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 concluirdNn=12dn=12=223d=1,2,3,4,6,12g=σdf=μnd

(μσ)(12)=μ(12)σ(1)+μ(6)σ(2)+μ(4)σ(3)+μ(3)σ(4)+μ(2)σ(6)+μ(1)σ(12)=01+13+04+(1)7+(1)12+128=0+310712+28=12=id(12)

flawr
fonte

Respostas:

4

Magra , 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

Experimente online!

Mais casos de teste com todas as funções.

Freira Furada
fonte
lambda é realmente mais caro que quatro bytes fun ?
Mario Carneiro
lambda é de três bytes, suponho
Leaky Nun
Eu acho que é dois em UTF8 (grego é muito baixo unicode)
Mario Carneiro
Você está certo. Eu também jogava golfe com a importação #
Leaky Nun
Eu também costumava condsalvar 5 bytes #
Nun Leaky #
4

Haskell , 46 bytes

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

Experimente online!

Graças ao flawr por -6 bytes e um grande desafio! E obrigado a H.PWiz por mais -6!

Mego
fonte
O mais simples é mais curto aqui
H.PWiz 17/17/18
@ H.PWiz Isso é muito inteligente - eu nem pensei em fazer dessa maneira!
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)

Experimente online!

Freira Furada
fonte
É //realmente necessário em vez de /?
Mr. Xcoder
/produziria carros alegóricos certo?
Leaky Nun
Como dé um divisor de, npor definição, a parte fracionária de n/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 em n/dvez de n//ddeve ser bom.
Mego
3

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.

DirichletConvolve

Experimente online!

Kelly Lowder
fonte
2

Adicionar ++ , 51 bytes

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

Experimente online!

Toma duas funções predefinidas como argumentos, mais , e saídasn(fg)(n)

Como 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
fonte
2

R , 58 bytes

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

Experimente online!

Toma n, fe g. Felizmente, o numberspacote 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

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

Experimente online!

Giuseppe
fonte
1

Geléia , 9 bytes

ÆDṚÇ€ḋÑ€Ʋ

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.fgn

Erik, o Outgolfer
fonte
1

Swift 4 ,  74 70  54 bytes

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

Experimente online!

Mr. Xcoder
fonte
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)

Experimente online!

Exemplos

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

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 soma


O mesmo em ngn / apl parece melhor por causa dos identificadores Unicode, mas ocupa 2 bytes adicionais por causa da indexação 1.

ngn
fonte
Certeza que demora 27 bytes adicionais em NGN / apl ...
Erik o Outgolfer
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;}

Implementação direta, descaradamente roubada da resposta Python do Leaky Nun .

Ungolfed:

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

Experimente online!

joH1
fonte
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 as duas funções fe ge um número natural n. Filtra os valores dque não se dividem naturalmente n. Em seguida, avalia f(n/d) e g(d)multiplica-os e soma os resultados.

Ciaran_McCarthy
fonte
0

Pari / GP , 32 bytes

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

Experimente online!

Existe uma dirmulfunção interna, mas suporta apenas sequências finitas .

alefalpha
fonte