Konvolusi Dirichlet

19

The Dirichlet konvolusi adalah jenis khusus dari konvolusi yang muncul sebagai alat yang sangat berguna di nomor teori. Ini beroperasi pada set fungsi aritmatika .

Tantangan

Diberikan dua fungsi aritmatika f,g (yaitu fungsi f,g:NR ) menghitung konvolusi Dirichlet sebagaimana didefinisikan di bawah ini.(fg):NR

Detail

  • Kami menggunakan konvensi .0N={1,2,3,...}
  • The Dirichlet konvolusi fg dari dua fungsi aritmatika f,g lagi fungsi aritmatika, dan itu didefinisikan sebagai
    (fg)(n)=d|nf(nd)g(d)=sayaj=nf(saya)g(j).
    (Kedua jumlah yang setara Ekspresi.d|nsaranadNmembagi, karena penjumlahan adalah atas alampembagidari nDemikian pula kita dapat subsitute.I=nnnsaya=ndN,j=dNdan kami mendapatkan formulasi setara kedua. Jika Anda tidak terbiasa dengan notasi ini ada langkah demi langkah contoh di bawah ini) Hanya untuk menguraikan (ini tidak secara langsung relevan untuk tantangan ini):. Definisi tersebut berasal dari komputasi produk dariseri Dirichlet:
    (nNf(n)ns)(nNg(n)ns)=nN(fg)(n)ns
  • Input diberikan sebagai dua fungsi kotak hitam . Atau, Anda juga bisa menggunakan daftar tanpa batas, generator, aliran, atau sesuatu yang serupa yang dapat menghasilkan jumlah nilai yang tidak terbatas.
  • Ada dua metode keluaran: Salah satu fungsi fg dikembalikan, atau Anda dapat mengambil input tambahan nN dan mengembalikan (fg)(n) secara langsung.
  • Untuk kesederhanaan Anda dapat mengasumsikan bahwa setiap elemen N dapat diwakili dengan misalnya int 32-bit positif.
  • Untuk kesederhanaan Anda juga dapat mengasumsikan bahwa setiap entri R dapat diwakili oleh misalnya satu angka floating point nyata.

Contohnya

Mari kita tentukan beberapa fungsi. Perhatikan bahwa daftar angka di bawah setiap definisi mewakili beberapa nilai pertama dari fungsi itu.

  • identitas multiplikatif ( 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, ...
  • fungsi unit konstan ( 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, ...
  • fungsi identitas ( A000027 )
    id(n)=nn
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
  • fungsi 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, ...
  • fungsi totient Euler ( A000010 )
    φ(n)=nhal|n(1-1hal)
    1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ...
  • fungsi Liouville ( A008836 )
    λ(n)=(-1)k
    mana k adalah jumlah faktor prima dari n dihitung dengan multiplisitas 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...
  • fungsi jumlah pembagi ( A000203 )
    σ(n)=d|nd
    1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ...
  • fungsi penghitung pembagi ( 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, ...
  • fungsi karakteristik bilangan kuadrat ( A010052 )
    sq(n)={1 jika n adalah angka kuadrat0jika tidak
    1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

Kemudian kita memiliki contoh berikut:

  • ϵ=1μ
  • f=ϵff
  • ϵ=λ|μ|
  • σ=φτ
  • sayad=σμ danσ=sayad1
  • sq=λ1 danλ=μsq
  • τ=11 dan1=τμ
  • id=φ1 danφ=idμ

Yang terakhir adalah konsekuensi dari inversi Mbius : Untuk setiap f,g persamaan g=f1 setara dengan f=gμ .

Langkah demi Langkah Contoh

Ini adalah contoh yang dihitung langkah demi langkah untuk mereka yang tidak terbiasa dengan notasi yang digunakan dalam definisi. Pertimbangkan fungsinyaf=μ dang=σ . Kami sekarang akan mengevaluasi konvolusi merekaμσ padan=12 . Beberapa istilah pertama mereka tercantum dalam tabel di bawah ini.

ff(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-10-11-1001-10σ134761281513181228

Jumlahnya berulang atas semua bilangan asli dN yang membagi n=12 , dengan demikian d mengasumsikan semua pembagi alami n=12=223 . Ini adalah d=1,2,3,4,6,12 . Dalam setiap ringkasan, kami mengevaluasig=σ padad dan mengalikannya denganf=μ dievaluasi padand . Sekarang kita bisa menyimpulkan

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

cacat
sumber

Jawaban:

4

Lean , 108 100 95 78 75 byte

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

Cobalah online!

Lebih banyak testcases dengan semua fungsi.

Biarawati Bocor
sumber
apakah lambda benar-benar lebih mahal daripada empat byte fun ?
Mario Carneiro
lambda adalah tiga byte, saya kira
Leaky Nun
Saya pikir itu dua di UTF8 (bahasa Yunani adalah unicode yang cukup rendah)
Mario Carneiro
Kamu benar. Saya juga bermain golf impor
Leaky Nun
Saya juga biasa condmenyimpan 5 byte
Leaky Nun
4

Haskell , 46 byte

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

Cobalah online!

Terima kasih kepada flawr untuk -6 byte dan tantangan besar! Dan terima kasih kepada H.PWiz untuk -6 lainnya!

Mego
sumber
Simpler lebih pendek di sini
H.PWiz
@ H.PWiz Itu cukup pintar - saya bahkan tidak berpikir untuk melakukannya dengan cara itu!
Mego
3

Python 3 , 59 byte

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

Cobalah online!

Biarawati Bocor
sumber
Apakah //benar-benar dibutuhkan, bukan /?
Tn. Xcoder
/akan menghasilkan mengapung kan?
Leaky Nun
Karena dmerupakan pembagi ndengan definisi, bagian fraksional n/dadalah nol, jadi seharusnya tidak ada masalah dengan aritmatika floating point. Mengapung dengan pecahan bagian nol cukup dekat dengan int untuk keperluan Pythonic, dan output dari fungsi adalah bilangan real, sehingga melakukan n/dalih - alih n//dharus baik-baik saja.
Mego
3

Bahasa Wolfram (Mathematica) , 17 byte

Tentu saja Mathematica memiliki built-in. Itu juga terjadi untuk mengetahui banyak fungsi contoh. Saya telah memasukkan beberapa contoh kerja.

DirichletConvolve

Cobalah online!

Kelly Lowder
sumber
2

Tambahkan ++ , 51 byte

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

Cobalah online!

Mengambil dua fungsi yang telah didefinisikan sebelumnya sebagai argumen, plus n, dan output (fg)(n)

Bagaimana itu bekerja

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

R , 58 byte

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

Cobalah online!

Membawa n, f, dan g. Untungnya numberspaket tersebut memiliki beberapa fungsi yang sudah diimplementasikan.

Jika versi vektor tersedia, yang dimungkinkan dengan membungkus masing-masing dengan Vectorize, maka versi 45 byte berikut ini mungkin:

R , 45 byte

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

Cobalah online!

Giuseppe
sumber
1

Jelly , 9 byte

ÆDṚÇ€ḋÑ€Ʋ

Cobalah online!

Baris di atas adalah jalur utama f, garis di bagian bawah adalah jalur utama g. n dilewatkan sebagai argumen untuk fungsi ini.

Erik the Outgolfer
sumber
1

Swift 4 ,  74 70  54 byte

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

Cobalah online!

Tuan Xcoder
sumber
1

JavaScript (ES6), 47 byte

Mengambil input sebagai (f)(g)(n).

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

Cobalah online!

Contohnya

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

APL (Dyalog Classic) , 20 byte

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

dengan ⎕IO←1

Cobalah online!

Mudah dipecahkan, sulit diuji - umumnya bukan tipe tantangan saya. Namun, saya sangat menikmati yang satu ini!

{ }mendefinisikan operator diad yang operandnya ⍺⍺dan ⍵⍵dua fungsinya dililit; adalah argumen numerik

∪⍵∨⍳⍵adalah pembagi dalam urutan menaik, yaitu unik ( ) dari LCMs ( ) dengan semua bilangan alami sampai ke sana ( )

⍵⍵¨ terapkan operan yang tepat untuk masing-masing

⍺⍺¨∘⌽ terapkan operan kiri ke masing-masing secara terbalik

+.× produk dalam - gandakan elemen yang sesuai dan jumlah


Hal yang sama dalam ngn / apl terlihat lebih baik karena pengidentifikasi Unicode, tetapi membutuhkan 2 byte tambahan karena pengindeksan 1.

ngn
sumber
Cukup yakin dibutuhkan 27 byte tambahan di ngn / apl ...
Erik the Outgolfer
1

C (gcc) , 108 byte

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

Implementasi langsung, tanpa malu-malu dicuri dari jawaban Python Leaky Nun .

Tidak Disatukan:

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

Cobalah online!

joH1
sumber
1

F #, 72 byte

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

Mengambil dua fungsi fdan gdan bilangan alami n. Menyaring nilai-nilai dyang tidak terbagi secara alami n. Kemudian mengevaluasi f(n/d) dan g(d), melipatgandakannya, dan menjumlahkan hasilnya.

Ciaran_McCarthy
sumber
0

Pari / GP , 32 byte

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

Cobalah online!

Ada dirmulfungsi bawaan, tetapi hanya mendukung urutan terbatas .

alephalpha
sumber