Дирихле свертка

20

Свертка Дирихля является особым видом свертка , который выглядит как очень полезным инструмент в теории чисел. Он действует на множестве арифметических функций .

Вызов

Для двух арифметических функций f,g (т.е. функций f,g:NR ) вычисляется свертка Дирихле (fg):NR как определено ниже.

Детали

  • Мы используем соглашение .0N={1,2,3,}
  • Свертка Дирихле двух арифметических функций снова является арифметической функцией, и она определяется как(Обе суммы эквивалентны. Выражение означает делит , поэтому суммирование производится по натуральным делителям числа . Аналогично мы можем заменитьfgf,g
    (fg)(n)=d|nf(nd)g(d)=ij=nf(i)g(j).
    d|ndNnni=ndN,j=dNи мы получаем вторую эквивалентную формулировку. Если вы не привыкли к этой нотации, ниже приведен пошаговый пример.) Просто для уточнения (это не имеет непосредственного отношения к этой задаче): определение исходит из вычисления произведения ряда Дирихле :
    (nNf(n)ns)(nNg(n)ns)=nN(fg)(n)ns
  • Ввод дается в виде двух функций черного ящика . В качестве альтернативы, вы также можете использовать бесконечный список, генератор, поток или что-то подобное, что может привести к неограниченному количеству значений.
  • Есть два метода вывода: либо возвращается функция , либо вы можете взять дополнительный вход и вернуть напрямую.fgnN(fg)(n)
  • Для простоты вы можете предположить, что каждый элемент может быть представлен, например, с помощью положительного 32-битного целого числа.N
  • Для простоты вы также можете предположить, что каждая запись может быть представлена, например, одним действительным числом с плавающей запятой.R

Примеры

Давайте сначала определим несколько функций. Обратите внимание, что список чисел под каждым определением представляет первые несколько значений этой функции.

  • мультипликативная идентичность ( A000007 ) case
    ϵ(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, ...
  • постоянная единичная функция ( 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, ...
  • функция тождества ( A000027 )
    id(n)=nn
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ...
  • функция Мёбиуса ( 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, ...
  • функция Эйлера ( A000010 )
    φ(N)знак равноNΠп|N(1-1п)
    1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, ...
  • функция Лиувилля ( A008836 )
    λ(N)знак равно(-1)К
    где К - число простых множителей N подсчитанных с кратностью 1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1, 1, -1, -1, -1, ...
  • функция суммы делителей ( A000203 )
    σ(N)знак равноΣd|Nd
    1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, ...
  • функция подсчета делителей ( 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, ...
  • характеристическая функция квадратных чисел ( A010052 )
    sQ(N)знак равно{1 если N квадратное число0в противном случае
    1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

Тогда у нас есть следующие примеры:

  • εзнак равно1*μ
  • езнак равноε*ее
  • εзнак равноλ*|μ|
  • σзнак равноφ*τ
  • яdзнак равноσ*μ иσзнак равнояd*1
  • sQзнак равноλ*1 иλзнак равноμ*sQ
  • τзнак равно1*1 и1знак равноτ*μ
  • яdзнак равноφ*1 иφзнак равнояd*μ

Последнее для является следствием инверсии Мёбиуса : для любого е,грамм уравнение g=f1 эквивалентно f=gμ .

Шаг за шагом Пример

Это пример, который вычисляется шаг за шагом для тех, кто не знаком с обозначениями, используемыми в определении. Рассмотрим функции 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)е(12)μ1-1-10-11-1001-10σ134761281513181228

Сумма повторяется по всем натуральным числам dN которые делят Nзнак равно12 , поэтому d принимает все натуральные делители числа Nзнак равно12знак равно223 . Это d=1,2,3,4,6,12 . В каждом слагаемом мы оцениваем g=σ при d и умножаем его на f=μ вычисленный при nd . Теперь мы можем сделать вывод

(μ*σ)(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знак равнояd(12)

flawr
источник

Ответы:

5

Lean , 108 100 95 78 75 байт

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

Попробуйте онлайн!

Больше тестов со всеми функциями.

Дрянная Монахиня
источник
действительно ли лямбда дороже, чем четыре байта fun ?
Марио Карнейро
лямбда - три байта, я полагаю
Лики Монахиня
Я думаю, что это два в UTF8 (греческий довольно низкий Unicode)
Марио Карнейру
Ты прав. Я также играл в гольф
Leaky Nun
Я также использовал, condчтобы сохранить 5 байтов
Leaky Nun
4

Haskell , 46 байтов

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

Попробуйте онлайн!

Спасибо flawr за -6 байтов и большой вызов! И спасибо H.PWiz за еще один -6!

Mego
источник
Проще здесь короче
H.PWiz
@ H.PWiz Это довольно умно - я даже не думал делать это таким образом!
Mego
3

Python 3 , 59 байт

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

Попробуйте онлайн!

Дрянная Монахиня
источник
Является ли //действительно необходимо вместо /?
г-н Xcoder
/будет производить поплавки правильно?
Утренняя монахиня
Поскольку по определению dявляется делителем n, дробная часть n/dравна нулю, поэтому с арифметикой с плавающей запятой не должно быть никаких проблем. Плавы с дробной нулевой частью достаточно близки к целым числам для целей Pythonic, и вывод функции является действительным числом, поэтому n/dвместо этого n//dдолжно быть все в порядке.
Mego
2

Добавить ++ , 51 байт

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

Попробуйте онлайн!

Принимает две предопределенные функции в качестве аргументов плюс N и выводит (е*грамм)(N)

Как это устроено

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 Coneheringaahing
источник
2

R , 58 байт

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

Попробуйте онлайн!

Принимает n, fиg . К счастью, в numbersпакете уже реализовано немало функций.

Если векторизованные версии были доступны, что возможно путем переноса каждой из них Vectorize, то возможна следующая 45-байтовая версия:

R , 45 байт

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

Попробуйте онлайн!

Giuseppe
источник
2

APL (Dyalog Classic) , 20 байтов

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

с ⎕IO←1

Попробуйте онлайн!

Легко решить, трудно проверить - как правило, не мой тип задач. Тем не менее, мне очень понравилось это!

{ }определяет диадический оператор, операнды ⍺⍺и ⍵⍵две свертываемые функции; числовой аргумент

∪⍵∨⍳⍵делители в возрастающем порядке, то есть unique ( ) из LCM ( ) со всеми натуральными числами до него ( )

⍵⍵¨ применить правильный операнд к каждому

⍺⍺¨∘⌽ применить левый операнд к каждому в обратном порядке

+.× внутреннее произведение - умножить соответствующие элементы и сложить


То же самое в ngn / apl выглядит лучше из-за идентификаторов Unicode, но занимает 2 дополнительных байта из-за 1-индексации.

СПП
источник
Уверен, что в ngn / apl требуется 27 дополнительных байтов ...
Эрик Аутгольфер
1

JavaScript (ES6), 47 байт

Принимает вход как (f)(g)(n).

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

Попробуйте онлайн!

Примеры

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
источник
1

F #, 72 байта

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

Принимает две функции fи gнатуральное число n. Отфильтровывает значения, dкоторые естественно не делятся на n. Затем оценивает f(n/d) и g(d), умножает их вместе и суммирует результаты.

Ciaran_McCarthy
источник
0

APL (NARS), 47 символов, 94 байта

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

где m и n - функции, которые нужно использовать (это потому, что я не знаю, как вызвать один массив функций в одной функции в APL). Используя приведенный выше пример умножения функции Мёбиуса (здесь это 12π) и суммы функции делителей (здесь это 11π) для значения 12, умножение будет:

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

если нужно вычислить другое значение:

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

Можно увидеть, если, например, первое число 2000 результат функции является тождеством

  (⍳2000)≡{(12π⍵[1])×11π⍵[2]}{+/⍺⍺¨{k←⍳⍵⋄(⍵÷b),¨b←k/⍨0=k∣⍵}⍵}¨⍳2000
1
RosLuP
источник