Donnie’s Blog

Last night I was looking for interesting programming problems, and I came across this page about the Möbius Function. It’s a pretty simple idea, although I have no idea how August Möbius came up with the idea in the first place.

Given a positive integer n, the Möbius function μ(n) returns:

• 0 if the number is a multiple of a square
• -1 if the number has an odd number of distinct prime factors
• 1 if the number has an even number of distinct prime factors

The n = 1 case is a special case; μ(1) is defined to return 1.

I thought this would be a fun little problem to play around with; it’s all about generating the list of prime factors for the input value. A number is a multiple of a square if it has any duplicate prime factors; for example, 12 = 2 × 2 × 3, so it is a multiple of a square, and μ(12) = 0.

An interesting little related problem is to find runs of numbers for which μ(n) is 0. For example, the first run of three multiples of squares is {48, 49, 50}. The first run of six square-multiples starts at 22020.

So, I wrote a Scheme program to implement the Möbius Function, and to find runs of square-multiples; here it is if you want to take a look! It was pretty fun, although the program starts to get annoyingly slow when hunting for runs of 7 or 8 square-multiples. I would have to upgrade to a much faster language if I were going to do something like that. Or perhaps there’s something I can improve in my implementation…

If you ever liked Rubik’s Cubes, check out these beasts: V-Cubes

The short version is that some professor figured out how to make Rubik’s Cube puzzles with sizes all the way up to 11×11x11. Right now his company is selling up to 7×7x7 “cubes” (they are actually slightly rounded), with larger versions in the offing.

I decided I just had to check these out, so I went ahead and ordered the set that includes the 5×5x5, the 6×6x6, and the 7×7x7. Should be fun!