All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Goldbach revisited (Posted on 2013-03-15) Difficulty: 4 of 5
1.How many distinct prime pairs sum up to 10000 ?
2.How many distinct prime pairs sum up to 100000000 ?

Provide exact answer to 1 and approximate answer to 2 .

The order of addends does not matter.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer aided solutions Comment 2 of 2 |

     10   while P<5000
     20      P=nxtprm(P)
     30      Diff=10000-P
     40      if prmdiv(Diff)=Diff then print P;Diff;"  ";:Ct=Ct+1
     45        :if Ct @ 5=0 then print
     50   wend
     60   print:print Ct

finds

     59  9941      71  9929     113  9887     149  9851     167  9833
    197  9803     233  9767     251  9749     257  9743     281  9719
    311  9689     449  9551     461  9539     467  9533     479  9521
    503  9497     509  9491     521  9479     563  9437     569  9431
    587  9413     659  9341     677  9323     719  9281     743  9257
    761  9239     773  9227     797  9203     827  9173     839  9161
    863  9137     941  9059     971  9029    1031  8969    1049  8951
   1151  8849    1163  8837    1181  8819    1193  8807    1217  8783
   1259  8741    1301  8699    1307  8693    1319  8681    1373  8627
   1427  8573    1487  8513    1499  8501    1553  8447    1571  8429
   1613  8387    1637  8363    1709  8291    1877  8123    1889  8111
   1907  8093    1913  8087    1931  8069    2063  7937    2081  7919
   2099  7901    2207  7793    2243  7757    2273  7727    2297  7703
   2309  7691    2351  7649    2357  7643    2393  7607    2411  7589
   2417  7583    2423  7577    2441  7559    2459  7541    2477  7523
   2543  7457    2549  7451    2693  7307    2753  7247    2789  7211
   2879  7121    2897  7103    2957  7043    2999  7001    3023  6977
   3041  6959    3083  6917    3089  6911    3137  6863    3167  6833
   3209  6791    3221  6779    3299  6701    3347  6653    3449  6551
   3527  6473    3671  6329    3677  6323    3701  6299    3779  6221
   3797  6203    3803  6197    3911  6089    3947  6053    3989  6011
   4013  5987    4019  5981    4073  5927    4133  5867    4139  5861
   4157  5843    4217  5783    4259  5741    4283  5717    4289  5711
   4349  5651    4409  5591    4481  5519    4493  5507    4517  5483
   4523  5477    4583  5417    4649  5351    4691  5309    4703  5297
   4721  5279    4919  5081

for a count of 127. Since order doesn't matter, only those with lower number first are shown and counted.

Approximation method:

The prime number theorem approximates the number of primes below a given number, n, as n / ln(n). For 100,000,000 this would be 100000000/18.42068 ~= 5428681. That also means that about 1/18.42 of the numbers under 100,000,000 are prime. Offhand, then, one would think if you subtracted a prime from 100,000,000 the probability that you'd get another prime would be 1/18.42 and the number of pairs, counting order separately would be 5428681/18.42 or about 294717. That counts both orders of a pair separately as the numerator included all primes, not just those smaller than 100000000/2, so you'd have to halve the number to discount order: 147358.

But how well does that method work when applied to the 10,000 version?

10000/ln(10000) implies about 1086 primes under 10000 and we'd expect 118 pairs counting both orders separately or 59 not considering order.

What went wrong?

As 10000 is even and all primes but the number 2 are odd, you're virtually guaranteed that the difference between the first prime chosen and 10000 is odd (not divisible by 2). You're also guaranteed that the complement of the first prime is not divisible by 5. So out of every 10 numbers in the range, 6 are ruled out automatically and the estimate needs to be multiplied by 10/4 or 5/2, making the estimate for the 10,000 version 59*5/2 ~= 148, in better agreement with the actual count of 127.

The same correction applies to the case of 100,000,000: 147358*5/2 = 368395.

Check:

 10   while P<50000000
 20      P=nxtprm(P)
 30      Diff=100000000-P
 40      if prmdiv(Diff)=Diff then print P;Diff;"  ";:Ct=Ct+1
 45        :if Ct @ 5=0 then print
 50   wend
 60   print:print Ct

finds the actual count is  291400.


  Posted by Charlie on 2013-03-15 15:43:03
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information