Pochodna funkcji jest kamieniem węgielnym matematyki, inżynierii, fizyki, biologii, chemii i wielu innych nauk. Dzisiaj będziemy obliczać coś tylko stycznie zależnego: pochodną arytmetyczną.
Definicja
Pochodna arytmetyczna a(n)
lub n'
jest zdefiniowana tutaj ( A003415 ) przez szereg właściwości, które są podobne do pochodnej funkcji.
a(0) = a(1) = 0
,a(p) = 1
, gdziep
jest jakaś liczba pierwsza, oraza(mn) = m*a(n) + n*a(m)
.
Trzecia zasada opiera się na zasadzie produktowej dla zróżnicowania funkcji: dla funkcji f(x)
i g(x)
, (fg)' = f'g + fg'
. Więc z liczb (ab)' = a'b + ab'
.
Należy również zauważyć, że ponieważ pochodną arytmetyczną można rozszerzyć na liczby ujemne za pomocą tej prostej zależności a(-n) = -a(n)
, dane wejściowe mogą być ujemne.
Zasady
- Napisz program lub funkcję, która przy dowolnej liczbie całkowitej
n
zwraca arytmetyczną pochodnąn
. - Wejścia będą
-230 < n < 230
, aby uniknąć problemów z liczbami całkowitymi i liczbami zbyt dużymi, aby uwzględnić je w rozsądnym czasie. Twój algorytm powinien nadal być w stanie teoretycznie obliczyć pochodną arytmetyczną liczb spoza tego zakresu. - Dozwolone są wbudowane funkcje matematyki symbolicznej, faktoryzacji i rozróżniania liczb pierwszych.
Przykłady
> 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
Jak zawsze, jeśli problem jest niejasny, daj mi znać. Powodzenia i dobrej gry w golfa!
code-golf
math
sequence
arithmetic
number-theory
Sherlock9
źródło
źródło
prime
wa(prime)
środku? Czy to tylko liczba pierwsza?Odpowiedzi:
MATL, 12 bytes
Try it online!
Explanation
Consider an integer a with |a|>1, and let the (possibly repeated) prime factors of |a| be f1, ..., fn. Then the desired result is a·(1/f1 + ... + 1/fn).
źródło
1
gives1
as its "prime" number decomposition. It's a strange result (an empty array would be more meaningful). But that's how Matlab works. And also CJam. So I guess there must be good reason to output1
in that case? What do you think? I've been tempted to redefine theYf
function to output an empty array for1
, but I wasn't surePython, 59 bytes
A recursive function. On large inputs, it runs out of stack depth on typical systems unless you run it with something like Stackless Python.
The recursive definition is implemented directly, counting up to search for candidate prime factors. Since
f(prime)=1
, ifn
has a primep
as a factor, we havef(n) == p*f(n/p)+n/p
.źródło
Jelly,
87 bytes-1 byte by @Dennis
Uses the same formula everyone else does. However, there's a little trick to deal with
0
.Try it here.
źródło
Python 2,
87787674 bytesImprovements thanks to @Maltysen:
Further improvement by two bytes:
Further improvement thanks to @xnor:
Explanation
The arithmetic derivative of
a
is equal toa
times the sum of the reciprocals of the prime factors ofa
. No exception for 1 is needed since the sum of the reciprocals of the prime factors of 1 is zero.źródło
abs(a)>1
can bea*a>1
.d,s = 2,0
Haskell,
20390 bytesThanks @nimi!
I still have no idea when what indentations cause what interpretation, this is the shortest I managed so far, and as always, I'm sure it can be golfed a lot more. I'm going to try again in the evening.
źródło
J,
302719 charsThanks to @Dennis for chopping off 3 characters.
Thanks to @Zgarb for chopping off 8 characters.
Try it online!
Sample input:
How it works:
źródło
Pyth -
108 bytesLovin' the implicit input! Should bring it on par with Jelly for most things (Except Dennis' golfing skills).
Test Suite.
źródło
Haskell, 59 bytes
Implements the recursive definition directly, with an auxiliary variable
p
that counts up to search for potential prime factors, starting from2
. The last line is the main function, which plugsp=2
to the binary function defined in the first line.The function checks each case in turn:
n*n<2
, thenn
is one of-1,0,1
, and the result is0
.n
is not a multiple ofp
, then incrementp
and continue.n=p*r
, and by the "derivative" property, the result isr*a(p)+p*a(r)
, which simplifies tor+p*a(r)
becausep
is prime.The last case saves bytes by binding
r
in a guard, which also avoids the1>0
for the boilerplateotherwise
. Ifr
could be bound earlier, the second conditionmod n p>0
could be checked asr*p==n
, which is 3 bytes shorter, but I don't see how to do that.źródło
Seriously,
17141112 bytesMy first ever Seriously answer. This answer is based on Luis Mendo's MATL answer and the idea that the arithmetic derivative of a number
m
is equal tom·(1/p1 + 1/p2 + ... + 1/pn)
wherep1...pn
is every prime factor ofn
to multiplicity. My addition is to note that, ifm = p1e1·p2e2·...·pnen
, thena(m) = m·(e1/p1 + e2/p2 + ... + en/pn)
. Thanks to Mego for golfing and bug fixing help. Try it online!Ungolfing:
źródło
Japt -x,
161310 bytes- 6 bytes thanks to @Shaggy
Try it online!
źródło
N.k()
doesn't work on them.-x
flag.APL (Dyalog Extended),
139 bytesA simple solution. The Dyalog Unicode version was simply a longer version of this so it has been omitted.
Edit: Saved 4 bytes by adopting the method in lirtosiast's Jelly solution.
Try it online!
Ungolfing
źródło
Ruby,
876680757068 bytesThis answer is based on Luis Mendo's MATL answer, wythagoras's Python answer, and the idea that the arithmetic derivative of a number
m
is equal tom·(1/p1 + 1/p2 + ... + 1/pn)
wherep1...pn
is every prime factor ofn
to multiplicity.This function is called in the following way:
Ungolfing:
źródło
Julia,
7243 bytesThis is an anonymous function that accepts an integer and returns a float. To call it, assign it to a variable.
For an input integer n, if n2 ≤ 1 return 0. Otherwise obtain the prime factorization of n2 as a
Dict
, then for each prime/exponent pair, divide the prime by its exponent, then divide n by the result. This is just computing n x / p, where p is the prime factor and x is its exponent, which is the same as summing n / p, x times. We sum the resulting array and divide that by 2, since we've summed twice as much as we need. That's due to the fact that we're factoring n2 rather than n. (Doing that is a byte shorter than factoring |n|.)Saved 29 bytes thanks to Dennis!
źródło
Jolf, 13 bytes
Kudos to the MATL answer for the algorithm! Try it here, or test them all at once. (Outputs [key,out] in an array.)
Explanation
źródło
Mathematica 10.0, 39 bytes
źródło
FactorInteger@1
yields{1,1}
, so theIf
function is no longer necessary, saving 10 bytes.{{1,1}}
, returned by my version ({}
is the expected result to me).APL(NARS), 35 char, 70 bytes
test and how to use:
I thought that it would not be ok because I don't know if c variable is composed (and not a prime)... But seems ok for the test...
źródło
05AB1E,
74 bytesPort of @lirtosiast's Jelly answer.
Try it online or verify all test cases.
Explanation:
źródło
Perl 5, 62 bytes
Uses the formula (from OEIS):
If n = Product p_i^e_i, a(n) = n * Sum (e_i/p_i).
źródło
Perl 6, 90
This might be a bit slow for large numbers. Replace
2..^n
with2..n.sqrt
for longer code but faster computation.źródło
Ink, 183 bytes
Try it online!
I refuse to believe this is a good solution, but I can't see a way to improve it either.
źródło
Pari/GP, 45 bytes
Try it online!
źródło