Number Maze

If you really want to try and figure it out, you should probably cover up the rest of the text, so that you don't see the answer by accident. Actually, just in case, I'll go ahead and ramble on a bit more before I say anything important.

As with so many other nice number things, I'm pretty sure I first discovered this pattern in high school. I don't remember what I was thinking that led me to write it down in the first place; what I do remember is that after the fact, I liked thinking of it as a maze. Or, rather, as a dungeon, in the Dungeons & Dragons sense … I imagined climbing down a ladder into the upper left corner, and seeing stone walls extending to infinity in two directions. Then I imagined moving around, square by square; that part probably owed more to Wizardry than to D&D.

Now, having run out of things to ramble on about, I'll tell you the answer. To get the pattern, first let the upper left corner have coordinates (1,1), then fill in all the squares where the coordinates are not relatively prime.

Many interesting and non-obvious facts are made apparent by the pattern, among others the following.

• The first free-standing single block is at (6,12).
• The first enclosed space is at (4,15).
• The first 2×2 block is at (14–15,20–21).

Here are two more facts that are only apparent if you have a larger version.

• The first enclosed space of more than one square is around (9,35).
• The first diagonally enclosed space is at (21,55).

By the way … I'm describing the facts in geometrical terms, but you can equally well think of them in terms of numbers. A block, for example, can be thought of as two sets of numbers such that when you pick one number from each set, the two numbers always have some factor in common. A 2×2 block, then, is one in which the sets consist of two consecutive integers.

Any good math problem suggests many avenues for further inquiry … and the pattern does, too! I happen to like blocks, so that's what I've thought about. Can there be 2×2 spaces? No. Can there be 3×3 blocks? Yes! That was the one great result I worked out, back when I first discovered the pattern. I'll tell you all about the block I found in just a second, but first let me point out some things I still don't know.

Actually, finding a 3×3 block is a very nice puzzle. If you want to try it yourself, now would be a good time to stop reading.

So, anyway … back to things I still don't know.

The 3×3 block I found exists at coordinates (x,y), where x is significantly smaller than y. I know the block is the first in the sense that x is minimal, and that y is minimal given x, but there could well be a block at some other coordinates (u,v) with both u and v smaller than y.

Then there are other block sizes. Where's the first 2×3 block? I sure don't know. Are there larger blocks? I'm pretty sure there must be, but where?

Now let me tell you about the 3×3 block.

The first thing you want to do is assume that the center of the block has odd coordinates. Then the edges will have even coordinates, and all four corners will be filled in by having a factor of 2 in common. (So, there's another question for you: where's the first 3×3 block without an odd center?)

The next thing to do is figure out the first possible coordinate x. We know x has to be odd, so it can only have odd factors, and we know it has to have factors in common with three consecutive integers. But, none of those factors can be the same, because for example you can't have two of three consecutive integers both be divisible by 3. So, x has to have three distinct odd prime factors, and the smallest number with that property is 3×5×7, a.k.a. 105.

So, now we know one of the sets of three consecutive numbers. Here they are, with factorizations.

104 = 2³ × 13
105 = 3 × 5 × 7
106 = 2 × 53

Now we can figure out the other coordinate y. It has to be odd, too, and it has to have factors in common with the three numbers above. So, clearly, it has to be an odd multiple of 13×53 = 689.

With those assumptions, we have (at least) the following common factors.

	104	105	106
y−1	2	?	2
y	13	?	53
y+1	2	?	2

So, all we need to do is find an odd multiple of 689 such that it and its neighbors are all divisible by 3, 5, or 7. There are clever ways of doing that, but trial and error works, too; the only thing I'd like to point out is that as far as divisibility by those three numbers is concerned, it's sufficient to work mod 105. Anyway, however you do it, you get the same result, and that gives you the other set of three consecutive numbers.

6200 = 2³ × 5² × 31
6201 = 3² × 13 × 53
6202 = 2 × 7 × 443

Guess what? The number maze is not quite as useless as I thought. In the lattice of points with integer coordinates, a point can be part of a basis if and only if its coordinates are relatively prime.

Item 48 in HAKMEM talks about the number maze and the first 3×3 block.