mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-05-03, 16:05   #1
roger
 
roger's Avatar
 
Oct 2006

22×5×13 Posts
Default 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
roger is offline   Reply With Quote
Old 2007-05-03, 16:39   #2
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

1 isn't a prime
grandpascorpion is offline   Reply With Quote
Old 2007-05-03, 17:04   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18EF16 Posts
Default

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 <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<A-3*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 (right-left > b)
              {
                bool happy = true;
                for (int c=2; c<CT && happy; c++)
                  if (starts.find(left+c*(right-left)) == starts.end())
                    happy=false;
                if (happy)
                  cout << left << " " << b << " " << right-left << endl;
              }
          }
    }
}

Last fiddled with by fivemack on 2007-05-03 at 17:08 Reason: add source code, point out that 7 is smallest possible
fivemack is offline   Reply With Quote
Old 2007-05-03, 18:21   #4
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2007-05-03, 19:41   #5
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2007-05-04, 00:37   #6
roger
 
roger's Avatar
 
Oct 2006

4048 Posts
Default

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
roger is offline   Reply With Quote
Old 2007-05-04, 01:16   #7
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2007-05-04, 08:49   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default 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<int> 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
Click image for larger version

Name:	ng.png
Views:	218
Size:	8.0 KB
ID:	1701  

Last fiddled with by fivemack on 2007-05-04 at 09:18 Reason: noticed 5x6!
fivemack is offline   Reply With Quote
Old 2007-05-04, 11:42   #9
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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
grandpascorpion is offline   Reply With Quote
Old 2007-05-04, 13:36   #10
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Old 2007-05-04, 16:07   #11
roger
 
roger's Avatar
 
Oct 2006

26010 Posts
Default

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
roger is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Regarding Squares a1call Miscellaneous Math 42 2017-02-03 01:29
parsimonious squares fivemack Miscellaneous Math 11 2011-06-29 02:09
Sum of reciprocal of squares of all prime numbers Damian Math 3 2010-05-24 23:57
Counting Latin rectangles Dougy Math 3 2010-02-16 10:20
squares or not squares 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.