Engineer's Book

Engineers – Telecoms – Physics – Teaching – Methods

Algorithmics 05 – Prime Numbers

Written By: Jean-Paul Cipria - Mai• 26•17
Number of Prime Numbers Density-800k

(Fig.1) – Number of Prime Numbers Density-800k – ©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-06-12 10:02:28.

<strong><span style="color: #800000;">Very Difficult ! PhD Level.</span></strong>

Very Difficult ! PhD Level.

Done ... Un Café ?

Done … Un Café ?

Then 32 years later M. Karatsuba [KARATSUBA-1995] understand as a very high level what he 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 annex thesis. So, hang in there and ride out the adverse periods. (Alors accrochez-vous et dépassez les étapes difficiles.)

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 …

Number of Prime Numbers Density-800k

(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.

Prime Numbers Density 1M - ©J.P. Cipria

(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 ?

Prime numbers Density - 1M - ©J.P. Cipria

(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.

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.


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 <i>\frac{log_2M}{T}</i> 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].


Scientifics Publications

  • KARATSUBA-1963] : KARATSUBA, A., et Yu OFMAN. « Multiplication of Multidigit Numbers on Automat ». Soviet Physics-Doklady Vol. 7 (1963): 595‑596.
  • [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


Jean-Paul Cipria

First Century Primes

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Anti-Spam Quiz: