[math-fun] formulas for producing primes
Hello, I have been working on a problem about primes for a while. How to get a formula that would produce primes in any possible way simpler or more direct than the known ones ? Mills formula : simple enough but it grows way too fast, the 4th term is 4932 digits long. Wright formula : simple too but still too fast. Matyasevich expression : very nice but totally useless for computation. Conwa's FRACTAN expression : even more clever but still useless for computation of primes. Is there another way to get out of this deadlock ? Here is one direction, take S(0) = 43.804... see the details here : http://plouffe.fr/NEW/Formula%20for%20primes.pdf If S(0) is 43.804... then S(n+1) = {S(n)^(5/4)} will produce an endless series of primes beginning, { x } is the rounded value of x. 113 367 1607 10177 102217 1827697 67201679 6084503671 1699344564793 1940223714629437 12877001925259260821 771380135526168946568519 722912215706743477640066820689 21079337353575904691781436731789131951 45166994522409258021988187061430676460306223027 20822194129240450122637347266336444580153717439156314146339 ... it is quite smaller than the known ones. Then the next question is : can we find a smaller exponent that will still work ? Answer : yes. If S(0) = 100000000000000000000000000000049.31221074776345 and the exponent being 11/10 then we get the following primes. 100000000000000000000000000000049 158489319246111348520210137339236753 524807460249772597364312157022725894401 3908408957924020300919472370957356345933709 70990461585528724931289825118059422005340095813 3438111840350699188044461057631015443312900908952333 489724690004200094265557071425023036671550364178496540501 ... even smaller ? : yes with this number S(0) = 10^500 + 961 and the exponent being 51/50 (that is 1.02) then the 50'th term of this formula is 2546223984434301126230560405750836844181156799213460578433735627810123608333414\ 6478717920178906592095759064531694091270765292863071164826802108312142369000399\ 0918112200598834059063704371274865057278618525926963160906859256204291253853779\ 0859263106429982680171352298624867958838188610026225438753363257569617236093303\ 5597738787705978929949787991104492121070145202492140062372248031624879195606603\ 9750665982863462494190199174051345073411763460889751017250124325112902369085214\ 0184828179289329015864573760367060446309168404382462687293461046639169729920475\ 3165541783062017852987962447647230150345731151542656737173297014806244172277491\ 6879804546188079063455344339451528745750861580732838099712175302071382677624428\ 4262968338987678773648741141485490879969521079400774328097643567743161861694439\ 2384400589489332204990330011362168526537013264388448543980911860963264776201897\ 0883314652642873229279315244591969596989887077667619942605707704348251758251233\ 1172015772215487384144161658368225114390354140649309995571635019281763656568221\ 8604642413102656623287079740572453580298728150605437498702948770557573781722652\ 8086931990592223405655647742963234918217685490055779977425394611159718143306147\ 7320512686294534342712886388641680379470072208880905199640988562813955595060316\ 87370269455744702618206542285281401557961196762713023289 Since we get here a series of 50 primes in a row : it does brake the 2 known records for a series of primes : namely : Polynomial expression : 46 values (degree 6) Primes in arithmetic progression : 26 values (with a(1) = 17 digits long). The next good question is : can we make simpler , smaller ? I do not kwow. Best regards, ps : Happy new year 2019 = not a prime.
Just out of interest what’s the best known current algorithm for listing all primes say starting with outputting 3 and missing none ?
On 31 Dec 2018, at 17:07, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello,
I have been working on a problem about primes for a while.
How to get a formula that would produce primes in any possible way simpler or more direct than the known ones ?
Mills formula : simple enough but it grows way too fast, the 4th term is 4932 digits long. Wright formula : simple too but still too fast. Matyasevich expression : very nice but totally useless for computation. Conwa's FRACTAN expression : even more clever but still useless for computation of primes.
Is there another way to get out of this deadlock ?
Here is one direction, take S(0) = 43.804... see the details here : http://plouffe.fr/NEW/Formula%20for%20primes.pdf
If S(0) is 43.804... then S(n+1) = {S(n)^(5/4)} will produce an endless series of primes beginning, { x } is the rounded value of x.
113 367 1607 10177 102217 1827697 67201679 6084503671 1699344564793 1940223714629437 12877001925259260821 771380135526168946568519 722912215706743477640066820689 21079337353575904691781436731789131951 45166994522409258021988187061430676460306223027 20822194129240450122637347266336444580153717439156314146339 ... it is quite smaller than the known ones.
Then the next question is : can we find a smaller exponent that will still work ? Answer : yes.
If S(0) = 100000000000000000000000000000049.31221074776345 and the exponent being 11/10 then we get the following primes.
100000000000000000000000000000049 158489319246111348520210137339236753 524807460249772597364312157022725894401 3908408957924020300919472370957356345933709 70990461585528724931289825118059422005340095813 3438111840350699188044461057631015443312900908952333 489724690004200094265557071425023036671550364178496540501 ...
even smaller ? : yes with this number S(0) = 10^500 + 961 and the exponent being 51/50 (that is 1.02)
then the 50'th term of this formula is 2546223984434301126230560405750836844181156799213460578433735627810123608333414\ 6478717920178906592095759064531694091270765292863071164826802108312142369000399\ 0918112200598834059063704371274865057278618525926963160906859256204291253853779\ 0859263106429982680171352298624867958838188610026225438753363257569617236093303\ 5597738787705978929949787991104492121070145202492140062372248031624879195606603\ 9750665982863462494190199174051345073411763460889751017250124325112902369085214\ 0184828179289329015864573760367060446309168404382462687293461046639169729920475\ 3165541783062017852987962447647230150345731151542656737173297014806244172277491\ 6879804546188079063455344339451528745750861580732838099712175302071382677624428\ 4262968338987678773648741141485490879969521079400774328097643567743161861694439\ 2384400589489332204990330011362168526537013264388448543980911860963264776201897\ 0883314652642873229279315244591969596989887077667619942605707704348251758251233\ 1172015772215487384144161658368225114390354140649309995571635019281763656568221\ 8604642413102656623287079740572453580298728150605437498702948770557573781722652\ 8086931990592223405655647742963234918217685490055779977425394611159718143306147\ 7320512686294534342712886388641680379470072208880905199640988562813955595060316\ 87370269455744702618206542285281401557961196762713023289
Since we get here a series of 50 primes in a row : it does brake the 2 known records for a series of primes : namely : Polynomial expression : 46 values (degree 6) Primes in arithmetic progression : 26 values (with a(1) = 17 digits long).
The next good question is : can we make simpler , smaller ? I do not kwow.
Best regards, ps : Happy new year 2019 = not a prime. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hello , the best algorithm is the Sieve of Erathosthene or some fancy improvements that have been done since the greeks, As far as I know the best program on this planet is Primesieve.exe (on windows) it produces a list of primes from 2 to whatever you want almost as the speed of your disk drive : in other words it is so fast that the disk can barely follow the flow of primes to be written to it. Try it you will see : primesieve.exe is easy to find on google. Best regards happy new year. Le lun. 31 déc. 2018 à 18:32, D J Makin via math-fun < math-fun@mailman.xmission.com> a écrit :
Just out of interest what’s the best known current algorithm for listing all primes say starting with outputting 3 and missing none ?
On 31 Dec 2018, at 17:07, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello,
I have been working on a problem about primes for a while.
How to get a formula that would produce primes in any possible way simpler or more direct than the known ones ?
Mills formula : simple enough but it grows way too fast, the 4th term is 4932 digits long. Wright formula : simple too but still too fast. Matyasevich expression : very nice but totally useless for computation. Conwa's FRACTAN expression : even more clever but still useless for computation of primes.
Is there another way to get out of this deadlock ?
Here is one direction, take S(0) = 43.804... see the details here : http://plouffe.fr/NEW/Formula%20for%20primes.pdf
If S(0) is 43.804... then S(n+1) = {S(n)^(5/4)} will produce an endless series of primes beginning, { x } is the rounded value of x.
113 367 1607 10177 102217 1827697 67201679 6084503671 1699344564793 1940223714629437 12877001925259260821 771380135526168946568519 722912215706743477640066820689 21079337353575904691781436731789131951 45166994522409258021988187061430676460306223027 20822194129240450122637347266336444580153717439156314146339 ... it is quite smaller than the known ones.
Then the next question is : can we find a smaller exponent that will still work ? Answer : yes.
If S(0) = 100000000000000000000000000000049.31221074776345 and the exponent being 11/10 then we get the following primes.
100000000000000000000000000000049 158489319246111348520210137339236753 524807460249772597364312157022725894401 3908408957924020300919472370957356345933709 70990461585528724931289825118059422005340095813 3438111840350699188044461057631015443312900908952333 489724690004200094265557071425023036671550364178496540501 ...
even smaller ? : yes with this number S(0) = 10^500 + 961 and the exponent being 51/50 (that is 1.02)
then the 50'th term of this formula is
2546223984434301126230560405750836844181156799213460578433735627810123608333414\
6478717920178906592095759064531694091270765292863071164826802108312142369000399\
0918112200598834059063704371274865057278618525926963160906859256204291253853779\
0859263106429982680171352298624867958838188610026225438753363257569617236093303\
5597738787705978929949787991104492121070145202492140062372248031624879195606603\
9750665982863462494190199174051345073411763460889751017250124325112902369085214\
0184828179289329015864573760367060446309168404382462687293461046639169729920475\
3165541783062017852987962447647230150345731151542656737173297014806244172277491\
6879804546188079063455344339451528745750861580732838099712175302071382677624428\
4262968338987678773648741141485490879969521079400774328097643567743161861694439\
2384400589489332204990330011362168526537013264388448543980911860963264776201897\
0883314652642873229279315244591969596989887077667619942605707704348251758251233\
1172015772215487384144161658368225114390354140649309995571635019281763656568221\
8604642413102656623287079740572453580298728150605437498702948770557573781722652\
8086931990592223405655647742963234918217685490055779977425394611159718143306147\
7320512686294534342712886388641680379470072208880905199640988562813955595060316\
87370269455744702618206542285281401557961196762713023289
Since we get here a series of 50 primes in a row : it does brake the 2 known records for a series of primes : namely : Polynomial expression : 46 values (degree 6) Primes in arithmetic progression : 26 values (with a(1) = 17 digits long).
The next good question is : can we make simpler , smaller ? I do not kwow.
Best regards, ps : Happy new year 2019 = not a prime. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dear Simon, By Bertrand's postulate you can find a prime with n binary digits for all n >= 2. Form a real number by concatenating them in binary: 0 2 5 11 17 ... 0.0 10 101 1011 10001 ... (in base 2) (We trivially don't end up with '1 recurring' because 2^n - 1 can only be prime whenever n is prime.) Let's call this number x. Then the number: floor(x 2^((n(n+1))/2)) mod 2^n pulls out the n-digit prime from this real. If you don't like the modulo operator, you can emulate it by more floors and suchlike. Best wishes, Adam P. Goucher
Sent: Monday, December 31, 2018 at 5:07 PM From: "Simon Plouffe" <simon.plouffe@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] formulas for producing primes
Hello,
I have been working on a problem about primes for a while.
How to get a formula that would produce primes in any possible way simpler or more direct than the known ones ?
Mills formula : simple enough but it grows way too fast, the 4th term is 4932 digits long. Wright formula : simple too but still too fast. Matyasevich expression : very nice but totally useless for computation. Conwa's FRACTAN expression : even more clever but still useless for computation of primes.
Is there another way to get out of this deadlock ?
Here is one direction, take S(0) = 43.804... see the details here : http://plouffe.fr/NEW/Formula%20for%20primes.pdf
If S(0) is 43.804... then S(n+1) = {S(n)^(5/4)} will produce an endless series of primes beginning, { x } is the rounded value of x.
113 367 1607 10177 102217 1827697 67201679 6084503671 1699344564793 1940223714629437 12877001925259260821 771380135526168946568519 722912215706743477640066820689 21079337353575904691781436731789131951 45166994522409258021988187061430676460306223027 20822194129240450122637347266336444580153717439156314146339 ... it is quite smaller than the known ones.
Then the next question is : can we find a smaller exponent that will still work ? Answer : yes.
If S(0) = 100000000000000000000000000000049.31221074776345 and the exponent being 11/10 then we get the following primes.
100000000000000000000000000000049 158489319246111348520210137339236753 524807460249772597364312157022725894401 3908408957924020300919472370957356345933709 70990461585528724931289825118059422005340095813 3438111840350699188044461057631015443312900908952333 489724690004200094265557071425023036671550364178496540501 ...
even smaller ? : yes with this number S(0) = 10^500 + 961 and the exponent being 51/50 (that is 1.02)
then the 50'th term of this formula is 2546223984434301126230560405750836844181156799213460578433735627810123608333414\ 6478717920178906592095759064531694091270765292863071164826802108312142369000399\ 0918112200598834059063704371274865057278618525926963160906859256204291253853779\ 0859263106429982680171352298624867958838188610026225438753363257569617236093303\ 5597738787705978929949787991104492121070145202492140062372248031624879195606603\ 9750665982863462494190199174051345073411763460889751017250124325112902369085214\ 0184828179289329015864573760367060446309168404382462687293461046639169729920475\ 3165541783062017852987962447647230150345731151542656737173297014806244172277491\ 6879804546188079063455344339451528745750861580732838099712175302071382677624428\ 4262968338987678773648741141485490879969521079400774328097643567743161861694439\ 2384400589489332204990330011362168526537013264388448543980911860963264776201897\ 0883314652642873229279315244591969596989887077667619942605707704348251758251233\ 1172015772215487384144161658368225114390354140649309995571635019281763656568221\ 8604642413102656623287079740572453580298728150605437498702948770557573781722652\ 8086931990592223405655647742963234918217685490055779977425394611159718143306147\ 7320512686294534342712886388641680379470072208880905199640988562813955595060316\ 87370269455744702618206542285281401557961196762713023289
Since we get here a series of 50 primes in a row : it does brake the 2 known records for a series of primes : namely : Polynomial expression : 46 values (degree 6) Primes in arithmetic progression : 26 values (with a(1) = 17 digits long).
The next good question is : can we make simpler , smaller ? I do not kwow.
Best regards, ps : Happy new year 2019 = not a prime. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, it is true, you concatenate the primes in binary and use { } or [ ] to list them using a real constant. But : there are no compression of data in this scheme, it is just a rewrite of the series of primes. In other words it works but there is no gain. In my last example, a precision of 1320 digits gives back 66000 digits of concatenated primes , a good ratio signal/noise. In the case of Mills formula, as far as I know there are no compression at all since you need a very high precision to get the n'th prime. It is a bit better with Wright formula but not much. That's the whole point. Simon Plouffe Le lun. 31 déc. 2018 à 18:33, Adam P. Goucher <apgoucher@gmx.com> a écrit :
Dear Simon,
By Bertrand's postulate you can find a prime with n binary digits for all n >= 2. Form a real number by concatenating them in binary:
0 2 5 11 17 ...
0.0 10 101 1011 10001 ... (in base 2)
(We trivially don't end up with '1 recurring' because 2^n - 1 can only be prime whenever n is prime.)
Let's call this number x. Then the number:
floor(x 2^((n(n+1))/2)) mod 2^n
pulls out the n-digit prime from this real.
If you don't like the modulo operator, you can emulate it by more floors and suchlike.
Best wishes,
Adam P. Goucher
Sent: Monday, December 31, 2018 at 5:07 PM From: "Simon Plouffe" <simon.plouffe@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] formulas for producing primes
Hello,
I have been working on a problem about primes for a while.
How to get a formula that would produce primes in any possible way simpler or more direct than the known ones ?
Mills formula : simple enough but it grows way too fast, the 4th term is 4932 digits long. Wright formula : simple too but still too fast. Matyasevich expression : very nice but totally useless for computation. Conwa's FRACTAN expression : even more clever but still useless for computation of primes.
Is there another way to get out of this deadlock ?
Here is one direction, take S(0) = 43.804... see the details here : http://plouffe.fr/NEW/Formula%20for%20primes.pdf
If S(0) is 43.804... then S(n+1) = {S(n)^(5/4)} will produce an endless series of primes beginning, { x } is the rounded value of x.
113 367 1607 10177 102217 1827697 67201679 6084503671 1699344564793 1940223714629437 12877001925259260821 771380135526168946568519 722912215706743477640066820689 21079337353575904691781436731789131951 45166994522409258021988187061430676460306223027 20822194129240450122637347266336444580153717439156314146339 ... it is quite smaller than the known ones.
Then the next question is : can we find a smaller exponent that will still work ? Answer : yes.
If S(0) = 100000000000000000000000000000049.31221074776345 and the exponent being 11/10 then we get the following primes.
100000000000000000000000000000049 158489319246111348520210137339236753 524807460249772597364312157022725894401 3908408957924020300919472370957356345933709 70990461585528724931289825118059422005340095813 3438111840350699188044461057631015443312900908952333 489724690004200094265557071425023036671550364178496540501 ...
even smaller ? : yes with this number S(0) = 10^500 + 961 and the exponent being 51/50 (that is 1.02)
then the 50'th term of this formula is
2546223984434301126230560405750836844181156799213460578433735627810123608333414\
6478717920178906592095759064531694091270765292863071164826802108312142369000399\
0918112200598834059063704371274865057278618525926963160906859256204291253853779\
0859263106429982680171352298624867958838188610026225438753363257569617236093303\
5597738787705978929949787991104492121070145202492140062372248031624879195606603\
9750665982863462494190199174051345073411763460889751017250124325112902369085214\
0184828179289329015864573760367060446309168404382462687293461046639169729920475\
3165541783062017852987962447647230150345731151542656737173297014806244172277491\
6879804546188079063455344339451528745750861580732838099712175302071382677624428\
4262968338987678773648741141485490879969521079400774328097643567743161861694439\
2384400589489332204990330011362168526537013264388448543980911860963264776201897\
0883314652642873229279315244591969596989887077667619942605707704348251758251233\
1172015772215487384144161658368225114390354140649309995571635019281763656568221\
8604642413102656623287079740572453580298728150605437498702948770557573781722652\
8086931990592223405655647742963234918217685490055779977425394611159718143306147\
7320512686294534342712886388641680379470072208880905199640988562813955595060316\
87370269455744702618206542285281401557961196762713023289
Since we get here a series of 50 primes in a row : it does brake the 2 known records for a series of primes : namely : Polynomial expression : 46 values (degree 6) Primes in arithmetic progression : 26 values (with a(1) = 17 digits long).
The next good question is : can we make simpler , smaller ? I do not kwow.
Best regards, ps : Happy new year 2019 = not a prime. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Well the simplest math expression to test if n is prime I’d guess is that n is prime if (gamma(n)^2)%n is not zero ;) I tested this using the mathematically simpler and smaller (but somewhat slower?) ((n-1)!*p!)%n where p! is the product of the primes less than n and with the exact equivalent to the gamma version ((n-1)!^2)%n. Not much use for huge primes without an incredibly fast and incredibly accurate method of evaluating the gamma function.
Sent: Monday, December 31, 2018 at 5:07 PM From: "Simon Plouffe" <simon.plouffe@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: [math-fun] formulas for producing primes <snip> The next good question is : can we make simpler , smaller ? I do not know.
Best regards, ps : Happy new year 2019 = not a prime. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Adam P. Goucher -
D J Makin -
Simon Plouffe