sidef-scripts/Math/moessner_miracle.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 23 July 2021
# https://github.com/trizen

# Simple implementation of the Moessner extension for computing k-th powers of integers and factorials, using only addition.

# See also the following Mathlogger video:
#   The Moessner Miracle. Why wasn't this discovered for over 2000 years?
#   https://www.youtube.com/watch?v=rGlpyFHfMgI

func moessner(n, k=2) {

    var arr = @(1..n)

    for (true; k > 1; --k) {

        arr = gather {
            var acc = 0
            arr.each_kv {|i,v|
                if (!(k `divides` (i+1))) {
                    take(acc += v)
                }
            }
        }
    }

    return arr
}

say moessner(20, 2)     #=> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
say moessner(20, 3)     #=> [1, 8, 27, 64, 125, 216, 343]
say moessner(20, 4)     #=> [1, 16, 81, 256, 625]
say moessner(20, 5)     #=> [1, 32, 243, 1024]

func moessner_factorial(n) {

    var arr = @(1..n)
    var factorials = []

    while (arr.len) {

        factorials << arr.head

        arr = gather {
            var acc = 0
            arr.each_kv {|k,v|
                if (!is_polygonal(k+1, 3)) {
                    take(acc += v)
                }
            }
        }
    }

    return factorials
}

say ''
say moessner_factorial(polygonal(14, 3))     #=> [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200]