MAGMA Syntax Highlighting

This blog post points out how to add syntax highlighting for MAGMA in gedit.

MAGMA is a very good computer algebra system, but not very well known outside a select mathematical circle. So it is not very surprising that gedit does not know how to syntax highlight MAGMA code out of the box.

Gedit uses GtkSourceView as its syntax highlighting engine. GtkSourceView can be extended by providing a language definition file.

So I set out to create a language definition file for MAGMA. The results can be found at github. In order to use is, you have to place the magma.lang file in the following directory:

~/.local/share/gtksourceview-2.0/language-specs

Below you can find a screenshot of a snippet of MAGMA code highlighted by gedit.

Updated old post

In this blog post I announced that I switched to using Mathjax. But I hadn't got to the point of rewriting my old post, with this new interface.

Coming this spring I set out to rectify this point and now all posts are using Mathjax as Latex rendering engine.

The only thing I noticed that not every post is using proper html. So probably I have to go back and change that to.

MinuteMath: A bite size math problem a day

I Recently subscribed to the The Mathematical Association of America twitter feed. The most important reason for me is their daily MinuteMath.

The MinuteMath is a daily bite size mathematical problem of varying difficulty. All the problems are multiple choice and hints, solutions and classifications are given.

It is a fun way to distract your mind for a moment and figure out a interesting little problem. If your interested start following @maanow.

MathJax: Include mathematics non-obtrusively

In this blog post I will explain the use of MathJax, a javascript based display engine for mathematics.

In an early post I pointed out that yourequations.com has a very nice solution for producing beautiful LaTeX on the web. Unfortunately as of October 31 2010 their service has shut down. As a result the LaTeX on my blog did not render any more.

So a tweet alerted me to mathjax, a display engine for mathematics. With mathjax it is possible to write mathematics in LaTeX or MathML and the javascript based engine will make a beautiful image.
As a bonus mathjax allows you to scale the mathematics, view the source in LaTeX or MathML and choice the rendermode i.e. straight to MathML or via their custom fonts.

Seeing their beautiful examples I decided that use mathjax for this blog. So once again, mathematics can be viewed in splendid glory.

\[
e^{i\pi}+1=0
\]

Counting Backgammon End Positions

In this blog I will count the number of end positions in backgammon.

Recently I picked up backgammon again. But I could not put my mathematical mind to rest. I got interested in the question of how many end positions backgammons has.
In order to count the number of positions I will introduce the following terminology. The number of stones you own in the end position will be denoted by \(m\). The number of points used available is \(n\). \(o\) is the number of stones owned by the opponent, which occupy \(p\) points of the available \(n\).
So in the following example, playing as black, the following equalities apply \(m=8,\,n=6,\,o=2,\,p=1\).

Let's look at a special case first. Lets assume we have a contact-less end position. So \(o=0\). I will proof that the number of backgammon end positions with \(m\) stones and \(n\) points is

\[
m + n - 1 \choose m
\]

To see this equality, study the following diagram, which corresponds with the figure above if you ignore the opponent stones:

Every dot corresponds with a stone. Every bar with the division between points. A moments reflection will bring the insight that every diagram of this kind corresponds to a backgammon end position and vice versa, every backgammon end position can be described by such a diagram. This proofs the stated equality.

With the result of this special case we can answer the main question: How many backgammon end positions exist with \(m\) stones distributed over \(n\) points of which \(p\) are occupied by \(o\) opponent stones? This number is exactly

\[
{n \choose p} {o - 1 \choose o - p} {m + n - p - 1 \choose m}
\]

The proof of the above equality comes from the following insight. The opponent stones are distributed over \(p\) points. there are \(n \choose p\) ways of picking the occupied points.
For a point to be occupied it must at least contain one opponent stone. So of the \(o\) opponents stones, we can freely distribute o - p opponent stones over \(p\) points. This is the special case we counted already, so this can be achieved in \({(o-p) + (p-1) \choose o - p} = {o - 1 \choose o - p}\) ways.
This brings us to the final factor. It represent the \(m\) stones which should be distributed over the remaining \(n-p\) points. Again this is given by our preliminary result of \({m + n - p - 1 \choose m}\) ways. This proofs the stated result.

In conclusion: the number of backgammon end point positions with \(m\) stones distributed over \(n\) points of which \(p\) are occupied by \(o\) opponent stones equals

\[
{n \choose p} {o - 1 \choose o - p} {m + n - p - 1 \choose m}
\]

Counting Graphic Sequences

In this post I give the the number of graphic sequences of length 0 through 6.

The numbers were counted by iterating over all sequences using a custom made graphic sequence iterator.

length	0	1	2	3	4	5	6	7
#	1	1	2	4	11	31	102	342

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.

Counting Monotonic Decreasing Sequences

In this blog post I will count the number of monotonic decreasing sequences of length \(m\) and height \(n\).

I recently got interested in graphic sequences. A graphic sequence is an example of a monotonic decreasing non-negative integer sequence i.e. a sequence which never goes up. For example

4,3,3,3,1,1

The next terminology will be used throughout this blog. The height of a sequence is the greatest element which occurs in the sequence. For monotonic decreasing sequences this corresponds with the first element. So the height of the sequence mentioned above is 5.

I set out to count the number of non-negative integer sequences of length <\(m\) and height \(n\). After some considerations I found an elegant manner in which to present the answer.

Consider plotting the above sequence on graph paper. We need a 6 by 5 box to plot the sequence. (Remember, it is a sequence of non-negative integers.) The graph is given below.

When the descenders are added a path is formed from the upper left corner to the lower right corner. (The descenders are in orange.) Because we have plotted a monotonic decreasing sequence the path is formed by making steps due "south" or "east". There are precisely \({m+n-1} \choose {n}\) such paths. (There are \(m+n-1\) choices to make of which \(n\) are "south").

An other relation can be deduced by examining the correspondence between monotonic decreasing sequences and south-east-paths. Let's count the monotonic decreasing sequences of length \(m\) and height at most \(n\). Notice that all those sequences are a tail-subsequence of a monotonic decreasing sequence of length \(m + 1\) and height \(n\). So one can deduce the relation

\[
\sum_{i=0}^{n} {{m+n-1} \choose {n}} = {{m+n} \choose {n}}
\]

On can count the number of monotonic decreasing non-negative integer sequences by considering a nice correspondence between such sequences and south-east-paths on grids.

Estimating Collisions in URL Shortening

In this blog post I estimate the time before the first collision for URL shorteners such as bit.ly occurs.

Observation on Binary Trees

In this post I will proof the following observation:

Let \(T\) be a binary tree, \(I\) the number of internal nodes and \(L\) the number of leaves in \(T\) then

\[
L = I + 1
\]

We will proof this fact by observing the following. Every binary tree can be "grown" by replacing leaves with trivial binary tree.

Assume to the contrary that not every binary tree can be grown by replacing leaves with trivial binary trees. Then there must exist a smallest binary tree which can not be grown in such a way. Call it \(C\).
Notice that both subtrees of \(C\) are smaller binary trees. Because \(C\) was the smallest tree which could not be grown, both subtrees can be grown.
But the following description grows \(C\).

1. Take trivial binary tree
2. On the left leaf use the description for the left subtree of \(C\)
3. On the right leaf use the description for the right subtree of \(C\)

This contradicts the fact that \(C\) was the smallest such tree. We are forced to drop the assumption that there exist a binary tree which could not be grown. Therefore all binary trees can be grown.

Now for the trivial binary tree is is clear that

\[
L = I + 1
\]

And when a leaf is grown both \(L\) and \(I\) go up by 1, maintaining the equality. From the above observations one can conclude that the equations hold for all binary trees.

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.