You are on an infinite Cartesian plane at the origin (0,0). For every integer pair of coordinates (n,m) there's a null-dimensional point (that is, the point has zero width and height).

Some of these are "visible" to you, but some others are "invisible". For example, the point (2,2) is not visible from the origin since it is "blocked" by (1,1). On the other hand, (3,5) is "visible" to you since there are no other points in the way.

Where can you build an "invisible" unit (1x1) square (all four vertices of which are "invisible" points) as near as possible to you - and the origin?

(14, 20), (15, 20), (14, 21), (15, 21)

The first thing to do is find out where the "visible" and "invisible" points are. A point will be visible iff its coordinates are relatively prime, that is, x and y have no common factors. On the same line of reasoning, a point is invisible iff its coordinates have at least one common factor.

Therefore, to make a square, we need to find two consecutive values that have two consecutive common factors. Before we start, let's note a few things:
A prime number n will never have two adjacent invisible points, since its only invisible points will be of the form (x, n) or (n, y) when x or y is a factor of n.
Similarly, any number with only one prime factor (a perfect square, cube, etc) will also only have invisible points when the other coordinate is a multiple of its prime factor.

Therefore, we are looking for two consecutive values that each have more than one prime factor.

  0 - all but (0, ±1) and (±1, 0) are invisible


  1 - all values are visible


  2 - prime


  3 - prime


  4 - perfect square


  5 - prime


* 6 - factors of 2 and 3


  7 - prime


  8 - perfect cube


  9 - perfect square


* 10 - factors of 2 and 5


  11 - prime


* 12 - factors of 2 and 3


  13 - prime


* 14 - factors of 2 and 7


* 15 - factors of 3 and 5

Finally, we have some values.
14 and 15, then, must be the lower of the two sets of coordinates. So, to match 14, the other values will be an odd multiple of 7 and either of the adjacent even numbers; to match 15, we just need adjacent multiples of 3 and 5. So, the odd multiple of 7 needs to also be a multiple of 3 or 5. The smallest way to do this (which is what we are looking for), of course, is just to multiply 3 and 7 to get 21. Happily, we see that one of the neighboring even numbers, 20, is indeed a multiple of 5. So, there is our answer. Also, any reflection or rotation is the same distance from the origin, so there are really eight squares:

( 14,  20), ( 15,  20), ( 14,  21), ( 15,  21)


( 20,  14), ( 21,  14), ( 20,  15), ( 21,  14)


(-14,  20), (-15,  20), (-14,  21), (-15,  21)


(-20,  14), (-21,  14), (-20,  15), (-21,  14)


( 14, -20), ( 15, -20), ( 14, -21), ( 15, -21)


( 20, -14), ( 21, -14), ( 20, -15), ( 21, -14)


(-14, -20), (-15, -20), (-14, -21), (-15, -21)


(-20, -14), (-21, -14), (-20, -15), (-21, -14)

These are all equivalent.

Another way to find these squares is to realize that all we need multiples of four distinct primes. Obviously, this will be minimized if we use the lowest primes (2, 3, 5, 7), so we could have just written out a list of all the numbers that have at least two of these primes as factors:

6, 10, 12, 14, 15, 18, 20, 21 ..

We can stop there.
We have already found two consecutive pairs, 14 and 15, and 20 and 21, the same ones as before, and we didn't have to look far.
We didn't have to look far to find the same answer.
Edited on August 25, 2003, 10:18 pm

Posted by DJ on 2003-08-24 13:00:05