The Next Block

Recently, I was trying to pass some time while traveling. I still had blocks and mental arithmetic on my mind, so I thought I'd see if I could find the next 3×3 block. And, of course I could, or I wouldn't be writing about it … the center is located at (231,5655).

After that, of course, I really had blocks on my mind. I thought I could probably find the next few by hand, but I wanted to find all of them, and I could already tell that that was going to be difficult … so instead I cheated and wrote a bit of code to find them. So, if you're interested in mental arithmetic, or just curious, you can read on for some details of how I found the next block, but if you just want to know the final answer, you can skip ahead to the section on minimal blocks.

Now let's work through the next-block calculation. We already know that the center coordinate x has to have three distinct odd prime factors, and we've already found a block for the first such coordinate, 3×5×7 = 105. So, what we need to do is look at other such coordinates until we find one that has a block at a lower value of y. (If a block has an even center, the odd edge coordinates both have to have three distinct odd prime factors, so we can worry about that when it happens … and here it doesn't.)

The first thing we need, then, is some way to enumerate the products of three distinct odd primes in some kind of reasonable order. There are various ways of doing that; the one that appeals to me uses an analogy from physics (or chemistry, depending on how you look at it). Think of the primes as the energy levels of some weird atom, and imagine that the levels are occupied by three electrons. The electrons have to obey the exclusion principle, so in the ground state, the state of least possible energy, they occupy the three smallest primes. Then the excited states correspond to the other sets of primes!

To enumerate the possible states, let's refer to the primes by sequence number rather than value—3 is the first odd prime, 5 is the second, and so on. So, we start in the ground state, 123. When the outer electron jumps up one level, we get the first excited state, 124; and when another electron jumps up, we get one of the next two excited states, 125 and 134; and so on.

Now, just for a moment, suppose that the sequence numbers represent energies, so that the ground state has energy 6, the first excited state has energy 7, the next two states have energy 8, and so on. If we blur the distinction between levels and states, we can think of each set of states as a shell, just like in chemistry except that the details are completely different. (E.g., here the third shell has two states, 125 and 134, but in chemistry it has eighteen … two 3s states, six 3p states, and ten 3d states.)

Those shells are very useful in Cross Sums, by the way.

In our case, since we're interested in products of primes, the energies ought to be proportional to the logarithms of the corresponding primes. Fortunately, we don't need to go into that much detail … all that matters is that the original, unperturbed shells provide a useful way of enumerating the states.

So … the next potential center coordinate is the first excited state, 124, which corresponds to 3×5×11 = 165. Factoring the adjacent numbers (164 and 166), we see that the y coordinate has to be an odd multiple of 41×83 = 3403. But, 3403 itself doesn't work (because for example it's congruent to 4 mod 11, so that the factor 11 doesn't contribute) and the next multiple is already larger than 6201.

What next? Well, here are the states in the third shell … plus the first state in the fourth shell, to show that that shell doesn't need to be considered yet.

125	3×5×13 = 195
134	3×7×11 = 231
126	3×5×17 = 255

Does 195 work? Factoring the adjacent numbers tells us that we're looking for an odd multiple of 97×7 = 679; and the only multiples that are small enough are 1, 3, 5, 7, and 9. But, since 679 is congruent to 3 mod 13, the multiples are congruent to 3, 9, 2, 8, and 1, so the only one for which 13 contributes is 9×679 = 6111. That almost works … all three factors hit within range, but unfortunately 5 and 13 both hit the same number, 6110.

Next is 231. As before, 232 has only one odd factor, 29, but now 230 has two, 5 and 23. So, here the y coordinate has to be an odd multiple of 5×29 = 145 or 23×29 = 667. The former seems more promising, since it has more multiples below 6201, so let's try it first. However, since it does have so many multiples, let's use something more clever than brute force.

We want a multiple where all three factors (3, 7, and 11) will contribute. Here's one way that could happen.

m × 145 ≡	−1	mod 3
m × 145 ≡	0	mod 7
m × 145 ≡	1	mod 11

There are six ways in total, one for each permutation of the numbers on the right. We could just solve the six sets of equations for m mod 231, but that would be a bit painful. Fortunately there's an easier way.

• Step through the multiples of 11 and look at the nearby numbers mod 7 and mod 3 to find the six possible values of m × 145, which are 55, 56, and 111 and their negatives (mod 231).
• Multiply those six values by the inverse of 145, which happens to be 94, to find the six possible values of m, which are 88, 182, and 39 and their negatives 143, 49, and 192. Those are actually very easy to compute, since 56 = 55+1 and 111 = 55+56. (And, those facts are not accidents!)

Finally, we need to convert from solutions mod 231 to solutions that are integers. Since we're looking for odd multiples, we have to add 231 to the even solutions, but that's academic because the smallest solution is still m = 39. So, multiplying it out, we get the y coordinate, 39×145 = 5655. Ta da!

Later I realized there were flaws in my calculation. I forgot to go back and check the multiples of 667, and I didn't consider potential coordinates with powers of factors, or more than three factors. Fortunately neither of those affects the result.

When I was done, I was pleased with myself not only because I'd obtained the result, but also because I'd thought of two innovations that made it relatively easy to do any kind of mental arithmetic modulo a three-digit number. I can add and subtract three-digit numbers, modulo something or not, but multiplying three-digit numbers and then dividing (by the modulus) and taking the remainder is beyond me … or at least a huge pain. So, I needed a different way of multiplying modulo something, and also a way of finding an inverse (which is like dividing).

The algorithm for multiplication takes advantage of two facts. First, it's not hard to multiply a three-digit number by a single digit, or by 10, and then subtract out a few multiples of the modulus. (But, it does help to precompute at least some of the multiples. You might compute the powers of two, to use as binary digits, or you might just walk through all the multiples and look for ones that are convenient and memorable. For example, from the fact that 3×231 = 693 is close to 700 you can derive the nice rule that 700 ≡ 7 mod 231.)

Second, any three-digit multiplication can be expressed in terms of addition and single-digit multiplication. For example,

137 × 137 = 10 × (10 × 137) + 3 × (10 × 137) + 7 × 137.

So, as a first step, you might compute 10×137. The product is 1370, that's easy; applying the nice rule twice shows that that's congruent to 14−30 = −16; and then adding 231 gives the intermediate result, 215.

Ironically, now that I've tidied up the calculation, multiplication mod 231 doesn't figure into it much. Oh well … at least the algorithm helped with my false starts.

The algorithm for finding an inverse is similar to the Euclidean algorithm for finding the greatest common divisor, except that the two numbers don't change roles. Here's how it works. For a single step, you find a multiple of the current number that's close to the modulus, either above or below, and then use congruence to reduce that multiple to a smaller number. So, for example, here's the first step in finding the inverse of 145 mod 231, written as an equation …

145 × 2 = 290 ≡ 59 mod 231

… and here are all the steps, written as a little table.

145	2	290	59
59	4	236	5
5	2×23	230	−1

Putting all the steps together, we have the following.

145 × (2 × 4 × 2×23) ≡ −1 mod 231

Multiplying out the numbers in parentheses gives 368, which is congruent to 137; bringing over the minus sign changes that to 94; and that leaves us with the result

145 × 94 ≡ 1 mod 231,

which shows that 94 is the desired inverse.

The algorithm is fine as it is, but here's a refinement I just thought of. In the worst case, when the modulus is right between two multiples, the current number is reduced by a factor of two. But, in that case, twice the modulus is right on top of a multiple, so you can get a better result by aiming for that. If you do the math, it turns out that you should aim for twice the modulus whenever the modulus is in the middle third of the range between multiples. Thus, the current number can always be reduced by a factor of three. For a three-digit number, that cuts the maximum number of steps from nine to six. Is that worth the added complexity?

Finally, I'd like to improve on a point I made in Operations. There I talked about how long division is a little program you can run, but, sadly, I didn't have any other examples of programs. Well, now I do … the Euclidean algorithm is one, and the algorithms for modular arithmetic are two more.