Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Hi All

I am switching to this thread because I think this tread is more appropriate for posts dealing with primes. I have previously posted on the "help me" thread.

I am a small time prime hobbyist and have previously posted two "algorithms" that I have developed roughly on my own devices, although I have learned of similar formulations by other researchers/mathematicians, so my stuff might be "copies" or inferior models of what have already been done. I will post my first two "algorithms posted elsewhere on this site for information and comment/criticism!

#1

The 1st algorithm is a variation on the Sieve of Eratosthenes, but actually not a real sieve, but rather a combination of sieve and modulo operations. I discovered recently that there are similar sieves out there (e.g by David Turner of St Andrews University and others -See Wikipedia) so not too sure about the uniqueness of this algorithm therefore. However I did develop the sieve on my own, and I suspect it would be slightly different (and perhaps inferior) to the others. It involves the following; (#1) Take number line of positive integers, 1,2,3....... (#2) strike out all multiples of 2 leaving odd numbers (#3) Identify/mark "3" as a (new) prime number since "3" is not divisible by any positive integer (excluding "1") smaller than itself without leaving a remainder. Calculate square of the newly identified prime (9 in this case). For all odd numbers between 3 and 9 divide by the first prime "2" -all primes less that square root of 9,....nothing to eliminate since 4, 6 & 8 were already eliminated, leaving 5 & 7 as new primes. Now take next prime namely "5". Square of this prime is "25" Now divide all the (odd) numbers remaining on the number line between 9 & 25, by all the identified primes less than "5", namely "2" & "3" . "2" can actually be dropped since all the even numbers had already been eliminated from the number line. This operation eliminates "15,18 & 21", identifying 11,13,17,19 & 23 as primes. (#4) Now do the same for the odd numbers between "25" and the next prime (7=49), dividing with the identified primes less than the square root of (49=7), repeating this operation step by step. The beauty of this operation/algorith is that it identifies primes well ahead of the primes being used in the "sector" being appraised.

#2

My second algorithm is much more curious. We all know that the seemingly random distribution of primes have been a source of amazement to mathematicians for centuries, making it impossible to predict accurately a pattern or the next prime number. However, I have discovered that adding primes together in a particular way (in fact the summing operation of primes seem to produce many solid patterns)-namely consecutive sum of primes produces very REGULAR curves (with coefficients of determination(R^2) of "1" or close to "1"), using the regularity of the obtained curve to "predict" the next prime. This I can do to an accuracy which appear to be an improvement of the estimation provided by the Prime Number Theorum (PNT), and the curve functions anywhere in a series of prime numbers as opposed to the PNT which is more accurate as it approaches infinity. One of the summations is like this (consecutive sum); Add the first two together. Then to the sum add the next prime. To this sum add the next prime number and so on....(p+p), (p+p+p),(p+p+p+p).....This produces a curve of almost perfect slope, whereby it is possible to the predict the NEXT prime by using a trend line or the polynomial equation of the formula. If this curve is true one could potentially predict primes or the location of primes to great numbers. Although I tested the series of consecutive primes in the "Series Encylopedia(OEIS)" it exists, but graphing this series to determine prime numbers has not been done before I think.

I would appreciate further comment.

Cipolla formula produces 1217 & 1224 with big O (if my calc's are correct). The actual value for 241th prime is 1523.

The polynomial curve (graphic algorithm) is giving +-1500 (vs 1523) by eye-ball.

This is very encouraging.

I am going to try to formalize the algorithm a bit more.

zetafunc wrote:

There are also other formulae for the nth prime, outside of PNT. For instance, Cipolla showed in 1902 that:

and this has since been improved by other authors, e.g. Dusart.

In the formula do I read log n -1 or log (n-1)? For the big O notation term...do I ignore this term for relatively small numbers?

What does this formala produce at the 240th prime?

I shall give it a bash, but I think that you might be able to calculate quicker.

The PNT theorem would be surely the standard to compare any other formula for the prediction of prime numbers against?

So it would be critical to calculate what the PNT ( n log n) would give at given points along the prime number line against any competing recipe.

What does the equivalent PNT formula give at this point? It was shown before in this tread that the PNT is more inaccurate in this range.

The new predicted number is not far away from the real value...in fact much closer than you would get by pure guessing!!!!

I get 168102 for the actual next term in the series, difference of only 57 for predicted term= 0.338098345% That seems a good forecast?

I am getting a bit electrified!

PREDICTED PRIME 240th TERM .............. 1531 vs 1511(actual)

The primes around (1511) is 1493,1499---1523,1531

EUREKA??????????????????????

Thanx!

That's not to bad! for 6th order...that is an error of 0.041428752% for 240th term!!!

What about the 241th term!!!!!!!!!!!!!!!!!!!!

Does fame and fortune beckon us?

Any body has any information about this....an improved algorithm using Sieve of Eratosthenes by Professor Helfgott (a Peruvian mathematician from France's National Centre for Scientific Research and the University of Göttingen in Germany? See link below

http://www.sciencealert.com/images/articles/processed/SieveofEratosthenes_web_1024.jpg

Yes that would be good if you could.

I am a bit perplexed however.

If I try to analyse your polynomial evaluations and I test the information with respect to validity, I come up with the following situation

For the set of data that you have analysed (239 terms) the polynomial holds 100% true....now reduce that subset by 1...this new sub set, call it subset b, should still holds true since it is part of a true set a.

Now if we take this subset b we should be able to prove that it holds true for nth term +1, since we know that that is the case...this would seem to indicate that the set is indeed polynomic unless the terms in the original "confined" set is not truely polynomial in the first place?

Why would Excell return a R^2 of 1.0000 for the 6th order polynomial of the curve of the data? Am I missing something, maybe a hidden force pattern in any summation of data. However, if I try to change any term by small units, then the R^2 value reacts very quickly.

Rgds

Hi Bobbym

Not sure where we are missing each other. When I generate an Excel curve with this data (up to 239th term) I get a trend line equation of

y=3.2759 x^2 - 116.67 x + 1763.3 (R^2=0.999)

Predicting the 240th prime I get a sum of 161002 (vs actual of 165048)...error of 2.45%, giving predicted prime near 1452 vs actual 1511, giving a location error of 4.2%

Prime Number Theory (PNT) -240th prime

~n log n gives prime value of 1315 vs actual of 1511 and location ERROR of 16.7%. (Correction factor not considered)

My problem is that the Excel graph equation for the 6th-order polynomial does not give the expected improved accuracy compared to the 2nd order polynomial, although the coefficient of determination (R^2) has improved to 1.00000

Thanx!

Could you just have a look a bit higher up the curve, as the slope at the beginning of the curve is at its steepest...remember even PNT has this problem of becoming more accurate only at infinity.

Is that possible?

Correct....the best fit you can do, so that we could test the predictive strength of such a curve/equation to predict the location and value of sums of primes and therefore the primes as well.

I need an equation for the first set of data listed.

Please find an equation for the resultant curve to the highest degree of accuracy that you can within your means.

Thx

Was mathematics invented or discovered....an application or a principle. I think a bit of both. Math only exists within consciousness...no consciousness no math! and yes other animals do have degrees of consciousness as well and some perhaps much more.

The problem with mathematics is that it is inherently contradictory/paradoxical.

Consider this, before we can think about something like e.g a math problem....we need time, say 1 second. But 1 second is composed of an infinite amount of fractions of a second. So before we can pass the threshold of 1 second, we first have to pass all these smaller fractions of time....this is an impossibility due to the infinite amount of fractions of time between the zero moment and 1 second...so no thought is possible mathematically.

In fact life is not possible...since there was no time to create it.

Interesting.

Einstein's Theory of Relativity includes a similar concept...curved space. It is postulated that in curved space you could throw a dart in one direction into space... and it would ultimately return from the opposite direction, after an infinite length of time.

How do you think the universe (energy & matter) came into being w.r.t the theory of the conservation of energy & matter?

Rgds

Substituting back in would give

2[√5-√(2x3)]/2 = √5 - √6

(Please check all answers for accuracy before accepting )

2 5 10 17 28 41 58 77 100 129 160 197 238 281 328 381 440 501 568 639 712 791 874 963 1060 1161 1264 1371 1480 1593 1720 1851 1988 2127 2276 2427 2584 2747 2914 3087 3266 3447 3638 3831 4028 4227 4438 4661 4888 5117 5350 5589 5830 6081 6338 6601 6870 7141 7418 7699 7982 8275 8582 8893 9206 9523 9854 10191 10538 10887 11240 11599 11966 12339 12718 13101 13490 13887 14288 14697 15116 15537 15968 16401 16840 17283 17732 18189 18650 19113 19580 20067 20554 21045 21544 22047 22556 23077 23600 24141 24688 25245 25808 26377 26948 27525 28112 28705 29304 29905 30512 31125 31742 32361 32992 33633 34276 34923 35576 36235 36896 37569 38246 38929 39620 40321 41030 41749 42476 43209 43948 44691 45442 46199 46960 47729 48502 49289 50086 50895 51706 52527 53350 54177 55006 55845 56698 57555 58414 59277 60154 61035 61918 62805 63712 64623 65542 66471 67408 68349 69296 70249 71216 72187 73164 74147 75138 76135 77144 78157 79176 80197 81228 82261 83300 84349 85400 86461 87524 88593 89680 90771 91864 92961 94064 95173 96290 97413 98542 99693 100846 102009 103180 104361 105548 106741 107942 109155 110372 111595 112824 114055 115292 116541 117800 119077 120356 121639 122928 124219 125516 126817 128120 129427 130746 132067 133394 134755 136122 137495 138876 140275 141684 143107 144534 145963 147396 148835 150282 151733 153186 154645 156116 157597 159080 160567 162056 163549 165048 166559

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 487 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511)

The first set is the result of the consecutive sum of the first 240 prime numbers, and the second set in brackets, is the first 240 prime numbers for reference only

I used n=1000 (PNT) which yields a result of 6908

for n log n. The actual value for the 1000th prime is 7919

Let sqrt of 2 = a & sqrt of 3 = b and sqrt of 5 =c, the equation becomes

>> [(1+a)/(c+b)]+[(1-a)/(c-b)]

>> {[(1+a)(c-b)]+[(1-a)(c+b)]}/(c+b)(c-b) ....LCD

>> [(c-b+ac-ab)+(c+b-ac-ab)]/(c^2-b^2) ....simplification

>> 2(c-ab)/(c^2-b^2) ....final simplification

From there you can substitute the values for a,b & c.

Please forgive my notation (answers always to be checked/confirmed!)

Rgds

Yes please!....However it seems that the PNT is poorly accurate in certain ranges as well?

Should I post a larger data set for analysis?

Plotting the limited set of listed data only in post #7, generates a curve with an equation for the trend-line (to the 2nd degree of the polynomial) of

y=1.9294 x^2 -7.7876 x + 14.478 (R^2=0.9997)

Substituting for the 5th term give a value of 24 (actual 28) and the 10th term 130 (actual 129). The equation could be refined to the 6th level polynomial in Excel which should theoretically give greater accuracies -However, this does not always seem to be the case due to the % error of the displayed Excel polynomial equations.

The extrapolated "next term-20th term" (following 568 (19th term in the data set) is 630 vs actual of 639 (20th term in prime number set)...the next prime would as per the Excel curve would then be 630-563= 67 vs actual 71(20th prime)...[The 19th prime is 67!!!]

Hi Zetafunc

How accurate is the PNT at lower values? And how do I use any of these two formulas to say determine the 10th prime which is 29?

2nd "algorithm" for possible determining of prime numbers.

We are all aware of the notorious "irregularity" of prime numbers w.r.t the gaps between prime numbers and consequently the seemingly pointless exercise of trying to generate a trend/prediction line for the set of prime numbers.

However, the curve for the consecutive sum of prime numbers (and some other derivations of the sum of the list of prime numbers) appear to generate a curve that gives a R^2 (Coefficient of determination) of 1 (correct to at six significant following zeros as per excel result.

So we start with 2 (1st term), add the next prime ~2+3 (2nd term), then add the next prime to the 2nd term to get the 3rd term, ect....this data seem to generate a Curve that readily delivers a R^2 of 1.00000. I have then used the Equation of the Curve generated by Excel to determine the next prime! or relatively close to the real prime value using this Curve.

However, the problem with the excel generated equation is that even at the 6th level polynomial, the equation does not hold true for the set of data plotted due to the error factor of the displayed Excel equation for the Curve - I have a very limited capacity laptop.

I am wondering 1) if anybody could comment on the potential of this approach towards the prediction of the "next prime" (or the location of a particular prime in the data set of primes plotted. 2) if somebody that has access to more powerful computing power could generate a more accurate Equation for the Curve, which could then be tested to see how far the resultant equation could be stretched to produce accurate values and location of prime numbers in the prime number set. The initial data for the mentioned realtionship is as follows....2,5,10,17,28,41,58,77,100,129,160,197,238,281,328,381,440,501,568.....

Any comments appreciated

I have developed the algorithm by myself, although I do not want to claim that this algorithm is unique at all and is very similar to the Sieve of Eratosthenes and others I suppose. I see the value of the Algorithm as possibly enabling the determination of a set of prime numbers within a narrow band or range of two (squared) consecutive prime numbers.

Appreciate your comments....very positive since I am only an amateur. I am off to work so I will post the graphic algorithm later today.

Rgds

I shall indeed be cautious and respectful.

My first algorithm is like this:

Starting off with the counting number line (excluding 1) all the multiples of 2 are eliminated (by sieving), leaving "2" and all the positive odd numbers. "2" is marked as a prime number, not being divisible by any smaller prime number.

Next all the odd numbers between the 2 and the square of (3)=9 are listed, which would be 3,5 & 7. These numbers are divided by the marked prime 2 using Excel Modulo function. If the operation yields a remainder, then this number is marked as a prime number, which would be the case for 3,5 & 7. Now 2,3,5 & 7 would be marked/identified as prime numbers.

Next all the remaining odd numbers between the square of (3)=9 and the square of (5)=25 are highlighted, namely 11,13,15,17,19,21 & 23. These highlighted odd numbers are now divided by the prior "identified" prime numbers - 2 & 3 less than the square root of (25)=5. If these highlighted numbers returns remainders for both the division operations for that number, that number is marked as a prime number. (If any division by the "prior" prime numbers should return a null remainder, then that number would not be prime). This would return 11,13,17,19 & 23 as prime numbers following division by 2 & 3, all these numbers returning remainders for both divisions by 2 & 3.

Next the odd numbers between (5) squared=25 and the square of (7)=49...the next identified prime number are highlighted, namely 29,31,37,41,43 & 47. These numbers are now tested by division by the three prior identified prime numbers (less than the square root of 49) -2,3 & 5 in the same manner....this operation would return 29,31,37,41 & 43 as the prime numbers.

Next the odd numbers between the square of (7)=49 and the next identified prime(11)=121 would be highlighted, divided by the next group of identified primes less than the square root of the highest prime square being tested, namely 2,3,5 and 7, following the same procedure/operations.

In this way primes would be identified over smaller "consecutive" ranges, constantly building up the list between consecutive squares of identified primes, as high as one would like to go.

Comments would be appreciated