faulhaber_s_triangle_polynomial_interpolation.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 06 December 2018
# https://github.com/trizen

# Generate the first few rows of Faulhaber's triangle, using polynomial interpolation.

# See also:
#   https://en.wikipedia.org/wiki/Vandermonde_matrix
#   https://en.wikipedia.org/wiki/Faulhaber%27s_formula

func find_poly_degree(a) {
    var c = 0
    loop {
        ++c
        a = a.map_cons(2, {|n,k| n-k })
        return 0 if a.is_empty
        return c if a.all { .is_zero }
    }
}

func faulhaber_triangle(n) {
    var a = (0..(n+2) -> accumulate { _**n })
    var c = find_poly_degree(a)

    var A = c.of {|n|
        c.of {|k| n**k }
    }

    A.msolve(a).slice(1)
}

10.times { say faulhaber_triangle(_) }