Thursday, November 19, 2009

interesting and uninteresting numbers

In a paper published this week on arXiv, Dann van Berkel mentions the famous proof (or joke, depending on how you view things) that all natural numbers are interesting. Essentially, if there are uninteresting natural numbers, consider the smallest such uninteresting number (which is guaranteed to exist, since the naturals are well-ordered). This number, because it is the smallest uninteresting number, is interesting, providing us with a contradiction.

As Wikipedia points out, Nathaniel Johnson has given a slightly different formulation of the question, that seems more objective, and yet also more paradoxical. And currently, this formulation actually  produces 'uninteresting' numbers. The formulation goes something like this:

A number is interesting if and only if it belongs to an interesting sequence.
The Online Encyclopedia of Integer Sequences (OEIS) contains all interesting sequences.
Consequently, the numbers that do not appear in OEIS are uninteresting.

This gives us (as of last week, according to Johnson) that the number 12407 is currently the smallest uninteresting natural number.

Unfortunately, the sequence of uninteresting numbers seems interesting, and should be considered for inclusion in OEIS... but this would contradict its definition. So far, the sequence has not been included, so it still exists.

Does this formulation give a proof that OEIS cannot contain all interesting sequences? I think there are probably a bunch of statements we can generate with this sort of "interesting" logic, such as:

If an encyclopedia contains all interesting sequences, then every natural number must occur at least once in the encyclopedia.

But then again, you could argue that any number that occurs only once is interesting, and that the sequence of these once-occurring numbers is interesting also, causing them to be included again... In any case, this way of thinking about "interesting numbers" shows a lot of affinity with the Barber paradox, Russell's paradox, and other classics.

But van Berkel was not discussing uninteresting numbers in his paper, but rather a particularly interesting number, 3435.

If you take a natural number and calculate the sum of its digits raised to themselves, you get another natural number. Can this operation ever give you the original number back? Yes. Consider the number 1, which has a single digit, 1, when raised to itself gives 1^1=1. Here are some other calculations:

n ... sum of digits raised to themselves
1 ... 1^1 = 1
2 ... 2^2 = 4
3 ... 3^3 = 27
4 ... 4^4 = 256
5 ... 5^5 = 3125
6 ... 6^6 = 46656
7 ... 7^7 = 823543
8 ... 8^8 = 16777216
9 ... 9^9 = 387420489
10 ... 1^1 + 0^1 = 2
11 ... 1^1 + 1^1 = 2
12 ... 1^1 + 2^2 = 5
13 ... 1^1 + 3^3 = 28
14 ... 1^1 + 4^4 = 257
15 ... 1^1 + 5^5 = 3126
16 ... 1^1 + 6^6 = 46657
17 ... 1^1 + 7^7 = 823544
18 ... 1^1 + 8^8 = 16777217
19 ... 1^1 + 9^9 = 387420490
20 ... 2^1 + 0^0 = 5
21 ... 2^1 + 1^1 = 5

If we call this function $\theta(n)$, do we ever get another number than 1 that is a fixed point for $ \theta(n)$? Well, yes, and 3435 provides us with the next example:

\[3435 = 3^3 + 4^4 + 3^3 + 5^5\]
The graph below shows a plot of theta for n up to 5000 - the two fixed points that are found in this range, 1 and 3435, are shown as blue squares (data file here). The huge scale on the y-axis makes the graph look more constant in places than it really is.

Numbers for which $n = \theta(n)$ for a given base $b$ are called Munchausen numbers, and are interesting, according both to common conceptions of what 'interesting' means, and according to Johnson's OEIS-based definition (OEIS entry: A166623, also submitted by van Berkel). Making 3435 even more interesting is the fact that, according to van Berkel's paper, 1 and 3435 are the only Munchausen numbers, base 10.

Munchausen numbers are (presumably) named after the semi-fictional Baron Munchausen, who interestingly enough may not have actually been interesting, but was intent on convincing others that he was. You may know Munchausen from the Terry Gillam movie, and he has also lent his name to the curious Munchausen syndrome, and to the disturbing Munchausen-syndrome-by-proxy. The image at the top of the post is from a 1902 edition of the book, The Adventures of Baron Munchausen.

1 comment:

  1. I dispute both of the premises of the OEIS paradox.

    I think there are numbers in interesting sequences that are not themselves interesting; for instance the sequence of Fibonacci numbers is interesting but only the first few terms, and a few other terms with other special properties, are themselves interesting. Also there are numbers that are interesting but may not be part of an interesting sequence (particularly numbers that are interesting because of a property that makes them unique, so it's unlikely that there would be an OEIS entry containing just the one number).

    More importantly, there exist interesting sequences not in the OEIS (yet? maybe asymptotically over time they are all in there) and uninteresting sequences that are in the OEIS.