Mersenne Numbers in C#

Don't ask why (you won't be amused) but I had a need to calculate some Mersenne numbers in C#. For those of you unfamiliar with the Mersenne numbers, a Mersenne number is of the form M_n = 2ⁿ - 1. Here are a few of the first Mersenne numbers:

1. M₁ = 2¹ - 1 = 1
2. M₂ = 2² - 1 = 3
3. M₃ = 2³ - 1 = 7
4. M₄ = 2⁴ - 1 = 15
5. M₅ = 2⁵ - 1 = 31
6. M₆ = 2⁶ - 1 = 63

Notice anything interesting about the values of the first 6 Mersenne numbers? Well, when stored in binary the Mersenne are binary repunits, meaning their values consist of 1 distinct bit value:

1. M₁ = 2¹ - 1 = 1 => 1
2. M₂ = 2² - 1 = 3 => 11
3. M₃ = 2³ - 1 = 7 => 111
4. M₄ = 2⁴ - 1 = 15 => 1111
5. M₅ = 2⁵ - 1 = 31  => 11111
6. M₆ = 2⁶ - 1 = 63  => 111111

How useful these numbers are is of course application specific, but I can't help but be fascinated with how easily the Mersenne numbers are represented in binary. Without knowing how the Mersenne numbers are stored in binary, you might be tempted to code some implementation of the formula M_n - 2ⁿ - 1.  But once we know that the Mersenne numbers are binary repunits, we can easily generate a sequence of these numbers with a loop and some bit manipulations:

ulong m = 0;
for (var i = 0; i < 64; i++)
{
    m = 1 | (m << 1);
    Console.WriteLine("Mersenne #" + (i + 1).ToString() + " = " + m.ToString());
}

Go ahead and run that, it'll generate the first 64 Mersenne numbers by repeatedly shifting a Mersenne number's bits to the left and performing a bit-wise OR with 1.

What's really important to point out here is that our algorithm for generating Mersenne numbers does not have an obvious mapping into the definition of what a Mersenne number is. What does "m = 1 | m << 1" have to do with the equation "M_n - 2ⁿ - 1"? Not a whole lot unless we examine how the Mersenne numbers look in binary. When designing algorithms, remember that efficient solutions may exist that are not obvious based on the problem definition.