Daily Archives: 3/18/2007

Thinking about sex…agesimal numbers

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 60k where 60k is divisible by 75. Well, that’s simple enough, 602 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 600, 601, 602… 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)

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

Technorati Tags: , ,

Hypermiling: Extreme Fuel Conservation by Unorthodox Driving

We’d all like to get better gas mileage from our cars. Well, me especially. My Ford Expedition isn’t exactly the cheapest car to put on the road. But so-called “hypermilers” take this to the extreme by adopting a number of techniques to reduce fuel consumption: such as drafting trucks with the engine off, or taking slow curves at high speed to retain momentum. I’m simultaneously horrified and amazed. Check out the cool article on Mother Jones.

This Guy Can Get 59 MPG in a Plain Old Accord. Beat That, Punk

Gutenberg Gem: Handwork in Wood by William Noyes

I know a couple of readers of mine are interested in woodworking, so when I saw Handiwork in Wood come by on the recently completed list over at Distributed Proofreaders, I thought I’d have a look. The title suggested a book about the working of wood with handtools, and indeed, the book does that, but it also includes a large section on the working of large lumbermills around the turn of the century, with many photos. Some are really pretty neat, like:

Loggers

It does include a wide variety of information on hand joinery using both simple and sophisticated planes of the day. Worth checking out.

Handwork in Wood by William Noyes – Project Gutenberg

Technorati Tags: , ,