A recent discovery, quoted from   Quantamagazine   (March 13, 2016):

     Two mathematicians have uncovered a simple, previously unnoticed property of 
     prime numbers — those numbers that are divisible only by 1 and themselves.     
     Prime numbers, it seems, have decided preferences about the final digits of    
     the primes that immediately follow them.  

and

     This conspiracy among prime numbers seems, at first glance, to violate a     
     longstanding assumption in number theory:  that prime numbers behave much    
     like random numbers. 

                            ─── (original authors from Stanford University):      
                            ─── Kannan Soundararajan  and  Robert Lemke Oliver    



The task is to check this assertion, modulo 10.

Lets call    i -> j    a transition if    i    is the last decimal digit of a prime, and    j    the last decimal digit of the following prime.



Task

Considering the first one million primes.   Count, for any pair of successive primes, the number of transitions    i -> j    and print them along with their relative frequency, sorted by    i .

You can see that, for a given    i ,   frequencies are not evenly distributed.



Observation

(Modulo 10),   primes whose last digit is   9   "prefer"   the digit   1   to the digit   9,   as its following prime.



Extra credit

Do the same for one hundred million primes.



Example for 10,000 primes

10000 first primes. Transitions prime % 10 → next-prime % 10.
1 → 1 count:        365 frequency: 3.65 %
1 → 3 count:        833 frequency: 8.33 %
1 → 7 count:        889 frequency: 8.89 %
1 → 9 count:        397 frequency: 3.97 %
2 → 3 count:          1 frequency: 0.01 %
3 → 1 count:        529 frequency: 5.29 %
3 → 3 count:        324 frequency: 3.24 %
3 → 5 count:          1 frequency: 0.01 %
3 → 7 count:        754 frequency: 7.54 %
3 → 9 count:        907 frequency: 9.07 %
5 → 7 count:          1 frequency: 0.01 %
7 → 1 count:        655 frequency: 6.55 %
7 → 3 count:        722 frequency: 7.22 %
7 → 7 count:        323 frequency: 3.23 %
7 → 9 count:        808 frequency: 8.08 %
9 → 1 count:        935 frequency: 9.35 %
9 → 3 count:        635 frequency: 6.35 %
9 → 7 count:        541 frequency: 5.41 %
9 → 9 count:        379 frequency: 3.79 % 



 
program primCons;
{$IFNDEF FPC}
  {$APPTYPE CONSOLE}
{$ENDIF}
const
  PrimeLimit =  2038074748 DIV 2;
type
  tLimit = 0..PrimeLimit;
  tCntTransition = array[0..9,0..9] of NativeInt;
  tCntTransRec = record
                   CTR_CntTrans:tCntTransition;
                   CTR_primCnt,
                   CTR_Limit : NativeInt;
                 end;
  tCntTransRecField = array[0..19] of tCntTransRec;
var
  primes: array [tLimit] of boolean;
  CntTransitions : tCntTransRecField;
 
procedure SieveSmall;
//sieve of eratosthenes with only odd numbers
var
  i,j,p: NativeInt;
Begin
  FillChar(primes[1],SizeOF(primes),chr(ord(true)));
  i := 1;
  p := 3;
  j := i*(i+1)*2;
  repeat
    IF (primes[i]) then
    begin
      p := i+i+1;
      repeat
        primes[j] := false;
        inc(j,p);
      until j > PrimeLimit;
    end;
    inc(i);
    j := i*(i+1)*2;//position of i*i
    IF PrimeLimit < j then
      BREAK;
  until false;
end;
 
procedure OutputTransitions(const Trs:tCntTransRecField);
var
  i,j,k,res,cnt: NativeInt;
  ThereWasOutput: boolean;
Begin
  cnt := 0;
  while Trs[cnt].CTR_primCnt > 0 do
    inc(cnt);
  dec(cnt);
  IF cnt < 0 then
    EXIT;
 
  write('PrimCnt ');
  For i := 0 to cnt do
    write(Trs[i].CTR_primCnt:i+7);
  writeln;
  For i := 0 to 9 do
  Begin
    ThereWasOutput := false;
    For j := 0 to 9 do
    Begin
      res := Trs[0].CTR_CntTrans[i,j];
      IF res > 0 then
      Begin
        ThereWasOutput := true;
        write('''',i,'''->''',j,'''');
        For k := 0 to cnt do
        Begin
          res := Trs[k].CTR_CntTrans[i,j];
          write(res/Trs[k].CTR_primCnt*100:k+6:k+2,'%');
        end;
        writeln;
      end;
    end;
    IF ThereWasOutput then
      writeln;
  end;
end;
 
var
  pCntTransOld,
  pCntTransNew  : ^tCntTransRec;
  i,primCnt,lmt : NativeInt;
  prvChr,
  nxtChr : NativeInt;
Begin
  SieveSmall;
  pCntTransOld := @CntTransitions[0].CTR_CntTrans;
 
 
  pCntTransOld^.CTR_CntTrans[2,3]:= 1;
  lmt := 10*1000;
 
  //starting at 2 *2+1 => 5
  primCnt := 2; // the prime 2,3
  prvChr := 3;
  nxtChr  := prvChr;
  for i:= 2 to PrimeLimit do
  Begin
    inc(nxtChr,2);
    if nxtChr >= 10 then nxtChr := 1;
    IF primes[i] then
    Begin
      inc(pCntTransOld^.CTR_CntTrans[prvChr][nxtChr]);
      inc(primCnt);
      prvchr := nxtChr;
      IF primCnt >= lmt then
      Begin
        with pCntTransOld^ do Begin
          CTR_Limit := i;
          CTR_primCnt := primCnt;
        end;
        pCntTransNew := pCntTransOld;
        inc(pCntTransNew);
        pCntTransNew^:= pCntTransOld^;
        pCntTransOld := pCntTransNew;
        lmt := lmt*10;
      end;
    end;
  end;
  pCntTransOld^.CTR_primCnt := 0;
  OutputTransitions(CntTransitions);
end.
 