brainwagon

Ever wonder why our clocks divide hours into sixty minutes of sixty seconds? What’s up with the sixty? I mean, factors of five and ten make some sense, but why sixty? Well, as it turns out, these things have some nifty properties because sixty has so many small factors. 60 = 2 * 3 * 2 * 5. Let’s look at the set of numbers which only have prime factors which are in the set {2, 3, 5}. What do they look like? Well… The first 30 are

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18,
20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50,
54, 60, 64, 72, 75, 80

You could get more terms from the Encyclopedia of Integer Sequences if you are too lazy to compute them yourself.

Let’s say that we have a number which we want to divide by a number in this list, say 75. 75 is 3*5*5. Let’s search (it isn’t hard) for a number 60^k where 60^k is divisible by 75. Well, that’s simple enough, 60² is 48 * 75. How does this relate back to division? Let’s say we want to divide 189 by 75. If we did the math normally, we’d get 2.52. But the Babylonians expressed fractions in sexagesimal notation: meaning that instead of having decimal digits, they had units, 1/60ths, 1/3600ths, and so on. We will write such numbers beginning with the units digits, and colons separating the remainders. A few seconds (minutes if you are rusty) of work on converting the number to radix 60 would tell you that the answer is 2:31:12. But let’s use what we learned above. instead of dividing by 75, let’s multiply by 48 instead. 48 * 189 = 9072. Let’s write this out as powers of 60. 9072 = 2 * 3600 + 31 * 60 + 12. Interesting! By multiplying by 48 and then shifting two sexegesimal digits, we can effect division: in short, we’ve discovered reciprocals. Because all these “regular” numbers have short reciprocals in base sixty, it’s actually rather convenient to use them to multiply and divide. Neat. The Babylonians apparently had good tables of these numbers.

It’s not hard to figure out that if a number x is regular, then its “reciprocal” must also be regular. (If a number is regular, it consists entirely of factors 2, 3, and 5 to some power. The sequence of powers 60⁰, 60¹, 60²… obviously generates arbitrarilly large numbers of these factors, and by dividing out, we are obviously left with 2, 3, and 5 being the only possible prime factors.) So we could just have easily divided by 48 by multiplying by 75 and then shifting by two sexagesimal digits.

It’s an interesting programming problem to find a short program to generate the list of all the numbers which are “regular”, which have only factors of 2, 3, and 5. If you have a lazy functional language which supports proper tail recursion, you can use streams to write a simple but interesting program to do it. I didn’t have either handy, but I did have Python handy. The analogous version didn’t work out too well at generating large numbers of terms, mainly because Python simply doesn’t do proper tail recursion, but in 20 minutes of tinkering with Python managed to hit on a method that worked pretty well using heaps. It took my AMD64 about 15 seconds to generate the first million terms, the millionth of which is 84 digits long.

Regular number – Wikipedia, the free encyclopedia

Addendum: Here’s the python code to generate these regular numbers (I retimed it, and it actually takes 18 seconds on my machine):

#!/usr/bin/env python

from sets import Set
from heapq import heappush, heappop

heap = []
heapset = Set([])

heappush(heap, 1)
heapset.add(1)

for x in range(1000000):
        val = heappop(heap)
        heapset.remove(val)
        print val
        if 2*val not in heapset:
                heappush(heap, 2*val)
                heapset.add(2*val)
        if 3*val not in heapset:
                heappush(heap, 3*val)
                heapset.add(3*val)
        if 5*val not in heapset:
                heappush(heap, 5*val)
                heapset.add(5*val)

Addendum²: A slightly modified version of this code can be used to verify that there 35,084 4-smooth numbers less than 10¹⁰⁰, which is the first part of problem 1.68 in Crandall and Pomerance’s Prime Numbers: A Computational Perspective.

^{[tags]Mathematics, Regular Numbers, Babylonian Numbers[/tags]}