OEIS a003415

A project that implements sequence A003415 from OEIS, the On-line Encyclopedia of Integer Sequences. The sequence in question is the arithmetic derivative of a number:

n' = arithmetic derivative of n: f(0) = f(1) = 0; f(prime) = 1; f(m * n) = (m * f(n)) + (n * f(m)). Can be extended to negative numbers by defining f(-n) = -f(n).

I implemented the arithmetic derivative with 2 major blocks:


(algorithm from here, 1000 primes from here)


... this algorithm I kind of made up myself and frankly don't really know how to explain. pf-1 stands for "prime factorization 1-step," and does one level of prime factorization. For example, while the prime factorization of 4755 is 3x5x317, pf-1 returns 15x317. It checks numbers from 1 to the ceiling value to see if they are a factor of n. If it doesn't return a valid factor (i.e. the block says that a number only has the factor of 1 when it isn't prime), the ceiling value is increased, and it is called again. Both the initial ceiling value and the value by which you increase the ceiling are arbitrary, but I think 20 and 10 are good so you don't have to run the algorithm too many times... which should save on time...

These blocks are used in the prime factorization block (which isn't used in the project)...


and the arithmetic derivative block, which was the main goal of the project:

Yeah!! There's no real point to it, just having fun. But I hope it is interesting!

Interesting. Does the answer not depend on the order in which you find factors? (As I understand the definition, there's no requirement that either m or n be prime.)

I don't think it does? I don't know why, though. My best guess is just because of the commutative property-- no matter what, for every number n, you're eventually just summing the arithmetic derivatives of the prime factors of n. Like f(30) = 6f(5) + 5f(6) = 6f(5) + 5(2f(3) + 3f(2)), so it doesn't matter whether you say 6f(5) + 10f(3) + 15f(2) or 15f(2) + 10f(3) + 6f(5)?

I was thinking more about associativity than about commutativity. For example, it has to be that f(240)=f(24·10)=f(16·15). And indeed both of those reduce to 480·f(2)+80·f(3)+48·f(5). But I'm not sure where those coefficients come from.