Moessner’s Magic

The sum of the firstn odd numbers isn^2. For example,

1 + 3 + 5 + 7 + 9 = 25 = 5^2

Here's another way to say the same thing. Start with the list of positive integers, remove every second integer from the list, and take the cumulative sum. The resulting list is the list of squares.

We begin with

1, 2, 3, 4, 5, ...

then have

1, 3, 5, 7, 9, ...

and end up with

1, 4, 9, 16, 25, ...

Cubes

Now start over with the list of positive integers. We're going to remove every third integer, take the cumulative sum, then remove every second integer, and take the cumulative sum. The result is a list of cubes.

Here are the steps described above for the positive integers up to 20:

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ..., 20
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20
1, 3, 7, 12, 19, 27, 37, 48, 61, 75, 91, 108, 127, 147
1, 7, 19, 37, 61, 91, 127
1, 8, 27, 64, 125, 216, 343

General case

In general, given an integerk we remove everykth element, take the cumulative sum. Then we reducek by 1 and repeat. We keep doing this untilk = 1, in which case we stop. The end result will be the list ofkth powers.

The result at the top of the post, corresponding tok = 2, has been known since ancient times. The generalization to largerk wasn't known until Alfred Moessner observed it in 1951. Oskar Perron proved Moessner's conjecture later the same year. The result has been called Moesnner's theorem or Moesnner's magic.

Python implementation

A little Python code will make it easier to play with Moessner's process for larger numbers.

from numpy import cumsumdef moessner(N, k): x = range(1, N+1) while k > 1: x = [x[n] for n in range(len(x)) if n % k != k - 1] # print(x) x = cumsum(x) # print(x) k = k - 1 return x

To see the intermediate steps, uncomment the print statements.

If we run the following code

for k in [2, 3, 4, 5]: print( moessner(25, k) )

we get the following.

[1 4 9 16 25 36 49 64 81 100 121 144 169][1 8 27 64 125 216 343 512 729][1 16 81 256 625 1296 2401][1 32 243 1024 3125]

Related posts

• Easy to guess, hard to prove
• Recaman's sequence

The post Moessner's Magic first appeared on John D. Cook.