How to resolve the algorithm Faulhaber's triangle step by step in the Nim programming language

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm Faulhaber's triangle step by step in the Nim programming language

Table of Contents

Problem Statement

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:

where

B

n

{\displaystyle B_{n}}

is the nth-Bernoulli number.

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

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}}

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Faulhaber's triangle step by step in the Nim programming language

Source code in the nim programming language

import algorithm, math, strutils
import bignum

type FaulhaberSequence = seq[Rat]

#---------------------------------------------------------------------------------------------------

func bernoulli(n: Natural): Rat =
  ## Return nth Bernoulli coefficient.

  var a = newSeq[Rat](n + 1)
  for m in 0..n:
    a[m] = newRat(1, m + 1)
    for k in countdown(m, 1):
      a[k - 1] = (a[k - 1] - a[k]) * k
  result = if n != 1: a[0] else: -a[0]

#---------------------------------------------------------------------------------------------------

func faulhaber(n: Natural): FaulhaberSequence =
  ## Return nth Faulhaber sequence (high degree first).

  var a = newRat(1, n + 1)
  var sign = -1
  for k in 0..n:
    sign = -sign
    result.add(a * sign * binom(n + 1, k) * bernoulli(k))

#---------------------------------------------------------------------------------------------------

proc display(fs: FaulhaberSequence) =
  ## Return the string representing a Faulhaber sequence.

  var str = ""
  for i, coeff in reversed(fs):
    str.addSep(" ", 0)
    str.add(($coeff).align(6))
  echo str

#---------------------------------------------------------------------------------------------------

func evaluate(fs: FaulhaberSequence; n: int): Rat =
  ## Evaluate the polynomial associated to a sequence for value "n".

  result = newRat(0)
  for coeff in fs:
    result = result * n + coeff
  result *= n

#———————————————————————————————————————————————————————————————————————————————————————————————————

for n in 0..9:
  display(faulhaber(n))

echo ""
let fs18 = faulhaber(17)  # 18th row.
echo fs18.evaluate(1000)

You may also check:How to resolve the algorithm Abbreviations, easy step by step in the Pascal programming language
You may also check:How to resolve the algorithm Hello world/Newbie step by step in the Zig programming language
You may also check:How to resolve the algorithm Convert seconds to compound duration step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Two bullet roulette step by step in the Python programming language
You may also check:How to resolve the algorithm File modification time step by step in the Slate programming language