mersenneforum.org Prime squares/rectangles
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-03, 16:05 #1 roger     Oct 2006 22×5×13 Posts Prime squares/rectangles On Henri Lifchitz's webpage, he describes what he calls primes in network. http://ourworld.compuserve.com/homep...z/Homepage.htm I have enough basic programming to understand that a program could be made to search for these easily, but I don't have enough to make it myself. By hand, I have only been able to make two: 1 ...7 13...................41 71 101 31 37 43......and......137 167 197 61 67 73.................233 263 293 [Objectionable] I'm not asking outright, please make one, but I think a quick search for these could be interesting. At the very least, it will help with basic understanding of these kind of patterns for people like me Roger
 2007-05-03, 16:39 #2 grandpascorpion     Jan 2005 Transdniestr 503 Posts 1 isn't a prime
 2007-05-03, 17:04 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18EF16 Posts I've found a 4x4 with the smallest-possible top left entry; let x=0..3 y=0..3 in 7 + 100062*x + 209220*y Other small top-lefts come from 11+38640*x+111570*y, 13+72030*x+130350*y 17+11532x+34650y, 23+16170x+57228y. Smallest bottom-right, which I expect to be minimal, is 2089 (199 + 210*x + 420*y). Smallest bottom-right for a given top-left is well-defined; can anyone manage a better bottom-right for top-left=17 than 138563? Haven't found a 5x5 yet; there aren't any with smallest difference less than 25000 and largest number less than 16 million. Have found a few 5x4 grids, amonst them: 71 + 210x + 86790y 113 + 630x + 4128y 607 + 1140x + 2310y Is there an obvious way of finding arithmetic progressions in a set of N numbers in time less than N^2 log N [sort list, for each a,b check whether 2a-b, 3a-2b ... in list taking advantage of sortedness] ? Code: `#include #include #include using std::endl; using std::cout; using std::vector; using std::set; using std::flush; using std::cerr; int main(void) { int B=1000,A=B*B; const int CT = 4; vector num(A); for (int r=4; r starts; for (int c=2; c toad; for (set::iterator frog = starts.begin(); frog != starts.end(); frog++) toad.push_back(*frog); for (int i=0; i b) { bool happy = true; for (int c=2; c
 2007-05-03, 18:21 #4 grandpascorpion     Jan 2005 Transdniestr 503 Posts If you are looking for a 5x5 grid, thru some prime limit P, I would sieve out any mod values for X, Y and S (starting value) such that S + aX + bY == 0 (mod p) where p is any prime <= P, 0<=a<=4, 0<=b<=4 and S + aX + bY > p Case in point (one of your 5x4 solutions above): X=210, Y=86790, S=71, p =23 71%23 + 0*(210%23) + 4*(86790%23) = 0 (mod 23) You could pre-compute such values and then use the Chinese remainder theorem to find viable triples Last fiddled with by grandpascorpion on 2007-05-03 at 18:26
 2007-05-03, 19:41 #5 grandpascorpion     Jan 2005 Transdniestr 503 Posts One simple to see result is that for 5x5 prime square, x and y must be multiples of 30. In general, X and Y must not divide S either of course. Last fiddled with by grandpascorpion on 2007-05-03 at 20:30
 2007-05-04, 00:37 #6 roger     Oct 2006 4048 Posts Thank you all! With regards to the multiples of 30, this is true yes, but also holds for some numbers with a six at the end. [eg 16, 26, 36 etc - note these don't work for the small numbers I've tried] This is because six is a common gap between primes? (Although sometimes having primes within that gap) Roger
 2007-05-04, 01:16 #7 grandpascorpion     Jan 2005 Transdniestr 503 Posts I was speaking directly about a 5x5 prime square which hasn't been found yet. You have to have gaps that are a multiple of 30. A number ending in 6 has nothing to do with a prime gap of 6. Sorry, but it's kind of frightening to read that in a math forum. Last fiddled with by grandpascorpion on 2007-05-04 at 01:33
 2007-05-04, 08:49 #8 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 13×491 Posts 5x5 prime squares Same code as above, require b to be a multiple of 30, increase limits a bit (primes up to 2^28), run overnight. I think I probably need a better idea to get to 6*6; there'll be a medium-sized constant factor in replacing the set with a hashtable, and 1GB holds a one-bit-per-odd-number table up to 10^10 which might suffice. [though finding the rows isn't the problem, and I have no better idea for the row-combining problem than my current one ... I can speed it up a bit with some modular tests, but I don't think I can actually *sieve* as such since the Y values are all implicit] Anyway, the 5x5 squares: S,X,Y = 14933623 30030 60060 [this one is a bit inelegant because it has equal entries!] 32188979 42900 18752580} these two make a 5x6! 50941559 42900 18752580} 54817403 28350 19538610 118965919 32340 22894200 File attached is a plot of delta against 'number of arithmetic progressions of five primes <2^28 with common difference delta'; lots of pretty modular patterns there. 30030 is unsurprisingly a very fertile delta, 510510 will probably be even better if I leave the run long enough to get there. Attached Thumbnails   Last fiddled with by fivemack on 2007-05-04 at 09:18 Reason: noticed 5x6!
 2007-05-04, 11:42 #9 grandpascorpion     Jan 2005 Transdniestr 503 Posts That's true if you do X and/or Y multiples of 30030, 510510, etc, you will have more progressions. Looking at this a bit, you don't necessarily need those if you are doing some modular checking though. I would at least implement a 7 check, for instance (to get a 5x5 grid): if S == 1 (mod 7): if X= 0 (mod 7), Y = 0,1,4 (mod 7) if X= 1 (mod 7), Y = 0 (mod 7) if X= 4 (mod 7), Y = 0 (mod 7) Last fiddled with by grandpascorpion on 2007-05-04 at 11:53
 2007-05-04, 13:36 #10 grandpascorpion     Jan 2005 Transdniestr 1111101112 Posts The more that I think about this, a hybrid approach is probably wiser. Using your code to find primes in a.p of a desired length j (or perhaps canned lists of primes in a.p (does a website exist)) , pick possible candidates using my modular approach through some p and then find all the set of moduli for p primorial such that all S + aX + bY is p-unsmooth for a=0..j-1, b=0..j-1 You could generalize this to rectangles easily as well.
 2007-05-04, 16:07 #11 roger     Oct 2006 26010 Posts Quote: A number ending in 6 has nothing to do with a prime gap of 6. Sorry, but it's kind of frightening to read that in a math forum. Sorry about that, I don't even know what I was trying to say. Turning on my brain now... This has gone way over my head now, so I'll just but out and let the experts take it away! Thanks for your help, now I get the basic stuff! Roger

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 42 2017-02-03 01:29 fivemack Miscellaneous Math 11 2011-06-29 02:09 Damian Math 3 2010-05-24 23:57 Dougy Math 3 2010-02-16 10:20 m_f_h Puzzles 45 2007-06-15 17:46

All times are UTC. The time now is 13:39.

Fri May 7 13:39:11 UTC 2021 up 29 days, 8:20, 0 users, load averages: 2.53, 2.64, 2.52