Math Is Fun Forum

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

You are not logged in.

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

More or less Prime

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

smile

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

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

Okay, have a good day. See you later.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: More or less Prime

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)

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: More or less Prime

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

Offline

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

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: More or less Prime

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.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

Yes, that would help.

How high did you go for the PNT?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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

Offline

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

zetafunc
Moderator
Registered: 2014-05-21
Posts: 2,432
Website

Re: More or less Prime

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.)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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

Thx

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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)

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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...


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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?

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: More or less Prime

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.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

Gophne
Member
Registered: 2016-10-16
Posts: 26

Re: More or less Prime

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

Offline

Board footer

Powered by FluxBB