20070503, 16:05  #1 
Oct 2006
2^{2}×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 
20070503, 16:39  #2 
Jan 2005
Transdniestr
503 Posts 
1 isn't a prime

20070503, 17:04  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
18EF_{16} Posts 
I've found a 4x4 with the smallestpossible top left entry; let x=0..3 y=0..3 in
7 + 100062*x + 209220*y Other small toplefts come from 11+38640*x+111570*y, 13+72030*x+130350*y 17+11532x+34650y, 23+16170x+57228y. Smallest bottomright, which I expect to be minimal, is 2089 (199 + 210*x + 420*y). Smallest bottomright for a given topleft is welldefined; can anyone manage a better bottomright for topleft=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 2ab, 3a2b ... in list taking advantage of sortedness] ? Code:
#include <vector> #include <iostream> #include <set> 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<unsigned char> num(A); for (int r=4; r<A; r+=2) num[r]=1; for (int r=3; r<B; r+=2) for (int s=r*r; s<A; s+=2*r) num[s]=1; for (int b=6; b<A; b+=2) { set<int> starts; for (int c=2; c<A3*b; c++) { bool happy = true; for (int k=0; k<CT && happy; k++) if (num[c+k*b]==1) happy=false; if (happy) starts.insert(c); } cerr << b << " " << starts.size()<<" \r"<<flush; vector<int> toad; for (set<int>::iterator frog = starts.begin(); frog != starts.end(); frog++) toad.push_back(*frog); for (int i=0; i<toad.size(); i++) for (int j=i+1; j<toad.size(); j++) { int left = toad[i], right=toad[j]; if (rightleft > b) { bool happy = true; for (int c=2; c<CT && happy; c++) if (starts.find(left+c*(rightleft)) == starts.end()) happy=false; if (happy) cout << left << " " << b << " " << rightleft << endl; } } } } Last fiddled with by fivemack on 20070503 at 17:08 Reason: add source code, point out that 7 is smallest possible 
20070503, 18:21  #4 
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 precompute such values and then use the Chinese remainder theorem to find viable triples Last fiddled with by grandpascorpion on 20070503 at 18:26 
20070503, 19:41  #5 
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 20070503 at 20:30 
20070504, 00:37  #6 
Oct 2006
404_{8} 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 
20070504, 01:16  #7 
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 20070504 at 01:33 
20070504, 08:49  #8 
(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 mediumsized constant factor in replacing the set<int> with a hashtable, and 1GB holds a onebitperoddnumber table up to 10^10 which might suffice. [though finding the rows isn't the problem, and I have no better idea for the rowcombining 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. Last fiddled with by fivemack on 20070504 at 09:18 Reason: noticed 5x6! 
20070504, 11:42  #9 
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 20070504 at 11:53 
20070504, 13:36  #10 
Jan 2005
Transdniestr
111110111_{2} 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 punsmooth for a=0..j1, b=0..j1 You could generalize this to rectangles easily as well. 
20070504, 16:07  #11 
Oct 2006
260_{10} 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Regarding Squares  a1call  Miscellaneous Math  42  20170203 01:29 
parsimonious squares  fivemack  Miscellaneous Math  11  20110629 02:09 
Sum of reciprocal of squares of all prime numbers  Damian  Math  3  20100524 23:57 
Counting Latin rectangles  Dougy  Math  3  20100216 10:20 
squares or not squares  m_f_h  Puzzles  45  20070615 17:46 