tag:blogger.com,1999:blog-20067416.post7758446958111733012..comments2022-09-22T01:46:17.706-04:00Comments on Recursivity: Rutgers Graduate Student Finds New Prime-Generating FormulaUnknownnoreply@blogger.comBlogger26125tag:blogger.com,1999:blog-20067416.post-78776995386864740022015-06-24T22:42:44.997-04:002015-06-24T22:42:44.997-04:00Define the following sequence (given using Haskell...Define the following sequence (given using Haskell syntax).<br /><br />r 2 = 1<br />r n = (n-1 - (n-2)*(signum ((gcd x (n-1)) - 1))) * x<br /> where x = r (n-1)<br /><br />Then (r (n+1)) / (r n) is always 1 or a prime for n >= 2. Furthermore the sequence contains all the prime numbers in increasing order. Is this related in some way?Anonymoushttps://www.blogger.com/profile/14687716858207901305noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-83366283232971656562013-08-07T22:03:38.402-04:002013-08-07T22:03:38.402-04:00Why don't you just ask him, instead of me?Why don't you just ask him, instead of me?Jeffrey Shallithttps://www.blogger.com/profile/12763971505497961430noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-4409981634712738352013-08-07T19:51:39.571-04:002013-08-07T19:51:39.571-04:00You said Benoit Cloitre proved his prime-generatin...You said Benoit Cloitre proved his prime-generating formula. Did Benoit Cloitre proved his prime-generating formula? Eric Rowland said he did not in this presentation on the last page: http://thales.math.uqam.ca/~rowland/talks/Formulas_for_primes.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-42462833148580506862009-03-26T14:10:00.000-04:002009-03-26T14:10:00.000-04:00Just found this site and am trying to convert the ...Just found this site and am trying to convert the code into "J".<BR/><BR/>In "J" (not java) you would write the following for GCD:<BR/><BR/>x +. y<BR/><BR/>So as an example:<BR/><BR/> x: 147573952589676412927 +. 761838257287<BR/><BR/>will return<BR/><BR/>761838257287<BR/><BR/>Buy the way:<BR/><BR/>1 - 2^67 is 147573952589676412927<BR/><BR/>and factors to the following numbers of:<BR/><BR/>193707721 761838257287Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-5252718825463648022008-08-19T12:21:00.000-04:002008-08-19T12:21:00.000-04:00This prime chain of 3237 terms, 1671 of which are ...This prime chain of 3237 terms, 1671 of which are distinct, was found by means of a prime-producing<BR/>generator closely akin to Eric Rowland's formula for an infinite<BR/>chain: a(1) = 7, n>1, a(n) = a(n-1) + gcd(n,a(n-1) .<BR/><BR/>It could be argued that neither one is a true prime chain since<BR/>there is a vast sea<BR/>of 1's in-between each prime, and that mine is not really even<BR/>a 'formula' since it<BR/>does not achieve an infinite consecutive list, but I see these<BR/>objections as<BR/>being more semantic than substantial in nature. I also believe that<BR/>the entire set of<BR/>primes occurring in the sequence represented by x^2 - x + 1 will<BR/>eventually appear in the<BR/>formula below,(about 1/2 of all primes) but this is yet to be<BR/>proved, and it is unclear due<BR/>to equipment limitations if the extreme density of primes at the<BR/>beginning of the sequence<BR/>continues indefinitely or breaks down at some point.<BR/><BR/>Let f(x) := x^2 - x + 41, x = 1, k = 2, a = 3 .<BR/>Repeat indefinitely a two-step process:<BR/>x := x + 1,<BR/>If GCD( x^2 - x + 41, (x-1)^2 - (x - 1) + 41 - a* k ) >1,<BR/>then k := k + 1;<BR/><BR/>The first 20 values of the sequence that do not equal '1' are:<BR/>47, 227, 71, 359, 113, 563, 173, 839, 251,1187,347, 1607,<BR/>461,2099,593, 2663, 743,<BR/>3299, 911,4007<BR/><BR/>Many other values for the 'a' variable above, perhaps infinitely<BR/>many, (but not all)<BR/>may be substituted in the formula and produce long initial prime<BR/>chains.<BR/>for a = 3 : 3237 consecutive primes,<BR/>a = 2 : 736<BR/>a = 4 : 817<BR/>a = 5 : 858<BR/>a = 6 : 161<BR/>a = 7 : 1159<BR/>a = 8 : 221<BR/>a = 9 : 284<BR/>a = 10 : 1276 etc.<BR/><BR/>Many other equations, perhaps infinitely many, (but not all) may be<BR/>substituted<BR/>for x^2 - x + 1 in the given formula, or a more complicated<BR/>development of that formula,<BR/>with good results. Example: f(x):= 5*x^2 + 5*x + 1, x = 1,<BR/>k = 2, a = 10 : 553 consecutive primes, 276 distinct primes.<BR/><BR/>Aldrich StevensAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-20735769714769129032008-07-30T09:59:00.000-04:002008-07-30T09:59:00.000-04:00Look up in google groups sci-mathon july 24-25 for...Look up in google groups sci-math<BR/>on july 24-25 for --<BR/>"A prime Generator that needs no<BR/>previous primes" will give the <BR/>correct indent for the Python <BR/>program I posted here.<BR/><BR/>DanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-61496403025120091242008-07-30T00:07:00.000-04:002008-07-30T00:07:00.000-04:00Through a unique summation sieving algorithm it is...Through a unique summation sieving algorithm it is <BR/>possible to sequentially produce all odd primes <BR/>up too any stopping point of (n) without using <BR/>any previous primes. <BR/>Likewise it is also possible to start with a large <BR/>prime and continue with this sequential list of <BR/>large primes up too any stopping point for (n) <BR/>without using any previous primes in the process <BR/>of generating these primes. <BR/><BR/>Here it is in Python code for all odd primes <BR/>up too (n)= 20000. <BR/>I am not sure if it will indent properly in <BR/>this post because in preview it shows no indents? <BR/><BR/><BR/>n= -2;n1= -4;n2= -1;n4=4;n5=1;b1=0;j=0 <BR/>a=[0]*20001 <BR/>data=[9,3,2,1,3,2] <BR/>for i in range(len(data)): <BR/> a1=data[i] <BR/> a1=a1+b1;a[a1]=a1;b1=a1 <BR/>a1=b1+n;a[a1]=a1;b1=a1 <BR/>n=n+n1 <BR/>for x in range(20000): <BR/> i=n4 <BR/> while i>=2: <BR/> a1=a1+i <BR/> if a1<=20000: a[a1]=a1 <BR/> i=i-1 <BR/> a1=a1+n <BR/> if a1<=20000: a[a1]=a1 <BR/> n4=n4+n5;n=n-n4 <BR/>for ii in range(10000): <BR/> i=2*ii+1 <BR/> if a[i]==0 and i>1: print i,;j=j+1 <BR/>print 'Total odd primes =',j <BR/>--------------------------------------------------- <BR/>Prime print output = 3,5,7,11,..19997 which is the last <BR/>prime less than (n) where n=20000 and gives a total number of odd primes = 2261. <BR/><BR/><BR/>So odd primes do have a pattern, complex as their pattern <BR/>may be through summations and negations starting with (9). <BR/>where this summation and negation never produce an odd prime. <BR/><BR/><BR/>It is very slow but shows this complex pattern of the odd primes <BR/>after the first summation of these 6 integers where no odd primes <BR/>are produced at each point of the summation. <BR/><BR/><BR/>+9+3+2+1+3+2 <BR/><BR/><BR/>Then continuing with the summations and negations below <BR/>where also no odd primes are produced when this pattern <BR/>emerges. <BR/><BR/><BR/>-2 <BR/>+4+3+2 <BR/>-6 <BR/>+5+4+3+2 <BR/>-11 <BR/>+6+5+4+3+2 <BR/>-17 <BR/>+7+6+5+4+3+2 <BR/>-24 <BR/>+8+7+6+5+4+3+2 <BR/>-32 <BR/>+9+8+7+6+5+4+3+2 <BR/>-41 <BR/>+10+.. <BR/>etc. <BR/>The pattern for the negations is just the difference <BR/>of +4 and -2 = 6 ,so the next negation is just -6 <BR/>The next negation is the difference of -6 and +5 = 11, <BR/>so the next negation is -11. and so on. <BR/>The other groups of summations have an obvious pattern <BR/>which increments by one from the previous group. <BR/><BR/><BR/>All the odd integers produced from these <BR/>summations and negations are composite and all the <BR/>odd integers (not) produced are primes except (1). <BR/><BR/><BR/>The problem is, many composites repeat one or more <BR/>times which adds to the processing time. <BR/><BR/><BR/>DanAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-20115711467355202032008-07-25T16:00:00.000-04:002008-07-25T16:00:00.000-04:00Congrats to Eric on the paper!Here is the formula ...Congrats to Eric on the paper!<BR/><BR/>Here is the formula in Mathematica, which Eric uses:<BR/><BR/>a[1]=7;<BR/><BR/>a[n_] := a[n-1] + GCD[n, a[n-1]]<BR/><BR/>If you want to remember (memoize the values) to speed it up:<BR/><BR/>a[n_] := a[n] = a[n-1] + GCD[n,a[n-1]]<BR/><BR/>In[4]:= Array[a,23]<BR/>Out[4]= {7,8,9,10,15,18,19,20,21,22,33,36,<BR/>37,38,39,40,41,42,43,44,45,46,69}<BR/><BR/>In[5]:= Differences[%]<BR/>Out[5]= {1,1,1,5,3,1,1,1,1,11,3,1,1,1,1,1,<BR/> 1,1,1,1,1,23}<BR/><BR/>In[6]:= DeleteCases[%,1]<BR/>Out[6]= {5,3,11,3,23}<BR/><BR/>In[7]:= PrimeQ/@%<BR/>Out[7]= {True,True,True,True,True}<BR/><BR/>Here's are the primes generated:<BR/><BR/>In[8]:= First/@Tally[DeleteCases[<BR/> Differences[Array[a,100000]],1]]<BR/><BR/>Out[8]= {5,3,11,23,47,101,7,13,233,467,941,<BR/>1889,3779,7559,15131,53,<BR/>30323,60647}<BR/><BR/>and in sorted order:<BR/><BR/>In[9]:= Union[DeleteCases[Differences[<BR/> Array[a,100000]],1]]<BR/><BR/>Out[9]= {3,5,7,11,13,23,47,53,101,233,467,<BR/> 941,1889,3779,7559,15131,30323,<BR/> 60647}<BR/><BR/>The formula can be seen as a "simple program" that generates an output known to be in some sense complicated, a point made very generally in Stephen Wolfram's 2002 book "A New Kind of Science".<BR/><BR/>Richard P.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-59033773985529438532008-07-25T15:26:00.000-04:002008-07-25T15:26:00.000-04:00I agree with Pseudonym, it can be calculated witho...I agree with Pseudonym, it can be calculated without even doing any recursion in c. The gcd function isn't a big problem, the euclidean is fast enough for me. But the main code would look like:<BR/><BR/>int main(void) {<BR/> unsigned int a,b,p,n;<BR/> a = 7;<BR/> for(n=2;n!=10000000;n++) {<BR/> b = a + gcd(n,a);<BR/> printf("%i %i\n",n-1,b-a);<BR/> a = b;<BR/> }<BR/>}<BR/><BR/>which makes it twice as fast then the old one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-69030847032982342792008-07-24T02:41:00.000-04:002008-07-24T02:41:00.000-04:00Shawn:rowlandSequence = filter (/= 1) $ zipWith (-...Shawn:<BR/><BR/>rowlandSequence = filter (/= 1) $ zipWith (-) (tail as) as<BR/> where<BR/> as = as' 7 2<BR/> as' an1 n = an1 : as' (an1 + gcd n an1) (n+1)<BR/><BR/>The two recursive calls are the main source of inefficiency in your code.Pseudonymhttps://www.blogger.com/profile/04272326070593532463noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-60560153623559510282008-07-23T21:54:00.000-04:002008-07-23T21:54:00.000-04:00Good catch Ryan, the algorithm they've implemented...Good catch Ryan, the algorithm they've implemented is actually *exactly* the "Accelerated Integer GCD Algorithm" I was talking about - I knew Kenneth Weber had contributed some code to gmp, but from the paper it seemed it was only part of the algorithm - iirc, a bmod implementation... (I guess I was wrong)<BR/><BR/>I've been doing some number-crunching, and along with the realization that the accelerated algorithm doesn't really offer a speed-up before there's a 5-bit difference in the size of n and a(n-1), I think gmp will definitely be needed well before the new algorithm saves us time - I'm not actually too sure it will ever happen - on average this seems to hold: a(n) ~= 2.5*n, any clever arguments as to why this would or would not ever cause a 5 (or more) bit difference in sizes?The Professorhttps://www.blogger.com/profile/00090522839301386041noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-81931163477920183632008-07-23T16:26:00.000-04:002008-07-23T16:26:00.000-04:00According to some info on the GMP site, (http://gm...According to some info on the GMP site, (<A HREF="http://gmplib.org/devel/" REL="nofollow">http://gmplib.org/devel/</A>), there's a very fast GCD implementation planned for a future release. Should just be a drop-in replacement for the one in the current release, so maybe someone should give it a try. According to that page, it is significantly faster than the current one.Ryan Grahamhttps://www.blogger.com/profile/18319610639577200961noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-10169159062648705542008-07-23T15:41:00.000-04:002008-07-23T15:41:00.000-04:00n00b, it depends on your platform, really... in th...n00b, it depends on your platform, really... in theory, the binary one I'm using should be faster, but on some platforms Euclids algorithm outperforms it marginally (looks like yours is one such case)<BR/><BR/>But as I mentioned a couple of posts up, Sequential (or Parallel) Accelerated Integer GCD is (probably) what we should be using - though I don't know of any implementation of it<BR/><BR/>I've not been able to find even an implementation of the "normal" Accelerated Integer GCD, though if anyone cares to read about it, here's the paper: <A HREF="http://www.csie.nuk.edu.tw/~cychen/gcd/The%20accelerated%20integer%20GCD%20algorithm.pdf" REL="nofollow">The accelerated integer GCD algorithm</A>The Professorhttps://www.blogger.com/profile/00090522839301386041noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-47326563066847810492008-07-23T02:10:00.000-04:002008-07-23T02:10:00.000-04:00Hmmm, parallelizing is the next tempting possibili...Hmmm, parallelizing is the next tempting possibility...<BR/><BR/>If you read the paper, an interesting point is that Stephen Wolfram was actually leading the summer school and we see the convergence with the notion of "experimental mathematics".<BR/><BR/>So can anyone implement this using CAs?Erdos56https://www.blogger.com/profile/04426474525236405685noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-87542260671879571512008-07-23T01:27:00.000-04:002008-07-23T01:27:00.000-04:00unsigned int gcd(unsigned int u, unsigned int v) {...unsigned int gcd(unsigned int u, unsigned int v) {<BR/> int t = 0;<BR/> while (v != 0)<BR/> {<BR/> t = v;<BR/> v = u % v;<BR/> u = t;<BR/> }<BR/> return t;<BR/>}<BR/><BR/>Seems to be slightly faster though not significantly.<BR/><BR/>$ gcc -O3 -Wall -o primes primes.c && time ./primes >> /dev/null<BR/><BR/>real 0m13.672s<BR/>user 0m13.561s<BR/>sys 0m0.030s<BR/><BR/>$ gcc -O3 -Wall -o primes_euclid primes_euclid.c && time ./primes_euclid >> /de<BR/>v/null<BR/><BR/>real 0m12.224s<BR/>user 0m12.186s<BR/>sys 0m0.062sAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-69674510606443753232008-07-22T23:56:00.000-04:002008-07-22T23:56:00.000-04:00Not sure about this... I'm new to this stuf... but...Not sure about this... I'm new to this stuf... but would the gcd function be faster as an implementation of Euclid's algorithm?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-57747771770049783682008-07-22T21:46:00.000-04:002008-07-22T21:46:00.000-04:00Hah, I guess I should have replied again sooner......Hah, I guess I should have replied again sooner...<BR/><BR/>The optimisation slinky mentions is actually in my current implementation (though I have to admit, was introduced by a friend of mine, when I mentioned this problem to him)<BR/><BR/>I actually also considered gmp to allow for really large numbers, but taking into account the amount of time it takes to calculate the sequence just up to 100.000.000 (well below any number that would require gmp) I figured it would just slow down the whole process for any reasonable application...<BR/><BR/>What really needs improvement, is the gcd-algorithm - I've been reading up on "accelerated integer gcd", and more specifically "sequential accelerated integer gcd" from the paper <A HREF="http://www-lipn.univ-paris13.fr/~sedjelmaci/science3.pdf" REL="nofollow">"Improvements on the accelerated integer GCD algorithm"</A> as it seam either that, or the parallel version from same paper is more or less the best implementation around.<BR/><BR/>I guess if anyone's got a cluster lying around, the parallel version along with gmp might come in handy, but until that, I recommend avoiding gmp, sticking to at most unsigned long long int in C, and just optimizing gcd, which is clearly the bottleneck at this point...The Professorhttps://www.blogger.com/profile/00090522839301386041noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-79425627430044484382008-07-22T19:23:00.000-04:002008-07-22T19:23:00.000-04:00Ok, this is not music everyone can enjoy. I'm hope...Ok, this is not music everyone can enjoy. I'm hopelessly lost. But I'm trying, if that counts for anything!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-55932078814073630162008-07-22T17:04:00.000-04:002008-07-22T17:04:00.000-04:00I made a version which uses the GNU MP multiple pr...I made a version which uses the GNU MP multiple precision arithmetic library, just in case someone wants to run the program until "hell freezes over" and see what kind of prime pops out...<BR/><BR/>You need <A HREF="http://gmplib.org/" REL="nofollow">libgmp</A>.<BR/>You can grab the updated program <A HREF="http://slinky.imukuppi.org/primes3.zip" REL="nofollow">here</A>.<BR/><BR/>Have fun!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-24436424667872005542008-07-22T16:49:00.000-04:002008-07-22T16:49:00.000-04:00freakcers, slinky, http://gist.github.com/1263Seem...freakcers, slinky, <A HREF="http://gist.github.com/1263" REL="nofollow">http://gist.github.com/1263</A><BR/><BR/>Seems like the perfect scenario for testing out the shiny new gist.Ryan Grahamhttps://www.blogger.com/profile/18319610639577200961noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-16426255046133548932008-07-22T15:18:00.000-04:002008-07-22T15:18:00.000-04:00Freakcers, having the cache and the recursive meth...Freakcers, having the cache and the recursive method seemed superfluous, as one only needs two numbers in the sequence to create the next one. Also, when doing so, one does not get limited by the memory with this.<BR/><BR/>I changed the program not to have the aforementioned things, and to skip all 1's, and also to put the two values to register.<BR/><BR/>Although it's not so much faster than your program, it doesn't need a lot of memory.<BR/><BR/>If someone wants to play with it, grab it <A HREF="http://slinky.imukuppi.org/primes2.zip" REL="nofollow">here</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-47533991966244997622008-07-22T12:20:00.000-04:002008-07-22T12:20:00.000-04:00By the way - I've also noticed that every new prim...By the way - I've also noticed that every new prime p that is discovered that is higher than a(1), seem to follow:<BR/>p = a(p)-a(p-1)<BR/><BR/>Dunno if that was an obvious result, but if true, it would mean that the function cannot possibly return all primes - at least not for a single value of a(1)The Professorhttps://www.blogger.com/profile/00090522839301386041noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-50771607837393949362008-07-22T11:37:00.000-04:002008-07-22T11:37:00.000-04:00I've been playing around with the problem in C...I've been playing around with the problem in C (for performance) and my program can calculate the differences of the first 10.000.000 numbers in the sequence in about 6.6 seconds on my amd64(2GHz) - best and worst run:<BR/><BR/>gcc -O3 -Wall -o primes primes.c && time ./primes >> /dev/null<BR/><BR/>real 0m6.321s<BR/>user 0m6.268s<BR/>sys 0m0.048s<BR/><BR/>real 0m6.698s<BR/>user 0m6.628s<BR/>sys 0m0.056s<BR/><BR/>out of curiosity, I modified shawns haskell program (and assuming I didn't break something in the meantime - this is the first time I've seen haskell) this is it's benchmarks - again, best and worst:<BR/><BR/>ghc -O -o shawn primes.hs && time ./shawn >> /dev/null<BR/><BR/>real 0m6.169s<BR/>user 0m6.096s<BR/>sys 0m0.008s<BR/><BR/>real 0m6.394s<BR/>user 0m6.352s<BR/>sys 0m0.032s<BR/><BR/><B>BUT</B> the haskell-version only generates the first <B><I>25</I></B> numbers in the sequence, as opposed to the C-versions <B><I>10.000.000</I></B> (might use less memory, though)<BR/><BR/>Here is the haskell I used:<BR/><A HREF="http://users.skumleren.net/cers/primes/primes.hs" REL="nofollow">primes.hs</A><BR/><BR/>and here is the C-version:<BR/><A HREF="http://users.skumleren.net/cers/primes/primes.c" REL="nofollow">primes.c</A><BR/><BR/>Anyone up for optimizing a bit more? (I suggest looking into a more efficient gcd, perhaps with caching)The Professorhttps://www.blogger.com/profile/00090522839301386041noreply@blogger.comtag:blogger.com,1999:blog-20067416.post-69187430298755239022008-07-21T15:23:00.000-04:002008-07-21T15:23:00.000-04:00there are properties of interest that depend on so...there are properties of interest that depend on something being infinite in a way that can't be approximated with finite objects or is too complex to be computed within reasonable time.<BR/><BR/>if there is a way to test ones hypotheses it can make sense to 'experiment'.<BR/>but often something works for 'generic' objects but not for all. <BR/>for example almost all square matrices are invertible, so if you test this hypothesis by generating square matrices with uniformly random doubles in [-1,1] you will always (very high probability) get an invertible matrix. so the experiment would not help much. as we know the answer already it's obvious how to describe an experiment that shows that some square matrices are not invertible, but if your problem is at the frontier of mathematical knowledge it can be less obvious.<BR/><BR/>for some questions about integer sequences experimenting is very useful, for the poincarĂ© conjecture not so much.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-20067416.post-58381343841106902262008-07-21T13:43:00.000-04:002008-07-21T13:43:00.000-04:00Does it make sense not to be an "experimental math...Does it make sense not to be an "experimental mathematician" nowadays?<BR/><BR/>If so, why?Anonymousnoreply@blogger.com