Codegolf — Арифметическая Производная

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

Определение

Арифметическая производная

 > a(1)
0
> a(7)
1
> a(14)   # a(7)*2 + a(2)*7 = 1*2 + 1*7 = 9
9
> a(-5)   # a(-5) = -a(5) = -1
-1
> a(8)    # a(8) = a(2**3) = 3*2**2 = 12
12
> a(225)  # a(225) = a(9)*25 + a(25)*9 = 6*25 + 10*9 = 150 + 90 = 240
240
> a(299792458)  # a(299792458) = a(2)*149896229 + a(7)*42827494 + a(73)*4106746 + a(293339)*1022 = 1*149896229 + 1*42827494 + 1*4106746 + 1*1022 = 149896229 + 42827494 + 4106746 + 1022 = 196831491
196831491
 

• n ,
• n , where a(-n) = -a(n) любое простое число, и
• (ab)' = a'b + ab' .

Третье правило основано на правиле произведения дифференциации функций: для функций (fg)' = f'g + fg' and g(x) , f(x) . So with numbers, a(mn) = m*a(n) + n*a(m) .

Также следует отметить, что арифметическая производная может быть распространена на отрицательные числа с помощью этого простого соотношения: p , the input may be negative.

Правила

• Напишите программу или функцию, которая по любому целому числу a(p) = 1 , returns the arithmetic derivative of a(0) = a(1) = 0 .
• Входы будут n' , to avoid problems with integer sizes and numbers too large to factor in a reasonable amount of time. Your algorithm should still be able to theoretically calculate the arithmetic derivative of numbers outside this range.
• Допускаются встроенные функции символьной математики, факторизации простых чисел и дифференцирования.

Примеры

Как всегда, если проблема неясна, пожалуйста, дайте мне знать. Удачи и хорошей игры в гольф!

#код-гольф #математика #последовательность #арифметика #теория чисел

МАТЛ, 12 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 n->n*vecsum([i[2]/p|i<-factor(n)~,0<p=i[1]])
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Объяснение

Рассмотрим целое число а с |а|>1, и пусть (возможно, повторяющиеся) простые множители |а| быть ж₁, ..., ж_н. Тогда желаемый результат а·(1/ж₁ + ... + 1/ж_н).

Питон, 59 байт

Рекурсивная функция. При больших входных данных в типичных системах ему не хватает глубины стека, если только вы не запускаете его с чем-то вроде Бесстековый Python.

Рекурсивное определение реализуется напрямую, осуществляя подсчет для поиска кандидатов на простые множители. С 2..^n , if sub A(\n) {0>n??-A(-n)!!(n>1)*{$_??n/$_*A($_)+$_*A n/$_!!1}(first n%%*,2..^n)};say A slurp имеет простое число If n = Product p_i^e_i, a(n) = n * Sum (e_i/p_i). as a factor, we have perl -MMath::Prime::Util=:all -E"map$i+=1/$_,factor abs($j=<>);say$i*$j" .

Желе, 8 7 байт

-1 байт от @Dennis

Использует ту же формулу, что и все остальные. Однако есть небольшая хитрость, с которой нужно справиться. ȧǐ/ .

Попробуйте это здесь.

Python 2, 87 78 76 74 байта

Улучшения благодаря @Maltysen:

Дальнейшее улучшение на два байта:

Дальнейшее улучшение благодаря @xnor:

Объяснение

Арифметическая производная Tr[If[#>1,#2/#,0]&@@@FactorInteger@#]#& is equal to *jmauΜm)jd/1H *j input times m)j p.f. of input Μ d/1H mapped to inverse u sum of ma abs of раз сумму обратных величин простых множителей *jmauΜm)jd/1H . No exception for 1 is needed since the sum of the reciprocals of the prime factors of 1 is zero.

Хаскелл, 203 90 байт

Спасибо @nimi!

Я до сих пор понятия не имею, какие отступы вызывают какую интерпретацию, это самое короткое, что мне удалось до сих пор, и, как всегда, я уверен, что в него можно играть гораздо больше. Вечером попробую еще раз.

Дж, 30 27 19 символов

Благодаря @Деннис за отрубание 3 символов.

Благодаря @Zgarb за отрубание 8 символов.

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

Пример ввода:

Как это работает:

Пиф — 10 8 байт

Обожаю неявный ввод! Должен привести его на один уровень с Джелли по большинству вещей (кроме навыков игры в гольф Денниса).

Тестовый набор.

Хаскель, 59 байт

Реализует рекурсивное определение напрямую с помощью вспомогательной переменной. m that counts up to search for potential prime factors, starting from Dict . Последняя строка — это основная функция, которая подключает n->n^2>1?sum(p->n÷/(p...),factor(n^2))/2:0 to the binary function defined in the first line.

Функция проверяет каждый случай по очереди:

• Если def a(n) s = 0 m = n.abs (2...m).each do |z| while m%d == 0 m /= d s += n / d end end if s == 0 if n > 1 s += 1 # if s is 0, either n is prime and the while loop added nothing, so add 1 # or n.abs < 2, so return 0 anyway # 0**s is used in the code because it returns 1 if s == 0 and 0 for all other s end end return s end , then > a=->n{s=0;(2...m=n.abs).map{|d|(m/=d;s+=n/d)while m%d<1};m<2?0:s+0**s} > a[299792458] 196831491 является одним из ->n{s=0;(2...m=n.abs).map{|d|(m/=d;s+=n/d)while m%d<1};m<2?0:s+0**s} , and the result is n .
• Если p1...pn is not a multiple of m·(1/p1 + 1/p2 + ... + 1/pn) , затем увеличьте m and continue.
• В противном случае выразите {+/⍵÷э|⍵} { } A dfn, a function in {} brackets. ?|⍵ The prime factors of the absolute value of our input. ⍵÷ Then divide our input by the above array, giving us a list of products for the product rule. +/ We sum the above numbers, giving us our arithmetic derivative. , and by the "derivative" property, the result is {+/⍵÷э|⍵} , что упрощает ÒU©a k £/X because r*p==n является простым.

Последний случай сохраняет байты обязательность mod n p>0 in a guard, что также позволяет избежать r for the boilerplate otherwise . Если 1>0 could be bound earlier, the second condition r можно проверить как p , which is 3 bytes shorter, but I don't see how to do that.

Япт -х, 16 13 10 байт

- 6 байт благодаря @Shaggy

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

APL (расширенный диалог), 13 9 байт

Простое решение. Версия Dyalog Unicode была просто более длинной версией, поэтому она была опущена.

Редактировать: Сэкономлено 4 байта за счет применения метода из желейный раствор лиртосиаста.

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

Унгольфинг

Рубин, 87 66 80 75 70 68 байт

Этот ответ основан на Ответ Луиса Мендо на MATL, ответ Витагора на Pythonи идея о том, что арифметическая производная числа p is equal to p где n is every prime factor of 0 к множественности.

Эта функция вызывается следующим образом:

Унгольфинг:

Юля, 72 43 байта

Это анонимная функция, которая принимает целое число и возвращает число с плавающей запятой. Чтобы вызвать его, присвойте его переменной.

Для входного целого числа н, если н² ≤ 1 возвращает 0. В противном случае получите простую факторизацию н² как 2 , then for each prime/exponent pair, divide the prime by its exponent, then divide н по результату. Это просто вычисления н х / п, где п является основным фактором и х - его показатель, который аналогичен суммированию н / п, х раз. Суммируем полученный массив и делим его на 2, так как мы просуммировали вдвое больше, чем нам нужно. Это связано с тем, что мы факторизуем н² скорее, чем н. (Это на байт короче, чем факторизация |н|.)

Сэкономлено 29 байт благодаря Денису!

Серьезно, 17 14 11 12 байт

Мой первый серьезный ответ. Этот ответ основан на Ответ Луиса Мендо на MATL и идея о том, что арифметическая производная числа p is equal to n%p|n*n<2=0|mod n p>0=n%(p+1)|r<-div n p=r+p*r%2 (%2) где * Times the input, implicitly (This also adds the sign back in) s Sum cL1 Reciprocal mapped over lit P Prime factorization .a Absolute value of input, implicitly is every prime factor of *scL1P.a к множественности. Мое дополнение состоит в том, чтобы отметить, что если 0:`(*[:+/%@q:@|)@.* N XX`[email protected] if Z then Y else X end 0: X: return 0 Z Z: signum(N) (*[:+/%@q:@|) Y: N*add_all(reciprocal_all(all_prime_factors(abs(N)))) N * * [:+/ add_all( ) %@ reciprocal_all( ) q:@ all_prime_factors( ) | abs( ) N , then 0:`(*[:+/%@q:@|)@.* _8 _12 0:`(*[:+/%@q:@|)@.* 0 0 0:`(*[:+/%@q:@|)@.* 8 12 . Благодаря Мего за игру в гольф и помощь в исправлении ошибок. Попробуйте онлайн!

Унгольфинг:

Йольф, 13 байт

Престижность за ответ MATL на алгоритм! Попробуйте здесь, или протестируйте их все сразу. (Выводит [key,out] в массиве.)

Объяснение

Математика 10.0, 39 байт

APL(NARS), 35 символов, 70 байт

тест и как использовать:

Я думал, что это будет неправильно, потому что я не знаю, является ли переменная c составной (а не простой)... Но для теста это нормально...

05AB1E, 7 4 байты

Порт @lirtosiast's Jelly ответ.

Попробуйте онлайн или проверить все тестовые случаи.

Объяснение:

Виксал o¬AÆfİS× Main link. Inputs: n o¬ Logical OR of n with its logical NOT That is, 0 goes to 1 and everything else goes to itself. A Then take the absolute value Æf get its list of prime factors İ divide 1 by those S sum × and multiply by the input. , 3 bytes

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

-1 спасибо Underslash

Перл 5, 62 байта

Использует формулу (из OEIS): p

Перл 6, 90

Это может быть немного медленно для больших чисел. Заменять f(prime)=1 with f=lambda n,p=2:+(n*n>1)and(n%p and f(n,p+1)or p*f(n/p)+n/p) для более длинного кода, но более быстрого вычисления.

Чернила, 183 байта

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

Я отказываюсь верить, что это хорошее решение, но я также не вижу способа его улучшить.

Париж/GP, 44 байта

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