Thread Rating:

Poll

1 vote (100%)
No votes (0%)
No votes (0%)
1 vote (100%)
No votes (0%)
No votes (0%)
No votes (0%)
No votes (0%)
No votes (0%)
No votes (0%)

1 member has voted

Wizard
Administrator
Wizard
  • Threads: 1491
  • Posts: 26435
Joined: Oct 14, 2009
September 8th, 2021 at 10:32:52 PM permalink
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?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
gordonm888
Administrator
gordonm888
  • Threads: 60
  • Posts: 5005
Joined: Feb 18, 2015
September 8th, 2021 at 11:51:38 PM permalink
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 >1025 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.
So many better men, a few of them friends, are dead. And a thousand thousand slimy things live on, and so do I.
Mission146
Mission146
  • Threads: 142
  • Posts: 16832
Joined: May 15, 2012
September 9th, 2021 at 8:33:00 AM permalink
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.
https://wizardofvegas.com/forum/off-topic/gripes/11182-pet-peeves/120/#post815219
billryan
billryan
  • Threads: 240
  • Posts: 16282
Joined: Nov 2, 2009
Thanked by
Mission146
September 9th, 2021 at 8:36:01 AM permalink
Kool punk rock band name, as well.
The difference between fiction and reality is that fiction is supposed to make sense.
Dieter
Administrator
Dieter
  • Threads: 16
  • Posts: 5478
Joined: Jul 23, 2014
Thanked by
Mission146
September 9th, 2021 at 10:52:02 AM permalink
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.
    May the cards fall in your favor.
    Wizard
    Administrator
    Wizard
    • Threads: 1491
    • Posts: 26435
    Joined: Oct 14, 2009
    September 9th, 2021 at 11:11:18 AM permalink
    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.
    "For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
    joedol
    joedol
    • Threads: 5
    • Posts: 76
    Joined: Mar 7, 2019
    September 9th, 2021 at 11:23:08 AM permalink
    Ya, what he said.
    • Jump to: