Named after Johann Faulhaber, the rows of Faulhaber's triangle are the coefficients of polynomials that represent sums of integer powers, which are extracted from Faulhaber's formula:








∑

k
=
1


n



k

p


=


1

p
+
1




∑

j
=
0


p





(



p
+
1

j


)




B

j



n

p
+
1
−
j




{\displaystyle \sum _{k=1}^{n}k^{p}={1 \over p+1}\sum _{j=0}^{p}{p+1 \choose j}B_{j}n^{p+1-j}}




where 




B

n




{\displaystyle B_{n}}

 is the nth-Bernoulli number.



The first 5 rows of Faulhaber's triangle, are:

    1
  1/2  1/2
  1/6  1/2  1/3
    0  1/4  1/2  1/4
-1/30    0  1/3  1/2  1/5



Using the third row of the triangle, we have:






∑

k
=
1


n



k

2


=


1
6


n
+


1
2



n

2


+


1
3



n

3




{\displaystyle \sum _{k=1}^{n}k^{2}={1 \over 6}n+{1 \over 2}n^{2}+{1 \over 3}n^{3}}





 Task
 show the first 10 rows of Faulhaber's triangle.
 using the 18th row of Faulhaber's triangle, compute the sum: 




∑

k
=
1


1000



k

17




{\displaystyle \sum _{k=1}^{1000}k^{17}}

 (extra credit).
 See also

 Bernoulli numbers
 Evaluate binomial coefficients
 Faulhaber's formula (Wikipedia)
 Faulhaber's triangle (PDF)


(() => {
 
    // Order of Faulhaber's triangle -> rows of Faulhaber's triangle
    // faulHaberTriangle :: Int -> [[Ratio Int]]
    const faulhaberTriangle = n =>
        map(x => tail(
                scanl((a, x) => {
                    const ys = map((nd, i) =>
                        ratioMult(nd, Ratio(x, i + 2)), a);
                    return cons(ratioMinus(Ratio(1, 1), ratioSum(ys)), ys);
                }, [], enumFromTo(0, x))
            ),
            enumFromTo(0, n));
 
    // p -> n -> Sum of the p-th powers of the first n positive integers
    // faulhaber :: Int -> Ratio Int -> Ratio Int
    const faulhaber = (p, n) =>
        ratioSum(map(
            (nd, i) => ratioMult(nd, Ratio(raise(n, i + 1), 1)),
            last(faulhaberTriangle(p))
        ));
 
    // RATIOS -----------------------------------------------------------------
 
    // (Max numr + denr widths) -> Column width -> Filler -> Ratio -> String
    // justifyRatio :: (Int, Int) -> Int -> Char -> Ratio Integer -> String
    const justifyRatio = (ws, n, c, nd) => {
        const
            w = max(n, ws.nMax + ws.dMax + 2),
            [num, den] = [nd.num, nd.den];
        return all(Number.isSafeInteger, [num, den]) ? (
            den === 1 ? center(w, c, show(num)) : (() => {
                const [q, r] = quotRem(w - 1, 2);
                return concat([
                    justifyRight(q, c, show(num)),
                    '/',
                    justifyLeft(q + r, c, (show(den)))
                ]);
            })()
        ) : "JS integer overflow ... ";
    };
 
    // Ratio :: Int -> Int -> Ratio
    const Ratio = (n, d) => ({
        num: n,
        den: d
    });
 
    // ratioMinus :: Ratio -> Ratio -> Ratio
    const ratioMinus = (nd, nd1) => {
        const
            d = lcm(nd.den, nd1.den);
        return simpleRatio({
            num: (nd.num * (d / nd.den)) - (nd1.num * (d / nd1.den)),
            den: d
        });
    };
 
    // ratioMult :: Ratio -> Ratio -> Ratio
    const ratioMult = (nd, nd1) => simpleRatio({
        num: nd.num * nd1.num,
        den: nd.den * nd1.den
    });
 
    // ratioPlus :: Ratio -> Ratio -> Ratio
    const ratioPlus = (nd, nd1) => {
        const
            d = lcm(nd.den, nd1.den);
        return simpleRatio({
            num: (nd.num * (d / nd.den)) + (nd1.num * (d / nd1.den)),
            den: d
        });
    };
 
    // ratioSum :: [Ratio] -> Ratio
    const ratioSum = xs =>
        simpleRatio(foldl((a, x) => ratioPlus(a, x), {
            num: 0,
            den: 1
        }, xs));
 
    // ratioWidths :: [[Ratio]] -> {nMax::Int, dMax::Int}
    const ratioWidths = xss => {
        return foldl((a, x) => {
            const [nw, dw] = ap(
                [compose(length, show)], [x.num, x.den]
            ), [an, ad] = ap(
                [curry(flip(lookup))(a)], ['nMax', 'dMax']
            );
            return {
                nMax: nw > an ? nw : an,
                dMax: dw > ad ? dw : ad
            };
        }, {
            nMax: 0,
            dMax: 0
        }, concat(xss));
    };
 
    // simpleRatio :: Ratio -> Ratio
    const simpleRatio = nd => {
        const g = gcd(nd.num, nd.den);
        return {
            num: nd.num / g,
            den: nd.den / g
        };
    };
 
    // GENERIC FUNCTIONS ------------------------------------------------------
 
    // all :: (a -> Bool) -> [a] -> Bool
    const all = (f, xs) => xs.every(f);
 
    // A list of functions applied to a list of arguments
    // <*> :: [(a -> b)] -> [a] -> [b]
    const ap = (fs, xs) => //
        [].concat.apply([], fs.map(f => //
            [].concat.apply([], xs.map(x => [f(x)]))));
 
    // Size of space -> filler Char -> Text -> Centered Text
    // center :: Int -> Char -> Text -> Text
    const center = (n, c, s) => {
        const [q, r] = quotRem(n - s.length, 2);
        return concat(concat([replicate(q, c), s, replicate(q + r, c)]));
    };
 
    // compose :: (b -> c) -> (a -> b) -> (a -> c)
    const compose = (f, g) => x => f(g(x));
 
    // concat :: [[a]] -> [a] | [String] -> String
    const concat = xs =>
        xs.length > 0 ? (() => {
            const unit = typeof xs[0] === 'string' ? '' : [];
            return unit.concat.apply(unit, xs);
        })() : [];
 
    // cons :: a -> [a] -> [a]
    const cons = (x, xs) => [x].concat(xs);
 
    // 2 or more arguments
    // curry :: Function -> Function
    const curry = (f, ...args) => {
        const go = xs => xs.length >= f.length ? (f.apply(null, xs)) :
            function () {
                return go(xs.concat(Array.from(arguments)));
            };
        return go([].slice.call(args, 1));
    };
 
    // enumFromTo :: Int -> Int -> [Int]
    const enumFromTo = (m, n) =>
        Array.from({
            length: Math.floor(n - m) + 1
        }, (_, i) => m + i);
 
    // flip :: (a -> b -> c) -> b -> a -> c
    const flip = f => (a, b) => f.apply(null, [b, a]);
 
    // foldl :: (b -> a -> b) -> b -> [a] -> b
    const foldl = (f, a, xs) => xs.reduce(f, a);
 
    // gcd :: Integral a => a -> a -> a
    const gcd = (x, y) => {
        const _gcd = (a, b) => (b === 0 ? a : _gcd(b, a % b)),
            abs = Math.abs;
        return _gcd(abs(x), abs(y));
    };
 
    // head :: [a] -> a
    const head = xs => xs.length ? xs[0] : undefined;
 
    // intercalate :: String -> [a] -> String
    const intercalate = (s, xs) => xs.join(s);
 
    // justifyLeft :: Int -> Char -> Text -> Text
    const justifyLeft = (n, cFiller, strText) =>
        n > strText.length ? (
            (strText + cFiller.repeat(n))
            .substr(0, n)
        ) : strText;
 
    // justifyRight :: Int -> Char -> Text -> Text
    const justifyRight = (n, cFiller, strText) =>
        n > strText.length ? (
            (cFiller.repeat(n) + strText)
            .slice(-n)
        ) : strText;
 
    // last :: [a] -> a
    const last = xs => xs.length ? xs.slice(-1)[0] : undefined;
 
    // length :: [a] -> Int
    const length = xs => xs.length;
 
    // lcm :: Integral a => a -> a -> a
    const lcm = (x, y) =>
        (x === 0 || y === 0) ? 0 : Math.abs(Math.floor(x / gcd(x, y)) * y);
 
    // lookup :: Eq a => a -> [(a, b)] -> Maybe b
    const lookup = (k, pairs) => {
        if (Array.isArray(pairs)) {
            let m = pairs.find(x => x[0] === k);
            return m ? m[1] : undefined;
        } else {
            return typeof pairs === 'object' ? (
                pairs[k]
            ) : undefined;
        }
    };
 
    // map :: (a -> b) -> [a] -> [b]
    const map = (f, xs) => xs.map(f);
 
    // max :: Ord a => a -> a -> a
    const max = (a, b) => b > a ? b : a;
 
    // min :: Ord a => a -> a -> a
    const min = (a, b) => b < a ? b : a;
 
    // quotRem :: Integral a => a -> a -> (a, a)
    const quotRem = (m, n) => [Math.floor(m / n), m % n];
 
    // raise :: Num -> Int -> Num
    const raise = (n, e) => Math.pow(n, e);
 
    // replicate :: Int -> a -> [a]
    const replicate = (n, x) =>
        Array.from({
            length: n
        }, () => x);
 
    // scanl :: (b -> a -> b) -> b -> [a] -> [b]
    const scanl = (f, startValue, xs) =>
        xs.reduce((a, x) => {
            const v = f(a.acc, x);
            return {
                acc: v,
                scan: cons(a.scan, v)
            };
        }, {
            acc: startValue,
            scan: [startValue]
        })
        .scan;
 
    // show :: a -> String
    const show = (...x) =>
        JSON.stringify.apply(
            null, x.length > 1 ? [x[0], null, x[1]] : x
        );
 
    // tail :: [a] -> [a]
    const tail = xs => xs.length ? xs.slice(1) : undefined;
 
    // unlines :: [String] -> String
    const unlines = xs => xs.join('\n');
 
 
    // TEST -------------------------------------------------------------------
    const
        triangle = faulhaberTriangle(9),
        widths = ratioWidths(triangle);
 
    return unlines(
            map(row =>
                concat(map(cell =>
                    justifyRatio(widths, 8, ' ', cell), row)), triangle)
        ) +
        '\n\n' + unlines(
            [
                'faulhaber(17, 1000)',
                justifyRatio(widths, 0, ' ', faulhaber(17, 1000)),
                '\nfaulhaber(17, 8)',
                justifyRatio(widths, 0, ' ', faulhaber(17, 8)),
                '\nfaulhaber(4, 1000)',
                justifyRatio(widths, 0, ' ', faulhaber(4, 1000)),
            ]
        );
})();