## Engineer's Book

Engineers – Telecoms – Physics – Teaching – Innovations

## Algorithmics 05-1 – Prime Numbers

Written By: Jean-Paul Cipria - Mai• 26•17

Matlab User Interface – PhD Annexes – Prime Numbers – ©J.P. Cipria 2017.

Why don’t we read [KARATSUBA-1963] references ? Has a habit there are two theorems :
. Theorem 1 called as Ofman.
. Theorem 2 called as Karatsuba.
. Lemme …
… without a correct demonstration ?

.

Created :2017-05-26 11:22:32. – Modified : 2017-07-31 18:21:00.

Very Difficult ! PhD Level.

Done … Un Café ?

Russian Mathematician M. Karatsuba and Ofman wrote a paper in 1963 with two theorems and a lemme [1] . But we can’t understand correctly the demonstration on its paper. Therefore 32 years later M. Karatsuba [2] understand as a very high level what they said 32 years ago and it is more efficient to … understand it ! Then, doctors in sciences (PhD), please, read only this last scientific reference ?

We continue by Matlab calculations how some theorems had proved by M. Karatsuba in 1995 in this article extract from annexes thesis. « So, hang in there and ride out the adverse periods. » (Alors accrochez-vous et dépassez les étapes difficiles.)

First step : « How to calculate prime number ? What is a density ? What form is the integral ?

Let’s see small film :

Link to the film if plugin doesn’t work : Film.

Our first research question as a PhD scientist is :

• « How to calculate efficiently with the more accuracy a lot of operations, for exemple with Matlab ?«

For exemple in cryptology we need to calculate numbers with a great amount of digits. In atomic clock accuracy is more than $10^{-16}$. Then we need to do additions and then multiplications with by exemple 23 digits by 23 digits there are 23+23+1=47 digits result. Then Matlab on « normal condition » calculates only by 32 digits. Then on first time:

• « How to increase accuracy then in second how to optimise or minimise the number of calculations ?«

Then scholars, high level skills engineers have think about this in the 1990th. Let’s read it. Let’s calculate prime numbers by the Eratosthene Method – « Algorithmics 04 – Prime Numbers » Then we tried it and we displayed the one million calculation with about 79000 prime numbers rationnaly calculated.

• « What is a Multiplication ?«
• « How to decompose a number on a perpendicular base of vector ? »
• « What is a Prime Number ? »
• « By what algorithm do we construct them ? »
• « What is its probability Densities ? »

# Do Number of Prime Numbers Defined ?

Do the Prime Number Increase Curve go to Infinite ?

YES, we can do it by calculation with the very long Eratosthène Method. But for 1 Million calculation we spend 3 mn and for 10 millions 4h30 (not compiled). Then we occupied 25% of processor time we can do four calculations at the same time. Just to « observe » physical behaviour « with hands » as we said before doing more clever or astucious methods. Let’s know, by hands and brain the physical phenomenon. So …

(Fig.2) – Number of Prime Numbers Density-800k (Integral) – ©J.P. Cipria

For 800 000 calculation curve seems to be increase. For 1 000 000 also, for 10 000 000 … idem. Observe beginning of diagram then the very small curve (to the ground).

Increase to infinity ? CQFD for 10 000 000.

## What is the Prime Number Density (of probability) ?

Is it important to determinate the probability density of Prime number when we increase X ? Yes it is. Why ? Because as like the Bose-Einstein density probability we can made calculation on physics phenomenon ? It is right for atomic and nuclear physics then it is right for mathematical number properties ?

VERY IMPORTANT DISCOVER or Measurements by calculation. Let’s observe attentively this curve.

(Fig.3) – Prime Numbers Density 1 million operations- ©J.P. Cipria

More the $X$ increase and less the prime numbers exist but … the integral of this curve don’t converge. As some demonstrations prove it the number of prime numbers is infinite as the first picture above (integral).

## Do we Change the Statistical Mode ?

Sample by 1000 against 100 ? Then ?

(Fig.4) – Prime numbers Density – 1M – ©J.P. Cipria

Fig.4 is better to understand ? Is’n it ? Then lesson ? Be carefull how we choose quantity of data on a statistical mode !

Then we can feel that this curve on Fig.2, on integral first picture, as like the $\sum \frac{1}{k}$ sum and look like a $ln(k)$ ! We can calculate it but we can’t do calculation to infiny. And a contrario more the $X$ is big more the chance it will be divisible. then more X is hight and more we have a chance it will be composed as $X=p_n \dot \dot \dot *p_i$ or as a result of a multiplication by two, three, n prime numbers.

## Matlab User Interface

Matlab User Interface – Prime Numbers – PhD Annexes – ©J.P. Cipria 2017.

We concept a Matlab user interface (UI) with the uicontrol command. We send number of calculation to prime number function. Then it return name of file with data. We displyed it on a multiline text. The number densities is displayed at the right side. Other picture maybe displayed in the main figure by « open a file » button.

## What sort of Physics Quantities are the Equations Displayed ?

Do the number $k$ of Prime Numbers by 100 or 1000 parts $X$ calculations increase like a $Nb=ln(k)$ ?

We can observe that $Nb=ln(k)$ looks like $S=\frac{1}{k}*ln(k)$ where $S$ is an Entropy. It miss only $\frac{1}{k}$ as we can interpret as the probability coefficient.

# Conclusions

## Prime Numbers Entropy ?

• Fig 4 is a Prime Number Density Entropy.
• Fig 2 is a Prime Number Entropy.

We don’t know who had said this theory but it seems to be prove by the calculations curves : Then CQFD ?

## How is the decreasing ?

• $Prime_{Entropy}~=~a*\frac{1}{x^{0.1}}+b$

The decreasing coefficient is about $0.1$ Then this is inf to 1 ==> Integral can’t converge.

CQFD by Simulation from 0 to 10 000 000 !

## How do we read C. Shannon ?

After reading C. Shannon [SHANNON-1998], also after 1998, we discovered that he « DEFINE » some physics concepts without any explanations at the first pages :

• $\lim\limits_{\substack{n \to \infty \\ n>0}} \frac{log_2M}{T}$

We begin to understand that $\frac{log_2M}{T}$ represent such an entropy is limited by time and is convergent. Why ? Entropy varies as $ln M$ and are infinite when n grew as infinite. Then we understand with Karatsuba 1. Why do we use logarithm and 2. Why we use the 2 binary system. CQFD. Then read [KARATSUBA-1995] then [KARATSUBA-1963] and after understanding prove read [SHANNON-1998].

# References

## Scientifics Publications

• [1] [KARATSUBA-1963] : KARATSUBA, A., et Yu OFMAN. « Multiplication of Multidigit Numbers on Automat ». Soviet Physics-Doklady Vol. 7 (1963): 595‑596.
.
• [2] [KARATSUBA-1995] : KARATSUBA, A. « The Complexity of Computation », 1995.
.
• [SHANNON-1998] : SHANNON, C.E. « Communication In The Presence Of Noise – Proceedings of the IEEE. VOL. 86, NO. 2, FEBRUARY 1998 », 1998.
.

## Fichier programme

See Erathostène Method :

Algorithmic 06 – The Billion, the Billion* ! Primes !

.

Jean-Paul Cipria
26/05/2017