Iterating Monotonic Decreasing Sequences

In this post I will show an algorithm to iterate over all monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\).

In a previous post I counted the number of monotonic decreasing sequences of length at most \(m\) and height \(n\). In order to study these objects it is nice If you can generate them all on a computer.

Furthermore, it would be nice to "visit" them one at a time. This cuts down on memory consumption, because then only one sequence has to be in memory at any time. In this blog post I will outline an algorithm to generate all the monotonic decreasing sequences of non-negative integers of length at most \(m\) and height \(n\) in lexicographical order.

The Power of the Internet

In this blog I reflect on a recent experience, which showed my the power of the internet.

Followers of my blog may have noticed that I wrote an article about the number 3435. In that article I generalized one of the properties 3435 has i.e.

\[
3^3 + 4^4 + 3^3 + 5^5 = 3435
\]

I defined Munchausen numbers in base b and proved that there are only finitely many Munchausen numbers in any base. Although I appreciated the result I never expected that the article would be read. This is where the power of the internet enters the stage.

Soon after I posted my article on the internet, a Andrew Baxter mailed my with some comments and suggestions. After including Andrew's suggestions and posting a new version of the article, I was content. Someone else had read my article, and it wasn't my mom.

After that I got an other mail, this time by Tracy Harms. He told my that my article inspired a discussion on Twitter. The discussion was about understanding the source of a program in the programming language J.
So a lot more people had read my article, even twittered about it.

I just finished googling "Munchausen Numbers" and there are numerous links all about an article I wrote. Without the internet nobody (besides my mom) would have read my article, let alone reacted on it. This experience showed my the power of the internet. And I am in awe.

The virtues of 3435

Folklore tells us that there is no such thing as an uninteresting integer. For, would such uninteresting integers exist, there would certainly be a smallest among them. But being the smallest uninteresting integer is a very interesting property, hence we should not have found it. The only way around this conundrum is to conclude that every integer is interesting.

Well, today three thousand four hundred thirty five got a little more interesting. Besides having a nice decimal representation, this number also possesses the following curious property:

\[
3^3 + 4^4 + 3^3 + 5^5 = 3435
\]

The only numbers who have this property are 1 and 3435. I know this for a fact because an exhaustive computer search until \(10^{10}\) did not reveal any other then numbers mentioned above.
Furthermore, if \(n > 10^{10}\) then \(n > 9^9\log(n)\) for

\[
\frac{10^{10}}{\log(10^{10})} = \frac{10^{10}}{10} = 10^{9} > 9^{9}
\]

Now, define \(\theta(n) := \sum c_{i}^{c_{i}}\) where the \(c_{i}\) are the numerals that express \(n\) in base 10. Then it can be shown that \(9^{9}\log(n) > \theta(n)\).

Now we know that 3435 is the only nontrivial number with such a special property.