Odds and Ends

Once I'd written the necessary code to find the minimal blocks, it was relatively easy to make it do other things as well. One thing I made it do was find the first adjacent pair of odd numbers with three distinct factors.

663 = 3 × 13 × 17
665 = 5 × 7 × 19

See how the numbers use six of the first seven odd primes?

Why do we care about those numbers? Well, as I mentioned earlier, we can use them to find the first 3×3 block with an even center coordinate x.

Here and below, when I talk about the first of a set of points, I always mean the point with the smallest value of x, regardless of y. In other words, I'm measuring using the function x. The function min(x,y) would be a strange choice here, since the set of points doesn't have reflection symmetry.

This time, instead of solving the whole problem all at once, let's solve a problem for each value of x that's involved, then combine those results.

The separate problems are actually pretty easy to solve. In fact, we've solved one already, back in The Next Block … remember when we found the six possible values for m × 145? The same method applies here. For 663, for example, we can just step through the multiples of the largest factor, 17, and look at the nearby numbers mod 13 and mod 3 until we find the six places where there are blocks of three. Actually, we only need to find two places, because the sum of the first two gives the third, and the negatives of those three (mod 663) give the rest.

Here are the results for several values of x.

661	prime
662	2 331	331		mod 662
663	3 13 17	169 170 339	494 493 324	663
664	23 83	83		166
665	5 7 19	20 56 76	645 609 589	665
666	2 32 37	lots		222
667	23 29

Now we can combine the results. There are three rows we're interested in. If we pick an element from each row, we get a set of simultaneous congruences, e.g.,

y ≡ 169	mod 663
y ≡ 83	mod 166
y ≡ 20	mod 665.

We can solve those equations for y, and when we do, we know the location of a 3×3 block. So, all we need to do is try all possible combinations of elements and take the smallest value of y, and we're done!

By the way, trying all possible combinations isn't as gruesome as it sounds. You can save a lot of effort by representing the negative elements as actual negative numbers, and by making use of the fact that the elements can be added together. Even better, if you multiply the elements by the Green's functions (see below), you can often figure out which combination will produce the smallest value of y. (That probably won't make any sense to you unless you're actually doing the calculation. Sorry!)

Now the only piece that's missing is that we need to figure out how to solve a set of simultaneous congruences. But, guess what? We've done that already, too, this time in the essay An Example. It's part of a larger essay, but you can ignore all of that and just skip to about halfway down. Basically, we need to work out some numbers, the “Green's functions” for the given moduli, and then do some adding and multiplying. Just for reference, here are those numbers.

663	220780
166	−440895
665	220116

Working out the Green's functions isn't as gruesome as it sounds, either … in fact it's easy, because the moduli are close together. The Green's function for 663, for example, is the multiple of 166×665 that's congruent to 1 mod 663. But,

166 × 665 ≡ 166 × 2 = 332 mod 663,

and

332 × 2 = 664 ≡ 1 mod 663,

so the desired multiple is just 2 × 166×665.

Now you know everything! With just a bit of calculation, you'll be able to confirm that the first 3×3 block with an even center coordinate x is (664,3464005). Kind of an anticlimax, isn't it?

Then, if I tell you that 645 is the first suitable value of x, you can do a similar calculation and confirm that the first 3×3 block with an even center coordinate y is (645,3211284). Equivalently, in terms of blocks with even x, (3211284,645) is the one with the smallest value of y.

I don't know why the coordinates of the points are so close. Strange but true!

Just for the record, here's one more I worked out: the first 3×3 block with two even center coordinates is (1310,20515516). Note that 664 + 645 = 1309.

The final thing I want to talk about is larger blocks.

First we need the idea of “depth”. The depth of a number is the largest number of adjacent squares that are ever filled in in the maze pattern for that number. The depth is always at least equal to the number of distinct factors, but can be larger if some of the factors are small (so that they contribute more than once). A prime or prime power, for example, has depth 1, a number with two factors has depth 3 if one of the factors is 2, otherwise depth 2, and so on.

For larger numbers, the depth can be tricky to compute, so here's a table I made that should hold you for a while … it covers everything up to the product of the first six odd primes, 255255, and also most things for quite a ways beyond that. To look up a number, go to the column for the number of distinct factors, then move down to the appropriate row depending on whether there are factors of 2 or 3. If there are numbers in parentheses, use the first if there's a factor of 5, the second if there are factors of both 5 and 7.

	1	2	3	4		5		6
-	1	2	3	4		5	(6)	6	(7,8)
3	1	2	4	5	(6)	7	(8,10)	.
2	1	3	5	7		9		11	(13)
2,3	-	3	5	9		11	(13)	15	(17,21)

If you want to check or extend the table, here are some hints.

• It helps to imagine having factors that are arbitrarily large. The factor 3, for example, produces a pattern with two-square gaps, so as you add arbitrarily large factors, the depth goes up in alternating steps of 1 and 2.
• A factor p can only contribute twice if the depth is at least p. For example, if a number has four factors, 3 plus three arbitrarily large others, the depth is 5, so it doesn't matter if one of the others is 7.
• Similarly, if a factor 2 is present, a factor p can only contribute twice if the depth is at least 2p.

Later I realized I wasted some effort … the rows with factors of 2 are related to the rows without factors of 2 by the following identity (valid for odd x).

D(2x) = 2 D(x) + 1

By the way … the depth function is strange and problem-specific, but there are related functions, like the number of distinct (or non-distinct) factors, that might actually be useful in number theory. But I digress.

We also need the idea of “width”. Given a desired depth D, the width of the number x is the largest number W such that all numbers in the range [x,x+(W−1)] have depth at least D. The reason that definition is interesting is that that's exactly what we need in order to have a block of size W×D!

As far as I know, there's no clever way to find out about width, you just have to search through a lot of numbers. So, that's one of the things I made the code do for me. And, here are some results … the first numbers with width W for various depths D. The entries that aren't filled in are all above 10000.

	width	1	2	3	4	5	6	7
depth
2		6	14	20	33	54	90	90
3		6	104	104	662	662	5420	5420
4		30	230	644	8853	.	.	.
5		30	1364	3794	.	.	.	.
6		210	8294	.	.	.	.	.
7–9		210	.	.	.	.	.	.

As it happens, the locations of the 3×3 blocks with even coordinates now make reappearances as the locations of the first 3×4 block (644) and of the first 4×3 and 5×3 blocks (662). That was probable, but not guaranteed … think about it.

I don't care to compute any of the y coordinates, they would just be large meaningless numbers. Instead, I'll leave you with these nice factorizations.

8853 = 3 × 13 × 227
8854 = 2 × 19 × 233
8855 = 5 × 7 × 11 × 23
8856 = 2³ × 3³ × 41