Moessner's theorem

In number theory, Moessner's theorem or Moessner's magic is related to an arithmetical algorithm to produce an infinite sequence of the exponents of positive integers 1n,2n,3n,4n,⋯ , with n≥1 , by recursively manipulating the sequence of integers algebraically. The algorithm was first published by Alfred Moessner in 1951; the first proof of its validity was given by Oskar Perron that same year.

For example, for n=2, one can remove every even number, resulting in (1,3,5,7⋯), and then add each odd number to the sum of all previous elements, providing (1,4,9,16,⋯)=(12,22,32,42⋯).

Construction

Write down every positive integer and remove every n-th element, with n a positive integer. Build a new sequence of partial sums with the remaining numbers. Continue by removing every (n−1)-st element in the new sequence and producing a new sequence of partial sums. For the sequence k, remove the (n−k+1)-st elements and produce a new sequence of partial sums.

The procedure stops at the n-th sequence. The remaining sequence will correspond to 1n,2n,3n,4n⋯ .

Example

The initial sequence is the sequence of positive integers,

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16⋯ .

For n=4, we remove every fourth number from the sequence of integers and add up each element to the sum of the previous elements

1,2,3,5,6,7,9,10,11,13,14,15⋯→1,3,6,11,17,24,33,43,54,67,81,96⋯

Now we remove every third element and continue to add up the partial sums

1,3,11,17,33,43,67,81⋯→1,4,15,32,65,108,175,256⋯

Remove every second element and continue to add up the partial sums

1,15,65,175⋯→1,16,81,256⋯,

which recovers 14,24,34,44,⋯.

Variants

If the triangular numbers are removed instead, a similar procedure leads to the sequence of factorials 1!,2!,3!,4!,⋯ .