More or less Prime

Gophne · 2016-10-16 06:08:11

I am a prime number hobbyist! I am looking at patterns/formula for prime numbers. I do not ascribe to the notion that "prime numbers are "random" or even pseudo-random as I believe they are very much systematic due the fact that they are generated by elimination of the multiples of the lowest prime numbers (integers) on the integer number line progressively upwards, but essentially at a fixed increment of 1. I believe that it is also not essential to access big primes to generate a possible "formula" as the formula should work for all values, including the low prime numbers!!

I have developed two "algorithms" which I need to post somewhere where some math gurus could have a look if they make sense...but it might well be that others have already formulated such "algorithms". My first algorithm is essentially a variation of the Sieve of Eratostene and the other is a graphic function which returns a R^2 of 1 in Excel

I am not a serious mathematician, so I am not fluent in some of the deeper proofs and stuff, but I can follow the logic of the proofs in broad terms.

Is there anybody out there that might be interested in looking at my ideas?

Rgds

Last edited by Gophne (2016-10-16 06:12:52)

bobbym · 2016-10-16 06:12:21

Hi;

Post them, but do so humbly, no one has ever found any patterns in the placement of the primes among the natural numbers. Your ideas will most likely have holes but there is no harm in looking.

I am not a serious mathematician, so I am not fluent in some of the deeper proofs and stuff, but I can follow the logic of the proofs in broad terms.

The primes have been the playground of mathematicians for more than 2000 years. All the great minds of every century have studied them, some for their entire lifetimes. In modern times guys with supercomputers fiddle with them too. Keep that in mine when studying them, even as a very talented amateur. Ask yourself this question, have I found what everyone before me missed? Am I that guy?

I do not ascribe to the notion that "prime numbers are "random" or even pseudo-random

Do not be devastated if your new approach was looked at by someone already 300 years before we were born and found to fail. Your posts may attract some of those guys who are well versed with this problem, they may tell you in no uncertain terms that this or that is hogwash. I will expect both you and them to respond politely according to the rules laid down in this forum. There will be no exceptions, no leniency, no tolerance for rudeness.

That being said and out of the way, what is it exactly that you are trying to do? Oh, welcome to the forum.

Gophne · 2016-10-16 08:43:35

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

Last edited by Gophne (2016-10-16 08:45:15)

bobbym · 2016-10-16 09:04:41

Hi;

It is good that you have discovered the sieve. Did you do it by yourself? Even better.

Let us look at this statement though.

as high as one would like to go.

Can we really go as high as we like? There is another factor governing our use of an algorithm. It is called feasibility. Lots of times we just know that our method will get them all or find the correct answer or sort that list, whatever. But we are finite creatures, with a limited amount of time available to us. An algorithm could be said to be infeasible if the amount of time it takes to finish is longer than we are willing to wait.

An algorithm that runs for an hour, is inconvenient but still feasible. If it takes a day or two we say it is feasible. A month or two okay, a year or two and you are stretching it. A century or two and we say it is infeasible since I will no longer be around to collect the answer. What do you imagine the time would be with such an algorithm as you describe, if I interpreted "as high as you like" to mean I want all the primes up to 1000000000000000000000000?

Gophne · 2016-10-16 17:03:41

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

Last edited by Gophne (2016-10-17 09:02:00)

bobbym · 2016-10-16 22:08:57

Okay, have a good day. See you later.

Gophne · 2016-10-17 07:10: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

Last edited by Gophne (2016-10-17 07:29:54)

zetafunc · 2016-10-17 07:22:35

I haven't read your algorithms in detail, but I can tell you that the Prime Number Theorem implies that, asymptotically, the nth prime is about This, along with a few other results, can be used to show that the nth term of your sequence is, asymptotically:

The other terms in the asymptotic expansion involve logarithmic integrals.

Last edited by zetafunc (2016-10-17 07:24:44)

Gophne · 2016-10-17 08:04:25

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?

Last edited by Gophne (2016-10-17 08:13:18)

zetafunc · 2016-10-17 08:12:52

It is not very accurate at all for small values of n. However, as n goes to infinity, the PNT gives an exact expression.

zetafunc · 2016-10-17 08:23:19

Gophne wrote:

And how do I use any of these two formulas to say determine the 10th prime which is 29?

That formula is asymptotic, so it will not be able to give you the nth prime. You can find a better approximation here.

Gophne · 2016-10-17 08:48:41

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!!!]

Last edited by Gophne (2016-10-17 09:05:52)

bobbym · 2016-10-17 10:23:40

Hi;

If I understand the computational part of what you are trying is that you wish to fit a high degree polynomial to that data you have found in post #7.

If that is what you want I will go over with you why this statement

The equation could be refined to the 6th level polynomial in Excel which should theoretically give greater accuracies

is not always true. After that we will play with polynomial interpolation of the numbers and we will generate more numbers and yet higher degree fits... I just want you to know why we will fail.

Gophne · 2016-10-17 10:28:37

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?

Last edited by Gophne (2016-10-17 10:32:25)

bobbym · 2016-10-17 23:23:42

Yes, that would help.

How high did you go for the PNT?

Gophne · 2016-10-18 06:36:43

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

zetafunc · 2016-10-18 07:39:06

Also, the PNT has an error term, if you don't use the asymptotics. In particular, if you assume that the Riemann hypothesis is true, then:

(That is, the above is true if and only if the Riemann hypothesis is true.)

bobbym · 2016-10-18 08:07:22

Hi;

Your second list is an accumulated sum of the primes. What do you want to do with it?

I used n=1000 (PNT) which yields a result of 6908
for n log n. The actual value for the 1000th prime is 7919

Intuitively we can see a convergence to 1 when n is infinity.

Gophne · 2016-10-18 08:13:22

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

Thx

bobbym · 2016-10-18 08:18:54

Hi;

I meant your first list is an accumulated sum of primes, sorry for the confusion. Is that the one you want to try a polynomial fit for?

The formula you are using to estimate the nth prime is only the first term in a series. To get more accuracy, you just require more terms.

Gophne · 2016-10-18 08:27:07

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.

Last edited by Gophne (2016-10-18 08:29:10)

bobbym · 2016-10-18 08:39:01

Already have the first one in and all the arithmetic when possible will be done in rationals to avoid floating point errors.

Supposing we start with a 4th order polynomial. We need 5 points to fit exactly a 4th order poly.

We use 2, 5, 10, 17, 28. We get:

If we plug in n = 1,2,3,4, 5 we get {2, 5, 10, 17, 28} which is indeed correct as we expected.

But how about n = 6, for that we get a prediction of 41 but the answer is 47.

So a 4th order poly can not even get the next one right. If you check it, it will be misleading for all the rest too.

What can we do? We can try a higher degree poly...

Let us try a 10th order polynomial, for that we will need 11 points. We will use 2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160. We get:

If we plug in n = 1,2,3,4,5,...11 we get {2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160} just as we should. Now try the very next one n = 12. We get a prediction of 541 but looking at your list we see the 12th one is 197. Once again not even close...

Gophne · 2016-10-18 16:45:39

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?

bobbym · 2016-10-18 19:13:21

Hi;

I can do better than that, I am going to use a 239th degree polynomial which will use all the points.

The polynomial is too large to post here and when I plug in n = 1,2,3,4,5,...240 it gets the number in your list.

It predicts 289991435608324462325753933907157920092316477855532814885155747935084486 for the next number but if we would extend your list the 241st one would be 168074, again not even close.

What this shows is that even if we do an interpolation which will always fit for the numbers we use, if we go outside those numbers we are dead.

Gophne · 2016-10-18 23:20:33

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

Math Is Fun Forum

#1 2016-10-16 06:08:11

More or less Prime

#2 2016-10-16 06:12:21

Re: More or less Prime

#3 2016-10-16 08:43:35

Re: More or less Prime

#4 2016-10-16 09:04:41

Re: More or less Prime

#5 2016-10-16 17:03:41

Re: More or less Prime

#6 2016-10-16 22:08:57

Re: More or less Prime

#7 2016-10-17 07:10:29

Re: More or less Prime

#8 2016-10-17 07:22:35

Re: More or less Prime

#9 2016-10-17 08:04:25

Re: More or less Prime

#10 2016-10-17 08:12:52

Re: More or less Prime

#11 2016-10-17 08:23:19

Re: More or less Prime

#12 2016-10-17 08:48:41

Re: More or less Prime

#13 2016-10-17 10:23:40

Re: More or less Prime

#14 2016-10-17 10:28:37

Re: More or less Prime

#15 2016-10-17 23:23:42

Re: More or less Prime

#16 2016-10-18 06:36:43

Re: More or less Prime

#17 2016-10-18 07:39:06

Re: More or less Prime

#18 2016-10-18 08:07:22

Re: More or less Prime

#19 2016-10-18 08:13:22

Re: More or less Prime

#20 2016-10-18 08:18:54

Re: More or less Prime

#21 2016-10-18 08:27:07

Re: More or less Prime

#22 2016-10-18 08:39:01

Re: More or less Prime

#23 2016-10-18 16:45:39

Re: More or less Prime

#24 2016-10-18 19:13:21

Re: More or less Prime

#25 2016-10-18 23:20:33

Re: More or less Prime

Board footer