Function Repository Resource:

ArithmeticD

Source Notebook

Compute the arithmetic derivative of a rational number

Contributed by: Shenghui Yang (Wolfram Research)

ResourceFunction["ArithmeticD"][r]

find the arithmetic derivative r' of a rational number r.

Details

Arithmetic derivative uses the explict formula of integer factorization from Barbeau's "Remarks on an arithmetic derivative".
The algorithm for finding the arithmetic derivative has the same complexity as integer factoriztion.
The arithmetic derivatives of 0 and 1 are zero.
The arithmetic derivative of any prime number is 1.
Arithmetic derivative follows Leibniz rule.
The second arithmetic derivative is the arithmetic derivative of the first arithmetic derivative; higher-order arithmetic derivatives are defined analogously.
Unlike the usual derivative studied in college calculus class, the arithmetic derivative does not obey linearity in general.
The arithmetic derivative behaves in ways that are not well understood in number theory; higher order derivatives present many unresolved properties.

Examples

Basic Examples (2) 

Find the arithmetic derivative of 100:

In[1]:=
ResourceFunction["ArithmeticD"][100]
Out[1]=

Find the arithmetic derivative of the fraction :

In[2]:=
ResourceFunction["ArithmeticD"][3/10]
Out[2]=

Scope (2) 

Arithmetic derivate for any prime is 1:

In[3]:=
ResourceFunction["ArithmeticD"][3]
Out[3]=

Using Leibniz rule it is easy to find the formula for prime tower :

In[4]:=
ResourceFunction["ArithmeticD"][3^11]
Out[4]=

which is the same as :

In[5]:=
11*3^10
Out[5]=

Properties and Relations (4) 

Higher order arithmetic derivatives are defined successively by nesting the same operation multiple times:

In[6]:=
ResourceFunction["ArithmeticD"][100]
Out[6]=
In[7]:=
NestList[ResourceFunction["ArithmeticD"], 100, 5]
Out[7]=

Arithmetic derivative of an integer n has the following bounds: , where is PrimeOmega[n] and gives the number of prime factors counting multiplicities.

The equality of the lower bound holds if and only if :

In[8]:=
DiscretePlot[
 ResourceFunction["ArithmeticD"][n]/
  With[{omega = PrimeOmega[n]}, omega*n^(1 - 1/omega)]
 , {n, 1, 100},
 PlotRange -> All, AxesOrigin -> {0, 1}]
Out[8]=

The equality of the upper bound holds if and only if n is prime or a prime tower:

In[9]:=
ListLogPlot[
 Table[((n*Log[n])/(2*Log[2]))/ResourceFunction["ArithmeticD"][n]
  , {n, 2, 100}], Sequence[
 PlotRange -> All, AxesOrigin -> {0, 0}, Filling -> Bottom, PlotStyle -> PointSize[0.01]]]
Out[9]=

if and only if where p is any prime:

In[10]:=
ResourceFunction["ArithmeticD"][17^17]
Out[10]=
In[11]:=
17^17
Out[11]=

It is easy to see that is not a fixed point:

In[12]:=
ResourceFunction["ArithmeticD"][17^17 + 1]
Out[12]=

has nontrivial solution for some rational value x:

In[13]:=
ResourceFunction["ArithmeticD"][4/27]
Out[13]=

Possible Issues (2) 

The arithmetic derivative does not obey linearity in general:

In[14]:=
ResourceFunction["ArithmeticD"] /@ {9, 10}
Out[14]=

Clearly 1 is not same as :

In[15]:=
ResourceFunction["ArithmeticD"][9 + 10]
Out[15]=

However, if we find some m and n such that , then for all integer k. For instance:

In[16]:=
ResourceFunction["ArithmeticD"] /@ {87, 78}
Out[16]=
In[17]:=
Total[%]
Out[17]=
In[18]:=
ResourceFunction["ArithmeticD"][87 + 78]
Out[18]=

Then the following also true:

In[19]:=
Total[ResourceFunction["ArithmeticD"] /@ (777*{87, 78})] == ResourceFunction["ArithmeticD"][777*(78 + 87)]
Out[19]=

Neat Examples (4) 

The graph of for

In[20]:=
Graph[Thread[
  Range[500] -> (ResourceFunction["ArithmeticD"] /@ Range[500])]]
Out[20]=

We can define the arithmetic integral by solving the equation given a, . The algorithm can be implemented with simple search in the interval found in the aforementioned bounds:

For example, the integrals of 10 and 100:

In[21]:=
ArithmeticI[10]
Out[21]=
In[22]:=
ArithmeticI[100]
Out[22]=

We also can find the a's that do not have their integrals less than 1000:

In[23]:=
LaunchKernels[];
res = ParallelMap[{#, ArithmeticILength[#]} &, Range[2, 1000]];
Cases[res, _?(#[[2]] == 0 &)][[All, 1]]
Out[18]=

Here is a list of number with more than one integral:

In[24]:=
Cases[res, _?(#[[2]] > 1 && #[[1]] <= 100 &)]
Out[24]=

The result means that 10 has two integrals, 12 has two integrals and so on.


The Goldbach conjecture implies that the differential equation has a positive integer solution for any natural number :

In[25]:=
Style[Entity["FamousMathProblem", "GoldbachConjectureStrong"][
  EntityProperty["FamousMathProblem", "Statement"]], "Text"]
Out[25]=

For instance as a sum of two primes:

In[26]:=
5 + 7
Out[26]=

By the Leibniz rule of arithmetic derivative, 35 is one solution for n such that the differential equation holds:

In[27]:=
ArithmeticI[12]
Out[27]=

Twin prime conjecture implies that the differential equation has infinite number of solutions:

In[28]:=
Style[Entity["FamousMathProblem", "TwinPrimeConjecture"][
  EntityProperty["FamousMathProblem", "Statement"]], "Text"]
Out[28]=

This is from the application of Leibniz rule on the arithmetic derivative of where p is any prime:

In[29]:=
ResourceFunction["ArithmeticD"][2*17]
Out[29]=
In[30]:=
ResourceFunction["ArithmeticD"][2]*17 + 2*ResourceFunction["ArithmeticD"][17]
Out[30]=

In general, . If is a prime again,

In[31]:=
NestList[ResourceFunction["ArithmeticD"], 2*17, 2] // Rest
Out[31]=

Thus we shall have infinite such if the conjecture holds.

Publisher

Shenghui Yang

Version History

  • 1.0.1 – 15 June 2022
  • 1.0.0 – 07 June 2022

Source Metadata

Author Notes

The efficiency of the ArithmeticI can be improved by building a large reverse lookup table ahead of computation.

License Information