Home> urticator.net Search About This Site > Domains Glue Stories Computers Driving Games Humor Law Math > Numbers Science Powers and Fractions Notes About Squares Decimal Expansions Repeat Length Again > Number Maze Primes Divisibility Intrinsic Nature of Primes Other Topics Other Topics (2)
Odds and Ends 
The Next BlockRecently, 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 nextblock 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 of 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 value3 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.
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.
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.
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 threedigit number. I can add and subtract threedigit numbers, modulo something or not, but multiplying threedigit 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 threedigit 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 threedigit multiplication can be expressed in terms of addition and singledigit 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 1430 = 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.
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 threedigit 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.

See AlsoOdds and Ends @ July (2004) 