Strange behaviour of prime numbers

[pier4r]

(05-27-2019 01:41 PM)rprosperi Wrote:  I am frequently amazed and impressed with the enormous amounts of resources and effort folks dedicate to researching Primes, and meta-data about Primes, with no clear predetermined benefit of doing so. Not complaining, just curious why so many people are drawn to research in this area, and what goals they set pursuing such research.

Have any significant non-academic-only results come about as a result of Prime research that isn't well-known, or maybe widely-known, but apparently not by me?

I have a personal answer to this (dunno if it will get refuted in the future if I get more experiences).

Such explorations are challenging but still feasible. It is like "Oh I have this question and I know I need only to find a way to crunch the data, that is feasible to do but requires a bit of work on my side". Therefore they bring satisfaction as well as solving a chess puzzle, or a riddle, a crossword, a sudoku and so on. Only creating the algorithm to solve the problem and sharing the results is (or at least it feels) a bit more valuable.

Then if you think about it most of the topics are focused on well known "simple" problems (read: one can write a procedure relatively quickly). Primes, digits of Pi, digits of E, digits of square root of 2.

No one goes trying finding several thousands digits of, say, square root of 3109. Maybe someone did but there was no follow up. Without considering other more complicated topics in math, programming, logic and what not.

I see it as mostly recreational mathematics that keep the mind of the person sharp and may provide pointers for informative discussions.


PS: for chess lovers, have you tried lichess tactics puzzles? Well don't as otherwise they suck up your time. https://lichess.org/training

[Thomas Okken]

(05-27-2019 01:41 PM)rprosperi Wrote:  I am frequently amazed and impressed with the enormous amounts of resources and effort folks dedicate to researching Primes, and meta-data about Primes, with no clear predetermined benefit of doing so. Not complaining, just curious why so many people are drawn to research in this area, and what goals they set pursuing such research.

It just happens to be an inexhaustible topic. Take a look at the Riemann Hypothesis to get an idea of just how deep and bizarre the connections can get.

(05-27-2019 01:41 PM)rprosperi Wrote:  Have any significant non-academic-only results come about as a result of Prime research that isn't well-known, or maybe widely-known, but apparently not by me?

Public-key cryptography is based on algorithms that can generate large primes easily, while relying on the difficulty of factoring the products of two large primes. It may be the only practical application of abstract algebra that I've ever encountered, but it's a big one.

[ijabbott]

(05-27-2019 08:38 AM)fred_76 Wrote:  If we write [nm] to identify a couple of primes, the first ending by n followed by the second ending by m then :
- least frequent are the "double ending" 11, 33, 77, 99 with a % of occurence in the range of 17%.
- most frequent is 91 with an occurence of a bit less than 33%
- then 17, 13, 39 and 79 with about 30%
- and 19, 31, 37, 71, 73, 93, 97 between about 21% and 28%

The table for the 10 first million primes is as follows. It shows the proportion of primes ending by n, followed by a prime ending by m, to the number of primes ending by n :

Code:


nm    %
11    17.9%
13    30.2%
17    30.8%
19    21.1%
    
31    23.7%
33    16.9%
37    28.6%
39    30.8%
    
71    25.6%
73    27.3%
77    16.9%
79    30.3%
    
91    32.8%
93    25.6%
97    23.7%
99    17.8%

I wonder how much the results are perturbed by the larger gap between 3 and 7 (due to the missing digit 5)? It would be interesting to repeat the test for base 8 or base 16 where there are no gaps in candidate odd number last digit.

[ttw]

There is a lot known (most of which raises more questions) about the density of primes. Not much about correlations though that is interesting in itself.

Dirichlet's theorem states that the density of primes in arithmetic progressions is just what is expected. The density of primes is about Ln(n)/n and an arithmetic progression with the additive constant relatively prime to the multiplier: x(j)=k*j+a has density Ln(n)/(k*n).

https://en.wikipedia.org/wiki/Dirichlet%...ogressions

However there are funnies like Chebyshev's Bias which says that primes of the form 4*k+3 occur more often than those of 4*k+1 (although there are small regions where the other inequality happens, just enough that the overall densities are the same.) If the Riemann Hypothesis is true (strong form) then this can be proved. However (again), the excess doesn't happen "almost everywhere").

https://en.wikipedia.org/wiki/Chebyshev%27s_bias

A more intuitive discussion of prime behavior and why it's difficult: https://terrytao.wordpress.com/2009/09/2...spiracies/

The Green–Tao theorem is weird; it states that the sequence of primes contains arbitrarily long arithmetic progressions.

https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem

This is a rather technical paper on the subject: http://math.uchicago.edu/~may/REU2013/REUPapers/Jun.pdf
This paper also explains the difference between "natural density" and "analytic density" which interestingly applies to Benford's Law (actually discovered by Simon Newcomb).

[Gilles]

(05-26-2019 05:08 PM)Albert Chan Wrote:  Hi, pier4r

Tried it with Mathematica. Distribution looks similar within sub-ranges.

Code:

keys = {1, 3, 7, 9};
joinlastdigit[x_, y_] := Mod[x, 10]*10 + Mod[y, 10];
keys = Flatten[Table[joinlastdigit[keys[[i]], keys[[j]]], {i, 4}, {j, 4}]];

lastdigitdist[range_] := Block[{n, p, t},    (* distribution percentages *)
    n = Length[range];
    p = Map[Prime, range];
    t = Map[joinlastdigit[p[[#]], p[[#+1]]]&, Range[n-1]];
    0.1 * Round[1000 * Map[Count[t, #]&, keys]/n]];

keys → {11, 13, 17, 19, 31, 33, 37, 39, 71, 73, 77, 79, 91, 93, 97, 99}

lastdigitdist[Range[1, 1000000]]        → {4.3, 7.7, 7.9, 5.0, 5.8, 4.0, 7.3, 7.9, 6.4, 6.9, 4.0, 7.8, 8.5, 6.4, 5.8, 4.3}

I'm probably wrong somewhere (or dont understand how you calculate the %) but I dont find the same result with this program in newRPL. For the first million I get :

{ 4.09. 8.02. 8.34. 4.53. 5.59. 3.58. 7.41. 8.47. 6.46. 6.93. 3.66. 7.94. 8.85. 6.51. 5.58. 4.02. }

Code:

«
  2 0 9 IDN 0 *  → prev new stat
  «
    2
    WHILE NEXTPRIME DUP 1E6 < REPEAT
     DUP 0 0 DIGITS 'new' STO
     'stat' prev new 2 →LIST DUP2 GET 1 + PUT
     new 'prev' STO
    END
    stat DUP AXL ΣLIST  ΣLIST / 100 *
  »
 »

(the results are in an array 9x9)
I takes only 0.96s with the simulator for the first million, 85sec on a HP50g hdw.

10 millions takes only 15sec

Code:

[ 
  [ 4.26. 0. 7.77. 0. 0. 0. 8.02. 0. 4.94. ] 
  [ 0. 0. 0. 0. 0. 0. 0. 0. 0. ] 
  [ 5.79. 0. 3.9. 0. 0. 0. 7.32. 0. 8. ] 
  [ 0. 0. 0. 0. 0. 0. 0. 0. 0. ] 
  [ 0. 0. 0. 0. 0. 0. 0. 0. 0. ] 
  [ 0. 0. 0. 0. 0. 0. 0. 0. 0. ] 
  [ 6.42. 0. 6.89. 0. 0. 0. 3.9. 0. 7.8. ] 
  [ 0. 0. 0. 0. 0. 0. 0. 0. 0. ] 
  [ 8.52. 0. 6.45. 0. 0. 0. 5.76. 0. 4.24. ] 
]

[Albert Chan]

(05-27-2019 09:35 PM)Gilles Wrote:  I'm probably wrong somewhere (or dont understand how you calculate the %) but I dont find the same result with this program in newRPL. For the first million I get :

{ 4.09. 8.02. 8.34. 4.53. 5.59. 3.58. 7.41. 8.47. 6.46. 6.93. 3.66. 7.94. 8.85. 6.51. 5.58. 4.02. }

Hi, Gilles

I don't think your code counted 1 million primes, but only primes below 1 million.
In other words, only PrimePi[10^6] = 78498 primes.

Tried lastdigitdist[Range[78498]], and it matches above posted distribution.

[rprosperi]

(05-27-2019 04:42 PM)Thomas Okken Wrote:  Public-key cryptography is based on algorithms that can generate large primes easily, while relying on the difficulty of factoring the products of two large primes. It may be the only practical application of abstract algebra that I've ever encountered, but it's a big one.

Well, full disclosure I actually did know that one (from a past life) and I should have noted that exception. I imagine there are likely several others though; since research seems to be done by folks in lots of technical areas (not just mathematicians) I've wondered if there are applications/challenges in those other areas they are seeking to find answers to.

[Gilles]

(05-27-2019 10:53 PM)Albert Chan Wrote:  

(05-27-2019 09:35 PM)Gilles Wrote:  I'm probably wrong somewhere ...

Hi, Gilles

I don't think your code counted 1 million primes, but only primes below 1 million.
In other words, only PrimePi[10^6] = 78498 primes.

Tried lastdigitdist[Range[78498]], and it matches above posted distribution.

You are right Albert ! Code must be :

Code:

«
  1 2 0 9 IDN 0 *  →  nbp prev new stat
  «
    2
    WHILE NEXTPRIME 'nbp' INCR 1E6 < REPEAT
     DUP 0 0 DIGITS 'new' STO
     'stat' prev new 2 →LIST DUP2 GET 1 + PUT
     new 'prev' STO
    END
    stat nbp / 100 *
  »
»

Same resuts as yours in 28,5 sec on my PC

[fred_76]

The % I gave are calculated :

% = [Nb of primes ending by n followed by a prime ending by m] / [Nb of primes ending by n in the sample] x 100

What you did is :

% = [Nb of primes ending by n followed by a prime ending by m] / [Nb of primes in the sample] x 100

If I calculate as you for the first million primes (and not primes up to 1 millions), the result is very close to your's (in brackets) :

11 : 4.29% (4.3%)
13 : 7.748% (7.7%)
17 : 7.945% (7.9%)
19 : 5.02% (5.0%)
31 : 5.83% (5.8%)
33 : 3.97% (4.0%)
37 : 7.28% (7.3%)
39 : 7.94% (7.9%)
71 : 6.42% (6.4%)
73 : 6.86% (6.9%)
77 : 3.96% (4.0%)
79 : 7.76% (7.8%)
91 : 8.46% (8.5%)
93 : 6.44% (6.4%)
97 : 5.81% (5.8%)
99 : 4.28% (4.3%)

For the first 10 millions primes, with your method :
11 : 4.47%
13 : 7.56%
17 : 7.70%
19 : 5.27%
31 : 5.93%
33 : 4.22%
37 : 7.15%
39 : 7.70%
71 : 6.39%
73 : 6.82%
77 : 4.22%
79 : 7.57%
91 : 8.20%
93 : 6.40%
97 : 5.93%
99 : 4.46%


Fred

[Gilles]

Hi Fred!
I get exactly the same results as you both for 1 and 10 millions

[Gerson W. Barbosa]

(05-27-2019 05:10 PM)ijabbott Wrote:  I wonder how much the results are perturbed by the larger gap between 3 and 7 (due to the missing digit 5)? It would be interesting to repeat the test for base 8 or base 16 where there are no gaps in candidate odd number last digit.

The number base is irrelevant, according to this (YouTube) video (4m43s).

[Gilles]

I'm not expert of this, but I guess this could be explain by the fact that there are some links between "divisibilty" and digits of a number. The most obvious is that a number is divisible by 3 if the sum of its digits is divisible by 3.

Suppose a prime number composed like this : abc3
Of course, a+b+c+3 is not divisible by 3. Remains 1 or 2

The next number with 3 at the end is : ab(c+1)3 . And there is a probability of 50% that a+b+(c+1)+3 is divisible by 3. So the probability of ab(c+1)3 is a prime number decrease of 50%.

The "gap" between the digits is also important, I imagine

[ijabbott]

(05-31-2019 07:07 PM)Gilles Wrote:  I'm not expert of this, but I guess this could be explain by the fact that there are some links between "divisibilty" and digits of a number. The most obvious is that a number is divisible by 3 if the sum of its digits is divisible by 3.

Suppose a prime number composed like this : abc3
Of course, a+b+c+3 is not divisible by 3. Remains 1 or 2

The next number with 3 at the end is : ab(c+1)3 . And there is a probability of 50% that a+b+(c+1)+3 is divisible by 3. So the probability of ab(c+1)3 is a prime number decrease of 50%.

The "gap" between the digits is also important, I imagine

That's why I suggested trying base 8 or base 16, because the base is co-prime with all odd numbers.

[Wes Loewer]

(05-26-2019 10:51 AM)ijabbott Wrote:  There's an interesting pattern when the prime numbers are written in base 2. If a prime number ends with the digit 1, the next prime will always end with the same digit. Spooky!

There's an even more interesting pattern when you list out the Mersenne Prime Numbers in base 2.