prime numbers

The article is about the question: Is the distribution of the prime numbers uniform random? Applied mathematics says NO! They are not uniform randomly distributed among the (odd) natural numbers! This might have consequences for our view of the universe, since the distribution of the prime numbers is also involved in the Riemann Zeta function which accurately describes the quantum eigenvalues up to now. So even quantum chaos and quantum mechanical randomness might be ruled by the distribution of the prime numbers. If this is true is there any true randomness out there in the universe?

Journal of Randomics archives

Standup comedy Martin Hapklaar (Dutch)

Budget calculator website for people with low income

Workshop for art projects

X-INDEX Fund technical analysis investments on international stock exchanges

My workportfolio extension rťsumť (Dutch)

Journal of Randomics scientific papers and blogs

Kleursymboliek Atelier: Computer art on assignment (Dutch)

About longevity supplements all from the supermarket (Dutch)

Lies van Dalen Psychotherapie Rotterdam (Dutch)

Ariena van der Ree Endovelicus Clinic Afvallen en Afslanken Rotterdam (Dutch)

Gislanien Sommer Thuiszorg Rotterdam (Dutch)

 

Copyright & Disclaimer

 

 

SATOCONOR .COM

J.G. van der GaliŽn ĎAre The Prime Numbers Randomly Distributed?í 1.2. (2002)

Communications to the editor

SATOCONOR.COM Journal of RANDOMICS

 

 

Are The Prime Numbers Randomly Distributed? Part 1

By: Johan G. van der GaliŽn (M.Sc.)

For comments e-mail: johan.van.der.galien@satoconor.com

Version 1.5. April 23, 2006 (version 1.1. from August 27, 2002)

 

HOME of SATOCONOR.COM

 

READ ALSO: 'A New Algorithmic Definition of Prime Number' by S. Chambers.

 

READ ALSO: 'The Last Digit Distribution of Prime Numbers' by J.G. van der GaliŽn and M. Winer.

 

READ ALSO: 'Randomics: The Study of Patterns and Randomness' by J.G. van der GaliŽn and M. Winer.

 

Download the PASCAL program PRIME9.PAS.

 

Download the PASCAL program PRIME27.PAS

 

Download the PASCAL program HBPRM2.PAS

 

The prime numbers up to 109 were transformed to Benford numbers and the digital distribution results were subjected to a Goodness-of-Fit Chi-square analysis.

If the prime numbers are truly uniform random then, for an infinite amount of them, their Benford counterparts should be evenly distributed among the digits 1 to 9.

But the Chi-square values increased with the amount of prime numbers tested, far beyond the point of reasonable doubt, with a confidence level << 10-10. Thus falsifying the null-hypothesis (H0 = The prime numbers are truly uniform random).

 

The prime numbers are regarded as one of the last arithmetic strongholds of true randomness. This is best illustrated by the words of R. C. Vaughan (February 1990): " It is evident that the prime numbers are randomly distributed but, unfortunately, we don't know what 'random' means." As if in the properties of the most ordered system we know, the set of natural numbers, there is still a fraction of pure chaos or randomness. And the prime numbers are the key to quantum chaos because of the connection between the Riemann Zeta function and random matrix theory.1 It might well be so that random numbers generated by quantum mechanic phenomena, like radioactive decay, is also reigned by the prime numbers.2 Could it be that true randomness is merely a utopia? In other words is the whole universe deterministic, and not governed by quantum mechanic change or randomness? A deterministic universe is also the key factor of the Omega Point hypothesis of Frank J. Tipler, it is about the fate of humanity in the far future and the after-life for all of us. (This also means that in time the whole universe, including the whole evolution with all living beings ever existed, will be uploaded into a gigantic computer animation.) 3 In my opinion the prime numbers are the key to this enigma!

Up to now there was no means to really test the randomness of the prime numbers. In this article a method is presented which is inspired by, measuring the first digit distribution like in, the Law of Benford.4 The key to this method is the following hypothesis: if the prime numbers are truly uniform random then, for an infinite amount of them, the distribution of their first digits (1,2,3Ö9) should all be equal to 100/9 ≈ 11,1111111111%. In Table 1 the results for the digital distributions of the prime numbers under N = 10, 102, 103, 104, 105, 106, 107, 108 and 109 is given. (To ensure that all digits have an equal probability of occurrence, in case the primes are truly random, one has to calculate the digital distribution for N is a power of 10.) These result are the output obtained by a PASCAL program called PRIME9, see Index for downloading the source code. The amount of prime numbers under the different Nís are in accordance with the values found on the internet.5 So there are no flaws in the way PRIME9 calculates the prime numbers.

What becomes clear of the digital distribution from the higher Nís, (N >= 103) which have a significant amount of prime numbers to do a distribution calculation in contrast to N < 103, that in Table 1 there is a strong bias in the results. In other words there are great deviations from the expected 11,1111111111%, what a true random distribution would give for each digit. Fig. 1 shows this bias for N = 109.

 

 

Fig.1: The bias in the digital distribution.

 

In order to quantify this bias the results of Table 1 were subjected to a Chi-square Goodness-of-Fit test also by means of the PASCAL program PRIME9. The calculated Chi-square values for the different Nís can also be found in Table 1.

 

 

Fig. 2: The Chi-square development.

 

If you want to falsify the null-hypothesis (H0 = the prime numbers are truly randomly distributed) for 8 degrees of freedom with a confidence level <= 10-10 then Chi-square has to be >= 56,4586.6 As one can clearly see from Fig. 2 and Table 1 that with an increasing N, with N >= 106 above the critical point, Chi-square goes far beyond 56,4586. This can only mean that for N >= 106 H0 is falsified with a confidence level of << 10-10.

The results proof that the prime numbers are not uniform randomly distributed among the natural numbers. This can easely be understood because there are not that many even primes! (There is of course only one even prime: 2) If they were random among all natural numbers then there should be equal amounts of odd and even primes. So lets forget the even prime and the even natural numbers. Remains only the odd primes among odd natural numbers. My results indicate too that the (odd) primes are also not uniform randomly distributed among all the odd natural numbers! My results are actually a consequence of the approximate amount of primes under x (any integer x > 1), the prime counting function, given by [x/Log(x) = x/Ln(x), Log(x) and Ln(x) different notation for the natural logarithm base e]. Also called the conjecture of Gauss, proven in 1896 by Hadamard and De la Vallee Pousin. Take for instance the approximate amount of primes between x = 10000 and 20000 is 933, between x = 20000 and 30000 is 890, between x = 30000 and 40000 is 864 and so on. To come back to the formula that inspired me, the Law of Benford (% of digit = Ln(1+1/digit)*100/Ln(10)), the primes do not obey this law. The % of digit are to evenly distributed, you can see that at a glance and you do not need Chi-square for that. So if the prime numbers are not uniform randomly distributed, and if they some how determine quantum chaos, is there then any true randomness out there in the universe? These results also indicate that there must be a mathematical formula to describe all prime numbers since they are not randomly distributed! After 5500 years of civilisation in which the prime numbers are known it is time that we, the scientific community, tackle this problem.7

 

Erratum:

 

As a matter of fact such mathematical formula's which can calculate the n-th prime already exist as I found out through the newsgroups. So my conclusion from the described research that they can exist was right! Thus no one can call the prime numbers random anymore, according to the definition of randomness that there is no deterministic process (Note: but for the prime numbers there are the n-formula's) which can predict better than change what the next element of a given "random" sequence will be. These n-formula's can be found on several places on the internet.8,9 One of the n-formula's I have incorporated in a PASCAL program PRIME27 (see the Index for downloading the source code).

 

{* Calculates the first hundred primes by means of the formula of Sebastian Martin Ruiz (2002) *}

{* Copyright Johan Gerard van der Galien 27 August 2002 johan.van.der.galien@satoconor.com *}

 

program prime27;

var j,k,n,s,Ik,Hs,Gk,P1n,Pn: longint;

†††     R:text;

 

Function entier(a:real):longint;

var rnd,trnc:longint;

begin

†   rnd:=round(a);

  trnc:=trunc(a);

†   if (abs(a)=-a) and (rnd=trnc) then entier:=trnc-1;

†   if (abs(a)=-a) and (rnd<trnc) then entier:=rnd;

†   if abs(a)=a then entier:=trnc;

end;

 

begin

†   assign(R,'D:\PASCAL\LOGDATA\PRIME27.TXT'); {* The output is to this file. *}

†   rewrite(R);

†   for n:=1 to 100 do

†   begin

†††     for k:=1 to 2*(entier(n*ln(n))+1) do

†††     begin

†††††       for j:=2 to k do

†††††       begin

        for s:=1 to entier(sqrt(j)) do

        begin

          Hs:=Hs+entier((j-1)/s)-entier(j/s);

†††††††         end;

†††††††         Ik:=Ik+entier((2+2*Hs)/j);

†††††††         Hs:=0;

†††††       end;

†††††       Gk:=k-1+Ik;

†††††       P1n:=P1n+(1-entier(Gk/n));

†††††       Ik:=0;

†††     end;

†††     Pn:=1+P1n;

†††     writeln(R,'n=',n);

†††     writeln(R,'Pn=',Pn);

   P1n:=0;

  end;

close(R);

end.

 

Fig. 3: The source code of PRIME27.PAS. PASCAL implementation of the formula of SebastiŠn MartŪn Ruiz published in 2002.8 The   function entier does the so in mathematical terms called floor function [x].

 

It is the n-formula of SebastiŠn MartŪn Ruiz published in 2002.8 You can calculate only the smaller primes in a reasonable time with that formula. For example the first 100 primes are calculated by PRIME27 in 13 minutes on my computer (AMD Athlon 700 MHz 128 Mb). Compare that with HBPRM2 (see the Index for downloading the source code) with does the same calculation but than by the simple method of trail divisions. The first 100 primes are thus calculated in less than one second! The other n-formula's are an even bigger burden on a nowadays computer because they use factorials (x!) which grow with n. So these formula's are only of fundamental and theoretically importance, they have no significance for example with cracking or generating keys for prime based encryption. To generate primes for this purpose you better rely on trail division, the sieve of Eratosthenes or even better the advanced field sieve methods. Nevertheless I personally believe that the prime n-formula's will be an important factor in proofing or falsifying the Riemann-hypothesis. So that is my next challenge to the scientific (mathematical) community, encouraged as I am that the former challenge was already fulfilled!

 

-o0o- Please also visit: The new Journal of Randomics site and the cumulated result of the site here

 

Notes & References:

1) Anonymous 'A prime case of chaos'

http://www.ams.org/featurecolumn/archive/prime-chaos.pdf

2) Walker J. 'HotBits: Genuine random numbers, generated by radioactive decay'

http://www.fourmilab.ch/hotbits/

3) Tipler F.J. 'The physics of immortality: Modern cosmology, God and the resurrection of the dead' Doubleday, New York (1994).

4) WOLFRAMRESEARCH 'Benford's law'

http://mathworld.wolfram.com/BenfordsLaw.html

5) Anonymous 'How many primes are there?'

http://primes.utm.edu/howmany.shtml

6) Walker J. 'Ent: A pseudorandom number sequence test program' webpage with an interactive chi square calculator

http://www.fourmilab.ch/random/

7) Van der GaliŽn J.G. ĎThe dawn of scienceí Scientia Araneae Totius Orbis 1.1. (2002)

http://www.satoconor.com

8) Ruiz M.S. 'Applications of Smarandache function, and prime and coprime functions'

http://www.gallup.unm.edu/~smarandache/SMRuiz-eBook.pdf

9) Wikipedia: The free encyclopedia 'Prime number'

http://en.wikipedia.org/wiki/Prime_number

 

Appendix

Table 1: The output of the PASCAL program PRIME9 for Nís up to 109.

 

Amount of prime numbers under 10=4

e(n) is the observed amount of prime numbers per digit

perc1= 0.0000000000E+00 e1=0

perc2= 2.5000000000E+01 e2=1

perc3= 2.5000000000E+01 e3=1

perc4= 0.0000000000E+00 e4=0

perc5= 2.5000000000E+01 e5=1

perc6= 0.0000000000E+00 e6=0

perc7= 2.5000000000E+01 e7=1

perc8= 0.0000000000E+00 e8=0

perc9= 0.0000000000E+00 e9=0

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=1

CHI-square= 5.0000000000E+00

 

Amount of prime numbers under 100=25

e(n) is the observed amount of prime numbers per digit

perc1= 1.6000000000E+01 e1=4

perc2= 1.2000000000E+01 e2=3

perc3= 1.2000000000E+01 e3=3

perc4= 1.2000000000E+01 e4=3

perc5= 1.2000000000E+01 e5=3

perc6= 8.0000000000E+00 e6=2

perc7= 1.6000000000E+01 e7=4

perc8= 8.0000000000E+00 e8=2

perc9= 4.0000000000E+00 e9=1

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=3

CHI-square= 2.6666666667E+00

 

Amount of prime numbers under 1000=168

e(n) is the observed amount of prime numbers per digit

perc1= 1.4880952381E+01 e1=25

perc2= 1.1309523810E+01 e2=19

perc3= 1.1309523810E+01 e3=19

perc4= 1.1904761905E+01 e4=20

perc5= 1.0119047619E+01 e5=17

perc6= 1.0714285714E+01 e6=18

perc7= 1.0714285714E+01 e7=18

perc8= 1.0119047619E+01 e8=17

perc9= 8.9285714286E+00 e9=15

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=19

CHI-square= 3.3157894737E+00

 

Amount of prime numbers under 10000=1229

e(n) is the observed amount of prime numbers per digit

perc1= 1.3018714402E+01 e1=160

perc2= 1.1879576892E+01 e2=146

perc3= 1.1310008137E+01 e3=139

perc4= 1.1310008137E+01 e4=139

perc5= 1.0659072417E+01 e5=131

perc6= 1.0984540277E+01 e6=135

perc7= 1.0170870627E+01 e7=125

perc8= 1.0333604557E+01 e8=127

perc9= 1.0333604557E+01 e9=127

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=137

CHI-square= 7.3138686131E+00

 

Amount of prime numbers under 100000=9592

e(n) is the observed amount of prime numbers per digit

perc1= 1.2437447873E+01 e1=1193

perc2= 1.1770225188E+01 e2=1129

perc3= 1.1436613845E+01 e3=1097

perc4= 1.1144703920E+01 e4=1069

perc5= 1.0998748957E+01 e5=1055

perc6= 1.0560884070E+01 e6=1013

perc7= 1.0706839033E+01 e7=1027

perc8= 1.0456630525E+01 e8=1003

perc9= 1.0487906589E+01 e9=1006

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=1066

CHI-square= 3.1039399625E+01

 

Amount of prime numbers under 1000000=78498

e(n) is the observed amount of prime numbers per digit

perc1= 1.2210502178E+01 e1=9585

perc2= 1.1646156590E+01 e2=9142

perc3= 1.1414303549E+01 e3=8960

perc4= 1.1142959056E+01 e4=8747

perc5= 1.0974801906E+01 e5=8615

perc6= 1.0774796810E+01 e6=8458

perc7= 1.0745496701E+01 e7=8435

perc8= 1.0606639660E+01 e8=8326

perc9= 1.0484343550E+01 e9=8230

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=8722

CHI-square= 1.7666039899E+02

 

Amount of prime numbers under 10000000=664579

e(n) is the observed amount of prime numbers per digit

perc1= 1.2040705469E+01 e1=80020

perc2= 1.1590044223E+01 e2=77025

perc3= 1.1328976691E+01 e3=75290

perc4= 1.1152022559E+01 e4=74114

perc5= 1.0977024552E+01 e5=72951

perc6= 1.0872597539E+01 e6=72257

perc7= 1.0768320997E+01 e7=71564

perc8= 1.0689173146E+01 e8=71038

perc9= 1.0581134824E+01 e9=70320

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=73842

CHI-square= 1.0729957341E+03

 

Amount of prime numbers under 100000000=5761455

e(n) is the observed amount of prime numbers per digit

perc1= 1.1907547659E+01 e1=686048

perc2= 1.1529674362E+01 e2=664277

perc3= 1.1300704423E+01 e3=651085

perc4= 1.1135971729E+01 e4=641594

perc5= 1.1002984489E+01 e5=633932

perc6= 1.0903599872E+01 e6=628206

perc7= 1.0811192659E+01 e7=622882

perc8= 1.0737044722E+01 e8=618610

perc9= 1.0671280085E+01 e9=614821

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=640162

CHI-square= 6.8661260665E+03

 

Amount of prime numbers under 1000000000=50847534

e(n) is the observed amount of prime numbers per digit

perc1= 1.1806924599E+01 e1=6003530

perc2= 1.1480723923E+01 e2=5837665

perc3= 1.1278985526E+01 e3=5735086

perc4= 1.1133548777E+01 e4=5661135

perc5= 1.1018760516E+01 e5=5602768

perc6= 1.0927637120E+01 e6=5556434

perc7= 1.0848372706E+01 e7=5516130

perc8= 1.0780554274E+01 e8=5481646

perc9= 1.0724492558E+01 e9=5453140

Total= 1.0000000000E+02

Expected amount of prime numbers per digit=5649726

CHI-square=4.6651487E+04 (Calculated by hand because longint is to small.)