Randomness of prime numbers

Randomness of prime numbers: Although the prime numbers will never end with the odd digit 5 the Chi-square with 3 degrees of freedom for the remaining odd last digits 1, 3, 7 and 9 indicates that according to this test the primes are truly random.

 

Copyright & Disclaimer

 

 

 SATOCONOR.COM

J.G. van der Galiën, M. Winer  ‘Last  Digit Distribution of Prime Numbers’ 5.3. (2006)

Communication to the editor

SATOCONOR.COM Journal of RANDOMICS

 

 

Last Digit Distribution of the Prime Numbers

Are the prime numbers randomly distributed? Part 2

By Johan Gerard van der Galiën (M.Sc.) and Martin Winer4

For comments: galien8@zonnet.nl

Version 1.0 March 31, 2006

 

HOME of SATOCONOR.COM

 

Aside from 2 and 5 there are no even primes or primes ending in the digit 5.  This is a side effect of the base 10 representation.  As a result all other primes, after 2 and 5 will end in the digits 1,3,7, and 9.

A previous paper examined the leading digit of the primes and discovered that there were more 1 prefixed primes than 3 prefixed primes, and so on for more 3 prefixed primes being more plentiful than 7 prefixed which were, in turn, more plentiful than 9 prefixed primes. This observation correlates well with the well known distribution of primes given by x/log(x).

The next question is: are the primes random when looking at the trailing digit? The Chi-square Goodness-Of-Fit with three degrees of freedom (for the remaining 1, 3, 7 and 9 last digit distribution) tends to become always below the 5% probability limit as the tested natural number range increases. In other words: Formally the fit is too good to be true random! And there is almost no spreading in the last digit distribution as expressed by the Chi-square. Only on average 1 in 20 measurements the Chi-square should be below 5% probability for a true random source. This can be explained by the fact that the total prime number space is tested under certain limits (= natural numbers 102, 103, 104, 105, 106, 107, 108 and 109).

The Chi-square 5% and 95% criteria would only work if relative small random samples (<= 167 primes) were drawn from these (total) prime number spaces. Nevertheless the Chi-square gives an indication of the deviation from the expected values, which becomes very small indeed, if the limit is raised. Or in other words: Despite the too low Chi-square, the prime numbers still can be regarded, according to this test, as randomly distributed.

 

All primes except 2 are odd. Since the last digit of all odd numbers are themselves odd. Intuitively one would say that all primes should have 1, 3, 5, 7 or 9 as last digit, and if the primes were randomly distributed among the odds the Chi-square of the last digit distribution with four degrees of freedom should be on average 9 times out of 10 independent measurements between the 5% and 95% probability.

The research in this paper is a follow-up of earlier work done on the randomness of prime numbers by the first digit distribution.1 The idea for the research of this paper was that maybe one should not look at the first digits, because of the conjecture of Gauss which shows that they have a pi(x) ≈ x/log(x) = x/ln(x) distribution,3 but one should look at the last digits of the primes. We conducted the research with a simple C program (Code 1). Doing so we discovered that the prime numbers never end in 5, except the third prime 5 of course but since it is a single digit that does formally not end in 5. In other words the multi-digit primes.

 

//copyright (c) 2006 Johan Gerard van der Galien, galien8@zonnet.nl

 

#pragma hdrstop

#include <condefs.h>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

//---------------------------------------------------------------------------

#pragma argsused

int main(int argc, char **argv)

{

       unsigned long int I,J,K1,K3,K5,K7,K9,Prime,Exp,Limit=1000000000;

       char str1[10];

       FILE *logfile;

       double h1,h3,h7,h9,CHI;

 

       logfile=fopen("LastDigit1LogFile2.TXT","a");

 

       K1=0;

       K3=0;

       K5=0;

       K7=0;

       K9=0;

       Prime=0;

 

        for(I=3;I<Limit;I+=2)

        {

            for(J=2;J<=(unsigned long int)sqrt(I);J++)

            {

                if(I%J==0) goto LOOP1;

            }

            Prime++;

            itoa(I,str1,10);

            if(str1[strlen(str1)-1]=='1') K1++;

            if(str1[strlen(str1)-1]=='3') K3++;

            if(str1[strlen(str1)-1]=='5') K5++;

            if(str1[strlen(str1)-1]=='7') K7++;

            if(str1[strlen(str1)-1]=='9') K9++;

            LOOP1:

 

        }

        Exp=(K1+K3+K7+K9)/4;

        h1=(double)((K1-Exp)*(K1-Exp))/Exp;

        h3=(double)((K3-Exp)*(K3-Exp))/Exp;

        h7=(double)((K7-Exp)*(K7-Exp))/Exp;

        h9=(double)((K9-Exp)*(K9-Exp))/Exp;

        CHI=h1+h3+h7+h9;

        fprintf(logfile,"\n");

        fprintf(logfile,"Limit = %u\n",Limit);

        fprintf(logfile,"Primes with last digit 1 = %u\n",K1);

        fprintf(logfile,"Primes with last digit 3 = %u\n",K3);

        fprintf(logfile,"Primes with last digit 5 = %u\n",K5);

        fprintf(logfile,"Primes with last digit 7 = %u\n",K7);

        fprintf(logfile,"Primes with last digit 9 = %u\n",K9);

        fprintf(logfile,"Primes of all last digits = %u\n",K1+K3+K5+K7+K9);

        fprintf(logfile,"CHI-square three degrees digits 1,3,7,9 = %f\n",CHI);

        fprintf(logfile,"CHI-square three degrees  5%% = 0.35\n");

        fprintf(logfile,"CHI-square three degrees 95%% = 7.81\n");

        fclose(logfile);

        return 0;

}

 

Code 1: The full program with Chi-square measurement.

 

An explanation for the 5-paradox is the fact that this is a consequence of the prime factorization of the number base. 10 = 2*5 So 2 will divide all 2, 4 (2*2), 6 (2*3) and 8 (2*2*2) ending numbers and 5 will divide all 5 ending numbers. Then these numbers can of course never be prime! Then there only remains 1, 3, 7 and 9 as potential candidates for the last digit of the primes. There are of course also composites possible with those last digits.

 

Because of this mathematical fact one should look at only the last digits 1, 3, 7 and 9 with the Chi-square Goodness-Of-Fit Test with three degrees of freedom to see if the primes are randomly distributed among the odd numbers. (Log 1)

 

Limit = 100

Primes with last digit 1 = 5

Primes with last digit 3 = 7

Primes with last digit 5 = 1

Primes with last digit 7 = 6

Primes with last digit 9 = 5

Primes of all last digits = 24

CHI-square three degrees digits 1,3,7,9 = 1.000000

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 1000

Primes with last digit 1 = 40

Primes with last digit 3 = 42

Primes with last digit 5 = 1

Primes with last digit 7 = 46

Primes with last digit 9 = 38

Primes of all last digits = 167

CHI-square three degrees digits 1,3,7,9 = 0.878049

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 10000

Primes with last digit 1 = 306

Primes with last digit 3 = 310

Primes with last digit 5 = 1

Primes with last digit 7 = 308

Primes with last digit 9 = 303

Primes of all last digits = 1228

CHI-square three degrees digits 1,3,7,9 = 0.094771

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 100000

Primes with last digit 1 = 2387

Primes with last digit 3 = 2402

Primes with last digit 5 = 1

Primes with last digit 7 = 2411

Primes with last digit 9 = 2390

Primes of all last digits = 9591

CHI-square three degrees digits 1,3,7,9 = 0.154360

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 1000000

Primes with last digit 1 = 19617

Primes with last digit 3 = 19665

Primes with last digit 5 = 1

Primes with last digit 7 = 19621

Primes with last digit 9 = 19593

Primes of all last digits = 78497

CHI-square three degrees digits 1,3,7,9 = 0.137587

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 10000000

Primes with last digit 1 = 166104

Primes with last digit 3 = 166230

Primes with last digit 5 = 1

Primes with last digit 7 = 166211

Primes with last digit 9 = 166032

Primes of all last digits = 664578

CHI-square three degrees digits 1,3,7,9 = 0.156665

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 100000000

Primes with last digit 1 = 1440298

Primes with last digit 3 = 1440474

Primes with last digit 5 = 1

Primes with last digit 7 = 1440495

Primes with last digit 9 = 1440186

Primes of all last digits = 5761454

CHI-square three degrees digits 1,3,7,9 = 0.045335

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Limit = 1000000000

Primes with last digit 1 = 12711386

Primes with last digit 3 = 12712499

Primes with last digit 5 = 1

Primes with last digit 7 = 12712314

Primes with last digit 9 = 12711333

Primes of all last digits = 50847533

CHI-square three degrees digits 1,3,7,9 = 0.087692

CHI-square three degrees  5% = 0.35

CHI-square three degrees 95% = 7.81

 

Log 1: The results of the Chi-square with four degrees of freedom. The limit means that all odd primes up to that number where tested. The ‘Primes of all last digits =’ figures are only of the odd primes, 2 excluded.

 

Except 102 and 103 the Chi-squares up to 109 in Log 1 are too low to be from a truly random source. (Below 5% probability.) On average only 1 measurement out of 20 should be below the 5% criterion. But here 6 out of 8 are below. This means that the fit according to the Chi-square is too good to be true. But the values of the Chi-square must always be taken with a grain of salt. Because:

This means for this particular case that the Chi-square 5% and 95% criteria would only work if relative small random samples were drawn from the (total) prime number spaces. In this case the sample size should be around <=167, because then the Chi-square is still within the 5% and 95% probability. Nevertheless the Chi-square gives an indication of the deviation from the expected values, which becomes very small indeed, if the limit is raised. Or in other words: Despite the too low Chi-square, the prime numbers still can be regarded, according to this test, as randomly distributed. A consequence of this research is that it should be possible to base a new kind of randomness test by picking 167 prime numbers at random from stored in a file by a (P)RNG and do the Chi-square with three degrees of freedom on the obtained last digit distribution. Do this test a 1000 times and calculate the Kolmogorov-Smirnoff (KS) value of the p-values distribution. But this is research for a new paper.

 

-o0o-

 

References& Notes:

1) Van der Galiën J.G. ‘Are the prime numbers randomly distributed?’ Scientia Araneae Totius Orbis 1.2. (2002)

http://www.satoconor.com

2) Scott P.D., Fasli M. 'Benford's law: An empirical investigation and a novel explanation' CSM Technical Report 349

http://cswww.essex.ac.uk/technicalreports/2001/CSM-349.pdf

3) Caldwell C. ‘How many primes are there?’ The Prime Pages

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

4) Winer M. ‘Primes: Randomness and twin prime proof’

http://www.rankyouragent.com/primes/primes.htm