The sum of the first n odd numbers is n². For example,
1 + 3 + 5 + 7 + 9 = 25 = 5²
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 integer k we remove every kth element, take the cumulative sum. Then we reduce k by 1 and repeat. We keep doing this until k = 1, in which case we stop. The end result will be the list of kth powers.
The result at the top of the post, corresponding to k = 2, has been known since ancient times. The generalization to larger k 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 cumsum
def 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]