Double Arithmetic Derivative

The arithmetic derivative is a beautiful example of number theory and has a surprising number of connections to other open problems in a variety of fields of mathematics.

My solution correlates to a paper written by Victor Ufnarovski and Bo Åhlander which can be found here .

According to the paper there are two such solutions to the problem.

Solution 1: Let $n=pqr$ , where $p$ , $q$ , and $r$ are distinct prime numbers.

$n'=(pqr)'=p'(qr)+p(q'r+qr')=qr+pr+pq$

If $qr+pr+pq$ is prime, then $n''=1$ .

Checking numbers under 100 leads to the following solutions:

$2\times3\times5=30$

$2\times3\times7=42$

$2\times3\times11=66$

$2\times5\times7=70$

$2\times3\times13=78$

Solution 2: Let $n=2p$ for some prime $p$ :

$n'=(2p)'=(2')(p)+(2)(p')=(1)(p)+(2)(1)=p+2$

If $p+2$ is prime as well, then $n''=1$ , therefore $2p$ is a solution to our problem.

If $p$ and $p+2$ are primes, then these numbers are what are known as "Twin Primes". Examples of this are $3$ & $5$ , $29$ & $31$ , etc. Whether there are an infinite number of Twin Primes is still an open problem, and proving that there are an infinite number of Twin Primes proves that there are an infinite number of solutions to our problem, $n''=1$ .

Here is the list of primes of the form $(p,p+2)$ where $2p < 100$ : $(3,5)$ , $(5,7)$ , $(11,13)$ , $(17,19)$ , $(29,31)$ , & $(41,43)$

Our final answer is equal to the sum of our answers from solution 1 and twice the sum of the first prime in each of the pairs of twin primes.

$(30+42+66+70+78)+2(3+5+11+17+29+41)=\boxed{498}$

This could have been a nice exercise in functional programming.

1
2
3
4
5
6
7
8

d :: Int -> Int
d n
    | n == 0 = 0
    | n == 1 = 0
    | otherwise = (n `div` p) + p * (d (n `div` p))
        where p = head [x | x <- [2..], n `mod` x == 0]

main = putStrLn $ show (sum [n | n <- [1..100], (d.d) n == 1])

Since the derivatives of 0, 1 and all primes are nonnegative integers, and nonnegativity is preserved by the rule $(ab)'=a'b+ab'$ , all derivatives of composites are nonnegative integers too.

All numbers below will be nonnegative integers.

Let $P$ denote the set of all prime numbers.

First establish Lemma 1: $n'=1 \Leftrightarrow n \in P$ The arrow from right to left is by definition; and if n is composite ( $n=ap$ with $a\geq 2, p \in P$ ), then $n'=a'p+ap'\geq a \geq 2$ . So composites never have derivative 1, which proves the arrow from left to right. ■

Lemma 2:. Let p be prime and k a positive integer, then $(p^k)'=kp^{k-1}$ For $k=1$ this is just $p'=1$ , which is the case by definition. For k>1: Step: $(p^k)'=(p\cdot p^{k-1})' = 1×p^{k-1}+p×(p^{k-1})'$ .

Applying this step by induction we get $(p^k)'=p^{k-1}+p(p^{k-2}+p(p^{k-3}+...))$ $=p^{k-1}+pp^{k-2}+p^2p^{k-3}...+p^{k-1}p^0=kp^{k-1}$ . ■

By lemma 1, we are looking for n, such that $n' \in P$ . All nonnegative integers fall in one of the following sets:

• 0 or 1. $n\in \{0, 1\}$ By definition $n'=0$ and therefore $n''=0 \neq 1$ .
• primes. $n \in P$ . By definition $n'=1$ and hence $n''=0 \neq 1$ .
• prime powers. $n \in \{p^k|p \in P, k>1\}$ . By lemma 2, $n' = kp^{k-1}$ , which is composite for $k \gt 1$ , so $n'' \neq 1$
• multiples of prime powers. $n \in \{ap^k| a,k >1, p\nmid a\}$ . $n'=a'p^k+akp^{k-1}=(a'p+ak)p^{k-1}$ . This is composite because both factors are larger than 1, so n $''\neq 1$
• products of two distinct primes. If $n=pq$ , then $n'=p+q$ In order for $n''$ to be 1, $p+q$ needs to be prime, which is only odd if one of the primes (say q) equals 2. Then $n'=(2p)'=2+p$ , This is prime if p is the lower of a twin prime. E.g. p=2, q=3. n=6, n'=2+3=5. All primes p below 50 for which $p+2$ is also prime are: $3, 5, 11, 17, 29, 41$ , so the $n$ for which $n''=1$ are $n \in \{6, 10,22,34,58,82\}$
• products of three distinct primes. If $n=pqr$ , then $n'=qr+pr+pq$ , which is always odd. All products of three different primes below 100 are: 30 : $30'r(2×3×5)'=15+10+6=31$ which is prime, 42 . $42'=(2×3×7)'=21+14+6=41$ which is prime, 66 . $66'=(2×3×11)'=33+22+6=61$ which is prime, 78 . $78'=(2×3×13)'=39+26+6=71$ which is prime, 70 . $70'=(2×5×7)'=35+14+10=59$ which is prime. So $n\in \{ 30,42,66,78,70\}$
• products of more than three distinct primes. These are all larger than 100.

Adding them all up $6+10+22+34+58+82+30+42+66+78+70=\boxed{498}$ .

See also https://oeis.org/A157037 .

Here we are searching for those numbers whose differentiation leads to a prime number which in turn differentiating leads to 1. ex:6.

case(i):
Any odd number less than 100 whose double differentiation (odd)'' cannot be 0. Because any odd number is a multiple of prime odd prime factors.
so for any odd number odd=p1xp2
(also note 2x3x7 is the least possible multiple of 3 odd prime 105>100)
so in this case differentiating (odd)'=p1+p2. Implies adding 2 odd numbers gives even number whose
double differentiation cannot be 1. i.e., (odd)'' can't be 1.

case(ii):
Also for all squares 1,4,9,16,25,36............ cannot yield prime number after first differentiation
4=2x2
(4)'=2+2=4 which is not a prime
36=9x4
(36)'=(9)'x4+9x(4)'=6x4+9x4 which is not a prime

case(iii):
All multiples of the square cannot yield prime after first differentiation 8,12,18,20.......
Because at least a multiple of one prime factor of a square.which can never be prime.
8=4x4
(8)'=4x4+4x4 is at least a multiple of one prime factor of a square.

18=9x2
(18)'=6x2+9 is a multiple of 3 which can never be prime.

So by
case(i): All odd numbers cannot be considered n<100 n is +ve.so 50 numbers left.

case(ii)and(iii): All multiples of squares cannot be considered so all even numbers multiple of 4 cannot be considered. So 25 even non-multiples of 4 are left. similarly, even multiples of 9,25,49 cannot be considered.

SO,
11 numbers left are which on double differentiation (n)'' yield 1 are

6
10
22
30
34
42
58
66
70
78
82

Adds to 498