Why does the subtitle of this blog say “MSM’s klog” — don’t you mean “blog”?
Well, maybe.
But when I was thinking about this material, I thought of it mostly as a series of meditations on issues that arise in my work, with only the occasional piece unrelated to W3C or my working groups. So my own notes for Messages in a bottle call it a work log, or worklog, or (yes) klog.
Hence the term in the subtitle. If it comes to seem too precious or weird, I suppose I can always change it. (Cool URIs don’t change, it’s true, but maybe subtitles don’t have to be cool.)
People on the W3C staff have been talking about blogs and how they can improve communication within a group, for some time. The discussions we had as a Team in Montréal (in November 2006) primed me to think about blogging as something it might be interesting to do. So did Jonathan Robie’s telling me that Jon Udell had urged him to start a blog, and Jonathan’s urging me to do so. (When was that? A long time ago, XML 2005 maybe.)
But the immediate impetus was finding some long-neglected pages on the W3C site (it really doesn’t matter which they were, or who wrote them) in which a Team member set down, years ago, some musings on a topic it turns out we both (and, as far as I can tell, virtually no others in the Team) are interested in.
It felt like finding a message in a bottle.
Putting such musings in a blog won’t help make them easier or harder to find, of course. But somehow the pages in question — and the pages I felt like writing in response — seem to fit more neatly into the genre of the journal, or the ongoing work log, the lab notebook, than into any other.
So I’m going to start a six-month experiment in keeping a work log. Think of it, dear reader, as my lab notebook. (I was going to do it starting a year ago, but, well, I didn’t. So I’m going to start now.)
My original plan was to make it accessible only to the W3C Team, so that I could talk about things that probably shouldn’t be discussed in public or in member space. Norm Walsh has blown a hole in that idea by
pointing to this log [Hi, Norm!]. So public it is. (Ideally, I’d have a blog in which each item could be marked with an ACL, like resources in W3C date space: Team-only, Member-only, World-readable. Maybe later.)
Next year about June, if I remember, I will evaluate the experiment and decide whether it’s been useful for me or not.
[27 December 2007; crucial typo corrected, graphics added 29 December]
Over Christmas I got a copy of Oystein Ore’s book Number theory and its history (New York: McGraw-Hill, 1948; reprint New York: Dover, 1988).
In section 2-3, exercise 5 reads
5. Prove that in the decadic number system [i.e. using decimal numerals] the fifth power of any number has the same last digit as the number itself.
This is straightforward enough, if you’ve just read the preceding section. (My exposition isn’t as good as Ore’s, so I won’t try to explain it.)
But now consider a related problem.
For numbers n whose decimal representation ends in a particular digit d, we can make a little directed graph that makes it easy to calculate the final digit of any number multiplied by n. Each graph will have ten nodes, labeled 0 through 9, and there will be an arc from node i to node j if and only if multiplying n by a number ending in i produces a number ending in j.
For the digit 3, for example, we’ll have the arcs 0 → 0, 1 → 3, 2 → 6, 3 → 9, 4 → 2, 5 → 5, 6 → 8, 7 → 1, 8 → 4, and 9 → 7. Like this:
And for the digit 5, there will be arcs from each odd-numbered state to state 5, and from each even-numbered state to state 0. And so on.
Like this:
There ought to be a name for these graphs, but I don’t know of one. I’ll call them multiplication graphs.
Now, consider what problem 5 means in terms of these multiplication graphs. For the given number, we pick the appropriate graph. If we raise the number to the power 0, the result is a number whose decimal representation ends in ‘1’. (Because it’s always the number 1.) Call the state labeled ‘1’ the start state. A path of length 1 will always take us to the state named for the digit whose multiplication properties the graph represents: in graph 3, a path of length 1 takes us to state 3, in graph 7, a path of length 1 takes us to state 7. Call this state the ‘characteristic state’.
If we raise the number to the power n, the result will have a decimal representation ending in the digit we reach by following a path through the graph, beginning at the start state and having exactly n steps. Final digit of the square? Follow a path two steps long. Final digit of the fifth power? Follow a path five steps long.
So: in terms of multiplication graphs, exercise 5 amounts to proving that in each graph, a path of length 5 takes you to the same state as a graph of length 1. Or, equivalently, that there is a cycle of length 4, or 2, or 1, beginning at the characteristic state of the graph.
It’s clear that there must be cycles in the graphs, and that the cycles can’t have length greater than 10, since there are only ten states. It’s clear, after a moment’s thought, that any cycle must either hit only even numbers or only odd numbers, and so any cycle must have length less than or equal to 5.
In fact, however, the cycles are all for length 1 (in graphs 0, 1, 5, and 6), 2 (graphs 4 and 9) or 4 (graphs 2, 3, 7, 8).
