Probability n is prime

One of my favorite YouTubers, right up there with Hannah Minx, is Matt Parker of the Stand Up Maths YouTube channel. I can forgive him, at least I think I can, for the "maths." It still makes the hair on the back of my neck stand up.

He addresses the probability that any given large number, n, is prime in this video. Start around the 4:40 point.


Direct: https://youtu.be/SMsTXQYgbiQ

Here he says, I would say very accurately, that the probability of a large number, let's call it n, being prime is 1/log(n). Let me pause and say that if the base of the log(x) function is not stated, assume it's e. Yes, I know there is ln(x) for that, but it's still conventional in advanced math to assume e, unless otherwise stated.

The following table shows the range of a span of a million primes. For example, the first line shows the first million primes range from 2 to 15,485,863.

Prime order	First	Last	Actual Probability	Estimated Probability
1 to 1000000	2	15,485,863	0.064575	0.063043
1000001 to 2000000	15485867	32,452,843	0.058938	0.058850
2000001 to 3000000	32452867	49,979,687	0.057055	0.057031
3000001 to 4000000	49979693	67,867,967	0.055903	0.055892
4000001 to 5000000	67867979	86,028,121	0.055066	0.055070
5000001 to 6000000	86028157	104,395,301	0.054445	0.054432
6000001 to 7000000	104395303	122,949,823	0.053895	0.053912
7000001 to 8000000	122949829	141,650,939	0.053473	0.053474
8000001 to 9000000	141650963	160,481,183	0.053106	0.053098
9000001 to 10000000	160481219	179,424,673	0.052789	0.052768
10000001 to 11000000	179424691	198,491,317	0.052448	0.052474
11000001 to 12000000	198491329	217,645,177	0.052209	0.052210
12000001 to 13000000	217645199	236,887,691	0.051968	0.051971
13000001 to 14000000	236887699	256,203,161	0.051772	0.051752
14000001 to 15000000	256203221	275,604,541	0.051543	0.051550

Source: https://www.utm.edu/staff/caldwell/primes/millions/

The actual probability column shows the ratio of primes in that range (always a million) to the difference between the largest and smallest prime in that range.

The estimated probability is the probability that a number in that range will be prime. To be specific, it is the inverse of the log of the half way point in that range. For example, the probability a number about half way between 256203221 and 275,604,541 (which equals 265,903,881) is prime 1/log(265,903,881). You can see the estimates match the actual probabilities very closely. It is amazing and beautiful how closely, but let's not get emotional.

Matt goes onto say that you can estimate the number of primes under n by taking the produce of n and log(n). Pause. It's common knowledge that as numbers get bigger, the average space between primes also gets bigger. This is a major point of the video in question. So, shouldn't the number of primes under n be the integral of f(x)=1/ln(x)? Matt says it is n/log(n). Wouldn't that be the number of primes in a range around n? Since primes are closer together as n gets closer to 0, wouldn't n/log(n) underestimate the number of primes?

The following table looks at the number of primes under n, the n/ln(n) estimate and the ratio of the estimate to the actual number. Let me offer the usual apologies that Excel can handle only about 15 significant digits of accuracy.

n	Primes	Matt Estimate	Ratio
10	4	4.34	1.085736
100	25	21.71	0.868589
1,000	168	144.76	0.861695
10,000	1,229	1,085.74	0.883431
100,000	9,592	8,685.89	0.905535
1,000,000	78,498	72,382.41	0.922092
10,000,000	664,579	620,420.69	0.933554
100,000,000	5,761,455	5,428,681.02	0.942241
1,000,000,000	50,847,534	48,254,942.43	0.949012
10,000,000,000	455,052,511	434,294,481.90	0.954383
100,000,000,000	4,118,054,813	3,948,131,653.67	0.958737
1,000,000,000,000	37,607,912,018	36,191,206,825.27	0.962330
10,000,000,000,000	346,065,536,839	334,072,678,387.12	0.965345
100,000,000,000,000	3,204,941,750,802	3,102,103,442,166.08	0.967913
1,000,000,000,000,000	29,844,570,422,669	28,952,965,460,216.80	0.970125
10,000,000,000,000,000	279,238,341,033,925	271,434,051,189,532.00	0.972052
100,000,000,000,000,000	2,623,557,157,654,230	2,554,673,422,960,300.00	0.973744
1,000,000,000,000,000,000	24,739,954,287,740,800	24,127,471,216,847,300.00	0.975243
10,000,000,000,000,000,000	234,057,667,276,344,000	228,576,043,106,975,000.00	0.976580
100,000,000,000,000,000,000	2,220,819,602,560,910,000	2,171,472,409,516,260,000.00	0.977780
1,000,000,000,000,000,000,000	21,127,269,486,018,700,000	20,680,689,614,440,600,000.00	0.978862
10,000,000,000,000,000,000,000	201,467,286,689,315,000,000	197,406,582,683,296,000,000.00	0.979844
100,000,000,000,000,000,000,000	1,925,320,391,606,800,000,000	1,888,236,877,840,230,000,000.00	0.980739
1,000,000,000,000,000,000,000,000	18,435,599,767,349,200,000,000	18,095,603,412,635,500,000,000.00	0.981558
10,000,000,000,000,000,000,000,000	176,846,309,399,143,000,000,000	173,717,792,761,301,000,000,000.00	0.982309

Source: https://primes.utm.edu/howmany.html

You can see that the estimates of the number of primes under n is not so good.

If the estimate of the probability of n being prime is so much better, why not integrate 1/ln(x) to get the number of primes under n?

Simple and frustrating answer -- you can't integrate 1/ln(x). Those familiar with the Cauchy Euler equation I'm sure can feel my pain.

It turns out there is a better estimate for the number of primes under n: f(n)=n/(ln(n)-1). The following table shows the actual and modified estimate for the number of primes number n using this formula. As you can see, it is much more accurate.

n	Primes	Modified Estimate	Ratio
10	4	7.68	1.919260
100	25	27.74	1.109518
1,000	168	169.27	1.007554
10,000	1,229	1,217.98	0.991030
100,000	9,592	9,512.10	0.991670
1,000,000	78,498	78,030.45	0.994044
10,000,000	664,579	661,458.97	0.995305
100,000,000	5,761,455	5,740,303.81	0.996329
1,000,000,000	50,847,534	50,701,542.45	0.997129
10,000,000,000	455,052,511	454,011,971.29	0.997713
100,000,000,000	4,118,054,813	4,110,416,300.73	0.998145
1,000,000,000,000	37,607,912,018	37,550,193,649.99	0.998465
10,000,000,000,000	346,065,536,839	345,618,860,220.62	0.998709
100,000,000,000,000	3,204,941,750,802	3,201,414,635,780.64	0.998899
1,000,000,000,000,000	29,844,570,422,669	29,816,233,849,000.70	0.999051
10,000,000,000,000,000	279,238,341,033,925	279,007,258,230,820.00	0.999172
100,000,000,000,000,000	2,623,557,157,654,230	2,621,647,966,812,030.00	0.999272
1,000,000,000,000,000,000	24,739,954,287,740,800	24,723,998,785,920,000.00	0.999355
10,000,000,000,000,000,000	234,057,667,276,344,000	233,922,961,602,470,000.00	0.999424
100,000,000,000,000,000,000	2,220,819,602,560,910,000	2,219,671,974,013,730,000.00	0.999483
1,000,000,000,000,000,000,000	21,127,269,486,018,700,000	21,117,412,262,910,000,000.00	0.999533
10,000,000,000,000,000,000,000	201,467,286,689,315,000,000	201,381,995,844,660,000,000.00	0.999577
100,000,000,000,000,000,000,000	1,925,320,391,606,800,000,000	1,924,577,459,166,810,000,000.00	0.999614
1,000,000,000,000,000,000,000,000	18,435,599,767,349,200,000,000	18,429,088,896,563,900,000,000.00	0.999647
10,000,000,000,000,000,000,000,000	176,846,309,399,143,000,000,000	176,788,931,049,964,000,000,000.00	0.999676

If we take the derivative of f(n)=n/(ln(n)-1), we should get another good estimate for the number of number of primes under n. This derivative is (ln(n)-2)/(ln(n)-1)^2.

I will stop here by saying, extremely respectfully, that I think Matt was a little quick to give the estimate for the number of primes number under n as n/ln(n). It is not a very good estimate for the number of primes under n, but rather the ratio of primes you would find in a range around n to the size of the range itself.

The question for the poll is what do you think about this topic?

First of all, I love almost any thread that is about primes -or almost any topic in number theory.

Of course, starting with Gauss, the frequency/density of primes as n increases (the so-called Prime Number Theorem) has always been one of the most central topics of number theory. I've read several book chapters on this subject. So, other than Matt's misstatements, most of this was familiar to me. But I enjoyed it anyway.

Wikipedia and other sites have tables of the number of primes per decade up to >10²⁵ with all the digits shown.

BTW, I sometime store numbers greater than 15 digits as text in an Excel cell, and perform any needed number crunching using the Wizard calculator (the 254 digit calculator that JB wrote for you.) Yeah, it defeats the purpose of having a spreadsheet, but it allows me to store very large numbers to more than 15 digits on Excel spreadsheets - which is useful because Excel is how I organize and display my math analyses and attempts at original research.

Matt Parker is from the UK, pursuant to their grammatical rules, math can be pluralized to, 'Maths.'

Think of it this way: Geometry is a math, Algebra is a math, and together, they are maths.

Kool punk rock band name, as well.

Quote: Mission146

Matt Parker is from the UK, pursuant to their grammatical rules, math can be pluralized to, 'Maths.'

Think of it this way: Geometry is a math, Algebra is a math, and together, they are maths.

link to original post

I don't think I've ever studied 'mathematic'. Maths is just fine by me.

edit: it's always been mathematics.

Quote: Wizard

Simple and frustrating answer -- you can't integrate 1/ln(x).

I was thinking on my unicycle ride this morning that you don't need to integrate 1/ln(n) to get the probability of a number around the nth prime being prime.

f(n)=ln(n) is an estimator everybody respects for the average distance between primes around the nth prime.

If we integrate that, we should get an estimate for the nth prime.

This is easy to integrate. Recall integration by parts: The integral of u*dv = uv - integral of vdu.

Let:
u=ln(n)
du=1/n
v=n
dv=1

So the integral of ln(n)*1 = n*ln(n) - integral of (n*(1/n)) = n*ln(n) - n = n*(ln(n)-1)

I'm not sure if there is anything practical about this formula, which is the sum of the average distance between primes for all integers up to n.

Dividing this number by n, which gives ln(n)-1, gives the average distance between primes for all integers up to n.

If we divide n by this average distance between primes, we get 1/(ln(n)-1), which is the estimates primes under n.

Example:
n = 275,604,541
n*(ln(n) - 1) = 5,080,625,730 = sum of average distances between primes from 2 to n. I know of know practical use for this alone.
ln(n)-1 = 18.434478 = average distance between primes between 2 and n.
1/(ln(n)-1) = 0.054246 = ​Probability a random number between 2 and n is prime.
n/(ln(n)-1) = 14,950,494 = Estimated number of primes under n.
Actual primes under n = 15,000,000.

So, there is a connection between ln(n) and n/(ln(n)-1). One is based on the derivative of the other.

Ya, what he said.