Enigmatic Code

Programming Enigma Puzzles

Enigma 136: Twelve-point square

From New Scientist #1280, 19th November 1981 [link]

“Take a large sheet of ordinary graph-paper,” said Professor Mortis, “and draw a circle with centre at any point you like. Now mark with a tiny blob any place where the circle exactly cuts one of the juncs of the graph-paper. … What? … A junc is where a north-south line cuts an east-west line, of course. … Right. … Then cut out any square you like from the graph paper. … Yes, the square can be of any size and orientation you choose… Next, count the blobs on the square. … Yes, a blob on the edge counts as on the square. … If there are fewer than 12 blobs, start again. But if there are 12 or more blobs, work out the area of the square.”

If the graph-paper is ruled at 1cm intervals, what is the smallest area I can end up with?

[enigma136]

3 responses to “Enigma 136: Twelve-point square

  1. Jim Randell 15 October 2013 at 9:27 am

    I didn’t solve this one programatically.

    Solution: The smallest square has an area of 45 cm².

    The smallest circle that passes through 12 lattice points has radius r = 5/√2 (≈ 3.54), and is centred at a point in the middle of a grid square. (See [ http://demonstrations.wolfram.com/LatticeCircles/ ]).

    So by enclosing this circle in a square we can manage a square with area (2r)² = 50 cm².

    However, we don’t need to enclose the entire circle in the square, just the lattice points. The red square in the diagram below has 8 of the lattice points on the edge of a square with edge length 7, and so has an area of 49 cm².

    Enigma 136

    But the blue square also has 8 of the lattice points on the edge of the square and has an area of 45 cm².

    • Jim Randell 6 October 2014 at 7:26 pm

      Wolfram Alpha has an interesting page on Lattice Circles [ http://mathworld.wolfram.com/CircleLatticePoints.html ].

      Based on the observation that any three points define a circle, and we only need to consider Lattice Circles whose centre lies within the triangle defined by (0, 0), (1/2, 0), (1/2, 1/2), this program produces lattice circles of increasing radius by looking at lattice points within a certain distance of this triangle and then choosing three of the potential lattice points, finding out where the centre of the circle defined by those points lies, and if it is within the required triangle we determine how many of the potential lattice points are at the same distance.

      The lattice circles for each radius interval are collected and returned in order of increasing radius size, then the interval is increased to find the next batch of circles, and so on, until we find the first circle with the required number of lattice points.

      The program uses the best implementation of rational numbers it can find. I found that using gmpy rationals under CPython was faster than using Python rationals under PyPy.

      from itertools import count, product, combinations
      from enigma import irange, sqrt, printf
      
      # choose an appropriate fractions implementation as F
      # (could also try 'sympy.Rational', but not for speed)
      for s in ('gmpy2.mpq', 'gmpy.mpq', 'fractions.Fraction'):
        (mod, fn) = s.split('.', 2)
        try:
          t = __import__(mod)
        except ImportError:
          continue
        else:
          F = t.__dict__[fn]
          printf("[using {s}]")
          break
      
      # 1/2
      h = F(1, 2)
      
      # points that define the target triangle
      pts = [(0, 0), (h, h), (h, 0)]
      
      # generate circles of increasing size
      def generate(s=1):
        for z in count(s):
          # min/max distance (squared)
          (m, M) = ((z - 1) ** 2, z ** 2)
      
          # collect lattice points
          lattice = list()
          for (x, y) in product(irange(-z, z), repeat=2):
            for (x0, y0) in pts:
              d2 = (x - x0) ** 2 + (y - y0) **2
              if m <= d2 < M:
                lattice.append((x, y))
                break
      
          printf("[checking radius < {z}] [{n} lattice points] ...", n=len(lattice))
      
          # accumulate results
          r = list()
          seen = dict()
      
          # choose three lattice points
          for ((x1, y1), (x2, y2), (x3, y3)) in combinations(lattice, 3):
            # the parameters for the perpendicular bisector of p1 and p2 (Ax + By = C)
            A1 = 2 * (x2 - x1)
            B1 = 2 * (y2 - y1)
            C1 = (x1 ** 2 - x2 ** 2) + (y1 ** 2 - y2 ** 2)
            # the parameters for the perpendicular bisector of p1 and p3 (Ax + By = C)
            A2 = 2 * (x3 - x1)
            B2 = 2 * (y3 - y1)
            C2 = (x1 ** 2 - x3 ** 2) + (y1 ** 2 - y3 ** 2)
            # do they intersect in the triangle?
            d = A1 * B2 - A2 * B1
            if d == 0: continue
            y0 = F(A2 * C1 - A1 * C2, d)
            if not(0 <= y0 <= h): continue
            x0 = F(B1 * C2 - B2 * C1, d)
            if not(y0 <= x0 <= h): continue
      
            # work out the radius of the circle
            r2 = (x0 - x1) ** 2 + (y0 - y1) ** 2
            if not(m <= r2 < M): continue
            # find the indices of points with the same distance
            ps = tuple(i for (i, (x, y)) in enumerate(lattice) if (x0 - x) ** 2 + (y0 - y) ** 2 == r2)
            if ps in seen: continue
            seen[ps] = 1
            # return (radius squared, centre, num points, points)
            r.append((r2, x0, y0, len(ps), tuple(lattice[i] for i in ps)))
      
          # return the circles by size
          for s in sorted(r, key=lambda x: x[0]):
            yield s
      
      # target number of lattice points
      import sys
      N = (12 if len(sys.argv) < 2 else int(sys.argv[1]))
      
      # consider circles, output the smallest for each n
      seen = dict()
      for (r2, x0, y0, n, ps) in generate():
        if n not in seen:
          printf("n={n} r={r} (r^2={r2}) ({x0}, {y0}) {ps}", r=sqrt(r2))
          seen[n] = 1
        if n == N: break
      

      This program finds a minimal sized circle with 12 lattice points in 88ms, and confirms that it has a radius of 5/√2, and is centred at (1/2, 1/2), and matches the diagram given above.

      Consequently I've moved this puzzle from the "Not Solved Programatically" section of the "Notable Enigmas" page to the "Partial Programmatic Solution" section.

      I've used (a variation on – see below) this program to check circles up to a radius of 1800 and here's a table of the minimal Lattice Circles I've found so far:

        n      r       r²              centre
      [ 0      0       0               (1/2, 1/2) (or any non-lattice point) ]
      [ 1      0       0               (0, 0) ]
      [ 2      0.5     1/4             (1/2, 0) ]
        3      1.179   25/18           (1/6, 1/6)
        4      0.707   1/2             (1/2, 1/2)
        5      5.892   625/18          (1/6, 1/6)
        6      2.5     25/4            (1/2, 0)
        7     23.891   138125/242      (9/22, 5/22)
        8      1.581   5/2             (1/2, 1/2)
        9     15.321   4225/18         (1/6, 1/6)
       10     12.5     625/4           (1/2, 0)
       11     57.536   801125/242      (5/22, 3/22)
       12      3.536   25/2            (1/2, 1/2)
       13    111.622   1221025/98      (1/14, 1/14)
       14     62.5     15625/4         (1/2, 0)
       15     76.603   105625/18       (1/6, 1/6)
       16      5.701   65/2            (1/2, 1/2)
       17    567.076   185870425/578   (9/34, 1/34)
       18     32.5     4225/4          (1/2, 0)
       19    567.076   185870425/578   (13/34, 7/34)
       20     17.678   625/2           (1/2, 1/2)
       21    349.980   29641625/242    (5/22, 1/22)
       22    349.980   29641625/242    (1/2, 9/22)
       23    558.109   30525625/98     (5/14, 5/14)
       24     12.748   325/2           (1/2, 1/2)
       25    995.842   17850625/18     (1/6, 1/6)
       26    601.102   35409725/98     (1/2, 3/14)
       27    260.451   1221025/18      (1/6, 1/6)
       28     88.388   15625/2         (1/2, 1/2)
       29   2091.997   3159797225/722  (13/38, 5/38) or (15/38, 11/38)
       30    162.5     105625/4        (1/2, 0)
       32     23.505   1105/2          (1/2, 1/2)
       36     45.962   4225/2          (1/2, 1/2)
       40     63.738   8125/2          (1/2, 1/2)
       42    812.5     2640625/4       (1/2, 0)
       43   2240.966   1215306625/242  (3/22, 1/22)
       44   2209.708   9765625/2       (1/2, 1/2)
       45   1302.255   30525625/18     (1/6, 1/6)
       48     52.560   5525/2          (1/2, 1/2)
       50   2112.5     17850625/4      (1/2, 0)
       52   3656.361   1310159825/98   (3/14, 3/14)
       54    552.5     1221025/4       (1/2, 0)
       56    318.689   203125/2        (1/2, 1/2)
       60    229.810   105625/2        (1/2, 1/2)
       64    117.527   27625/2         (1/2, 1/2)
       72    189.506   71825/2         (1/2, 1/2)
       80    262.797   138125/2        (1/2, 1/2)
       81   7553.079   1026882025/18   (1/6, 1/6)
       84   1149.049   2640625/2       (1/2, 1/2)
       88   7967.218   126953125/2     (1/2, 1/2)
       90   2762.5     30525625/4      (1/2, 0)
       96    283.042   160225/2        (1/2, 1/2)
      100   2987.526   17850625/2      (1/2, 1/2)
      108    781.353   1221025/2       (1/2, 1/2)
      112   1313.987   3453125/2       (1/2, 1/2)
      120    947.530   1795625/2       (1/2, 1/2)
      128    632.900   801125/2        (1/2, 1/2)
      144   1020.521   2082925/2       (1/2, 1/2)
      160   1415.207   4005625/2       (1/2, 1/2)
      168   4737.648   44890625/2      (1/2, 1/2)
      180   3906.765   30525625/2      (1/2, 1/2)
      192   1721.674   5928325/2       (1/2, 1/2)
      216   4207.715   35409725/2      (1/2, 1/2)
      224   7076.038   100140625/2     (1/2, 1/2)
      240   5102.604   52073125/2      (1/2, 1/2)
      256   3849.781   29641625/2      (1/2, 1/2)
      288   6207.585   77068225/2      (1/2, 1/2)
      320   8608.372   148208125/2     (1/2, 1/2)
      384  11024.095   243061325/2     (1/2, 1/2)

      Note that the minimal circles with 17 and 19 points have the same radius, as do the minimal circles with 21 and 22 points.

      Using a different program which checks for lattice circles with a known centre (which is much faster), I’ve checked all the centres found above up to (at least) radius 5000, and here are additional lattice circles that I’ve found where n ≤ 100 or r ≤ 100,000, but I can’t guarantee that these are the smallest possible radius:

        n       r       r²                   centre
       31    2790.546   763140625/98         (3/14, 3/14)
       33    2883.211   1346691125/162       (7/18, 1/6)
       34    4429.005   11338095925/578      (1/2, 15/34)
       35    4979.210   446265625/18         (1/6, 1/6)
       37    3912.896   3705203125/242       (9/22, 1/22)
       38    3912.896   3705203125/242       (1/2, 7/22)
       39    3237.034   1026882025/98        (1/14, 1/14)
       41    4576.496   2052543025/98        (1/14, 1/14)
       46    3005.510   885243125/98         (1/2, 1/14)
       47   16543.733   132468422125/484     (2/11, 1/22)
       49   15585.947   175389495125/722     (11/38, 1/38)
       51    9445.224   64411251125/722      (5/38, 1/38) or (13/38, 3/38)
       53    5010.952   6076533125/242       (7/22, 1/22)
       55   16469.488   69438470725/256      (3/8, 1/16)
       57   15229.966   167469252925/722     (15/38, 5/38)
       58   15229.966   167469252925/722     (7/38, 7/38) or (13/38, 9/38)
       59   23525.749   399598746625/722     (17/38, 5/38)
       61   41593.921   837346264625/484     (3/22, 1/11)
       62   15027.552   22131078125/98       (7/14, 5/14)
       63    6511.275   763140625/18         (1/6, 1/6)
       65   45187.994   2160388179625/1058   (7/46, 3/46)
       66   16185.169   25672050625/98       (1/2, 1/14)
       67   22882.481   51313575625/98       (5/14, 5/14)
       68   22882.481   51313575625/98       (1/2, 1/14)
       69   16185.169   25672050625/98       (5/14, 5/14)
       70   10562.5     446265625/4          (1/2, 1/2)
       71   87514.165   8102935391525/1058   (9/46, 3/46)
       73   84669.851   12058230426125/1682  (15/58, 7/58)
       74   25054.761   151913328125/242     (3/22, 3/22)
       75   16929.315   5158830625/18        (1/6, 1/6)
       76   30560.696   226017390625/242     (9/22, 9/22)
       77   32990.750   785817263725/722     (7/38, 5/38) or (15/38, 1/38)
       78   19690.108   37994634925/98       (1/2, 5/14)
       79   56195.930   2280063436625/722    (17/38, 9/38)
       82   24645.186   59523747725/98       (1/2, 3/14)
       83   93006.835   4186731323125/484    (5/11, 3/22)
       85   16314.478   64411251125/242      (9/22, 3/22)
       86   16314.478   64411251125/242      (1/22, 1/22)
       87   62794.760   2846977299725/722    (11/38, 5/38)
       89   82347.439   1735961768125/256    (5/16, 1/8)
       91   82347.439   1735961768125/256    (3/8, 5/16)
       92   18281.806   32753995625/98       (1/14, 1/14)
       93   80925.846   641801265625/98      (3/14, 3/14)
       94  114412.403   1282839390625/98     (1/2, 5/14)
       95  114412.403   1282839390625/98     (3/14, 3/14)
       97  157834.878   26356735791425/1058  (9/46, 1/46)
       98  137312.5     75418890625/4        (1/2, 0)
       99  141578.125   1282839390625/64     (1/8, 0)
      101   99798.754   7190969300125/722    (13/38, 11/38)
      102   73769.559   3929086318625/722    (13/38, 7/38) or (1/2, 3/38)
      103   73769.559   3929086318625/722    (17/38, 9/38)
      104   26618.712   69438470725/98       (1/14, 1/14)
      105   84646.574   128970765625/18      (1/6, 1/6)
      106   36480.282   322056255625/242     (7/22, 7/22)
      107   36480.282   322056255625/242     (3/22, 1/22)
      124   91409.032   818849890625/98      (5/14, 5/14)
      126   13812.5     763140625/4          (1/2, 0)
      132   28726.213   1650390625/2         (1/2, 1/2)
      135   37765.395   25672050625/18       (1/6, 1/6)
      138   98450.540   949865873125/98      (1/2, 3/14)
      140   14937.631   446265625/2          (1/2, 1/2)
      150   35912.5     5158830625/4         (1/2, 0)
      162   16022.5     1026882025/4         (1/2, 0)
      176   32849.681   2158203125/2         (1/2, 1/2) 
      200   12317.886   303460625/2          (1/2, 1/2)
      252   19533.825   763140625/2          (1/2, 1/2)
      270   80112.5     25672050625/4        (1/2, 0)
      280   61589.429   7586515625/2         (1/2, 1/2)
      300   50787.945   5158830625/2         (1/2, 1/2)
      324   22659.237   1026882025/2         (1/2, 1/2)
      336   25513.018   1301828125/2         (1/2, 1/2)
      360   21038.573   885243125/2          (1/2, 1/2)
      400   66333.846   8800358125/2         (1/2, 1/2)
      432   25594.529   1310159825/2         (1/2, 1/2)
      448   43041.858   3705203125/2         (1/2, 1/2)
      480   31037.925   1926705625/2         (1/2, 1/2)
      512   24650.625   1215306625/2         (1/2, 1/2)
      576   39747.938   3159797225/2         (1/2, 1/2)
      640   55120.473   6076533125/2         (1/2, 1/2)
      768   80256.620   12882250225/2        (1/2, 1/2)

      The numerators of the squared radii in the smallest circles I’ve found (so far) are all products of powers of 5, 13, 17 and 29. These are all primes of the form (4k + 1), known as Pythagorean Primes.

      I’m keeping a full list of lattice circles that I’ve found at [ https://github.com/enigmatic-code/lattice_circles ].

      • Jim Randell 20 February 2016 at 6:41 am

        The program given above works OK when the radius is small, but as the radius gets larger it soon gets bogged down.

        The following program is a refinement of the method used in the program above that considers fewer of the lattice points when searching for circles, and so runs much faster. (I’ve used it to increase the search space for the minimal lattice circles given above).

        For example, if we are looking for lattice circles with 9 or more points on the circumference, then we can consider dividing the circle into quadrants. One of those quadrants must contain 3 of the lattice points, and this is enough to define the circle. So we can reduce the number of lattice points we consider when looking for lattice circles with more than a certain number of points. In general if we consider a 1/k sector of the circle, it must contain 3 or more points for any lattice circle with 2k + 1 or more points. So as we find minimal circles we can reduce the size of the sector we consider.

        The circles we find by this method may not have their centres in the canonical format (0 ≤ yx ≤ ½), but by reflecting the circle in one or more of the lines x = ½, y = ½, x = y (which don’t change the position of lattice points) we can find an equivalent circle centred in the required triangle.

        from itertools import count, product, combinations
        from enigma import irange, sqrt, printf
        
        # choose an appropriate fractions implementation as F
        # (could also try 'sympy.Rational', but not for speed)
        for s in ('gmpy2.mpq', 'gmpy.mpq', 'fractions.Fraction'):
          (mod, fn) = s.split('.', 2)
          try:
            t = __import__(mod)
          except ImportError:
            continue
          else:
            F = t.__dict__[fn]
            printf("[using {s}]")
            break
        
        # 1/2
        h = F(1, 2)
        
        # centre of the square and distance from it
        (xt, yt, rt2) = (h, h, h)
        
        # command line arguments:
        # N = target number of lattice points (can be 0)
        # s = radius to start from
        import sys
        argv = sys.argv[1:]
        N = (12 if len(argv) < 1 else int(argv[0]))
        s = ( 1 if len(argv) < 2 else int(argv[1]))
        
        # canonical position of centres
        def canonical(x, y):
          (x, y) = (x % 1, y % 1)
          if y > h: y = 1 - y
          if x > h: x = 1 - x
          if y > x: (x, y) = (y, x)
          return (x, y)
        
        # record the smallest circle
        r = dict()
        
        # the smallest circle we haven't found yet
        nmin = 3
        
        for z in count(s):
          # min/max distance (squared)
          (m2, M2) = ((z - 1) ** 2, z ** 2)
        
          # collect lattice points
          lattice = list()
          for (x, y) in product(irange(-z, z), repeat=2):
            # calculate distances
            (x0, y0, x1, y1) = (x ** 2, y ** 2, (x - 1) ** 2, (y - 1) ** 2)
            if any(m2 <= d2 < M2 for d2 in (x0 + y0, x0 + y1, x1 + y0, x1 + y1)):
              lattice.append((x, y))
        
          # we only need to check points in one sector of the circle
          while nmin in r: nmin += 1
          if nmin > 16:
            (k, check) = (8, list((x, y) for (x, y) in lattice if not(y < 0 or x < 0 or x + 1 < y)))
          elif nmin > 8:
            (k, check) = (4, list((x, y) for (x, y) in lattice if not(y < 0 or x < 0)))
          elif nmin > 4:
            (k, check) = (2, list((x, y) for (x, y) in lattice if not(y < 0)))
          else:
            (k, check) = (1, lattice)
        
          printf("[checking radius < {z}] [nmin={nmin}] [{n} points in 1/{k} sector] ...", n=len(check))
        
          # choose two lattice points
          p = len(check)
          for (i, j) in combinations(irange(0, p - 2), 2):
            ((x1, y1), (x2, y2)) = (check[i], check[j])
            # the parameters for the perpendicular bisector of p1 and p2 (Ax + By = C)
            a1 = 2 * (x2 - x1)
            b1 = 2 * (y2 - y1)
            c1 = (x1 ** 2 - x2 ** 2) + (y1 ** 2 - y2 ** 2)
            # does it pass through the origin square
            d2 = F(((a1 * xt) + (b1 * yt) + c1) ** 2, a1 ** 2 + b1 ** 2)
            if d2 > rt2: continue
        
            # choose the remaning lattice point
            for k in irange(j + 1, p - 1):
              (x3, y3) = check[k]
              # the parameters for the perpendicular bisector of p1 and p3 (Ax + By = C)
              a2 = 2 * (x3 - x1)
              b2 = 2 * (y3 - y1)
              # check they are not parallel
              d = a1 * b2 - a2 * b1
              if d == 0: continue
              c2 = (x1 ** 2 - x3 ** 2) + (y1 ** 2 - y3 ** 2)      
              # do they intersect in the square
              y0 = F(a2 * c1 - a1 * c2, d)
              if not(0 <= y0 <= 1): continue
              x0 = F(b1 * c2 - b2 * c1, d)
              if not(0 <= x0 <= 1): continue
              # work out the radius of the circle
              r2 = (x0 - x1) ** 2 + (y0 - y1) ** 2
              if not(m2 <= r2 < M2): continue
        
              # count lattice points with the same distance
              n = sum(1 for (x, y) in lattice if (x0 - x) ** 2 + (y0 - y) ** 2 == r2)
              if n not in r or r2 < r[n][0]:
                # record (distance squared, canonical centre)
                (x0, y0) = canonical(x0, y0)
                r[n] = (r2, x0, y0)
                printf("-> n={n} r={r} (r^2={r2}) ({x0}, {y0})", r=sqrt(r2))
        
          # have we found the required circle?
          if N in r:
            (r2, x0, y0) = r[N]
            printf("n={N} r={r} (r^2={r2}) ({x0}, {y0})", r=sqrt(r2))
            break
        

        So, when the program is run to find minimal lattice circles. It starts by considering the entire circle, until circles with 3 and 4 points have been found (the one with 3 points has the largest radius), it then switches to considering half of the circle until circles with 5, 6, 7 and 8 points have been found (the one with 7 points has the largest radius), then it switches to considering one quarter of the circle until minimal circles from 9 to 16 points have been found (the one with 13 points has the largest radius), at which stage it can switch to considering just one eighth of the circle.

        In fact, this program was able to find all minimal lattice circles with r < 200 in about an hour, something that would take my first program many days.

        Another approach I tried was to consider a lattice circle with origin at a rational point. Then by scaling up the circle by the common denominator of the coordinates of the centre we get a larger circle that is centred on a lattice point, and each lattice point that was on the original circle corresponds to a lattice point on the larger circle (although there may be extra lattice points on the larger circle). So, we can find lattice circles by looking for those centred on a lattice point and scaling them down and translating them appropriately. This boils down to finding positive integers that are expressed as the sum of two squares (possibly in multiple ways). While this does give a method of generating lattice circles, I didn’t see an easy way to be sure I’d found a minimal lattice circle, so I didn’t explore this approach further.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: