Faulhaber's triangle: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
(15 intermediate revisions by 9 users not shown) | |||
Line 36:
* [http://www.ww.ingeniousmathstat.org/sites/default/files/Torabi-Dashti-CMJ-2011.pdf Faulhaber's triangle (PDF)]
<br>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Using code from the Algol 68 samples for the [[Arithmetic/Rational]] and [[Bernoulli numbers]] tasks and the Algol W sample for the [[Evaluate binomial coefficients]] task.<br>
Note that in the Bernoulli numbers task, the Algol 68 sample returns -1/2 for B(1) - this is modified here so B(1) is 1/2.<br>
Assumes LONG LONG INT is long enough to calculate the 17th power sum, the default precision of LONG LONG INT in ALGOL 68G is large enough.
<syntaxhighlight lang="algol68">
BEGIN # show some rows of Faulhaber's triangle #
# utility operators #
OP LENGTH = ( STRING a )INT: ( UPB a - LWB a ) + 1;
PRIO PAD = 9;
OP PAD = ( INT width, STRING v )STRING: # left blank pad v to width #
IF LENGTH v >= width THEN v ELSE ( " " * ( width - LENGTH v ) ) + v FI;
MODE INTEGER = LONG LONG INT; # mode for FRAC numberator & denominator #
OP TOINTEGER = ( INT n )INTEGER: n; # force widening n to INTEGER #
# Code from the Arithmetic/Rational task #
MODE FRAC = STRUCT( INTEGER num #erator#, den #ominator#);
PROC gcd = (INTEGER a, b) INTEGER: # greatest common divisor #
(a = 0 | b |: b = 0 | a |: ABS a > ABS b | gcd(b, a MOD b) | gcd(a, b MOD a));
PROC lcm = (INTEGER a, b)INTEGER: # least common multiple #
a OVER gcd(a, b) * b;
PRIO // = 9; # higher then the ** operator #
OP // = (INTEGER num, den)FRAC: ( # initialise and normalise #
INTEGER common = gcd(num, den);
IF den < 0 THEN
( -num OVER common, -den OVER common)
ELSE
( num OVER common, den OVER common)
FI
);
OP + = (FRAC a, b)FRAC: (
INTEGER common = lcm(den OF a, den OF b);
FRAC result := ( common OVER den OF a * num OF a + common OVER den OF b * num OF b, common );
num OF result//den OF result
);
OP - = (FRAC a, b)FRAC: a + -b,
* = (FRAC a, b)FRAC: (
INTEGER num = num OF a * num OF b,
den = den OF a * den OF b;
INTEGER common = gcd(num, den);
(num OVER common) // (den OVER common)
);
OP - = (FRAC frac)FRAC: (-num OF frac, den OF frac);
# end code from the Arithmetic/Rational task #
# alternative // operator for standard size INT values #
OP // = (INT num, den)FRAC: TOINTEGER num // TOINTEGER den;
# returns a * b #
OP * = ( INT a, FRAC b )FRAC: ( num OF b * a ) // den OF b;
OP * = ( INTEGER a, FRAC b )FRAC: ( num OF b * a ) // den OF b;
# sets a to a + b and returns a #
OP +:= = ( REF FRAC a, FRAC b )FRAC: a := a + b;
# sets a to - a and returns a #
OP -=: = ( REF FRAC a )FRAC: BEGIN num OF a := - num OF a; a END;
# returns the nth Bernoulli number, n must be >= 0 #
OP BERNOULLI = ( INT n )FRAC:
IF n < 0
THEN # n is out of range # 0 // 1
ELSE # n is valid #
[ 0 : n ]FRAC a;
FOR m FROM 0 TO n DO
a[ m ] := 1 // ( m + 1 );
FOR j FROM m BY -1 TO 1 DO
a[ j - 1 ] := j * ( a[ j - 1 ] - a[ j ] )
OD
OD;
IF n = 1 THEN - a[ 0 ] ELSE a[ 0 ] FI
FI # BERNOULLI # ;
# returns n! / k! #
PROC factorial over factorial = ( INT n, k )INTEGER:
IF k > n THEN 0
ELIF k = n THEN 1
ELSE # k < n #
INTEGER f := 1;
FOR i FROM k + 1 TO n DO f *:= i OD;
f
FI # factorial over Factorial # ;
# returns n! #
PROC factorial = ( INT n )INTEGER:
BEGIN
INTEGER f := 1;
FOR i FROM 2 TO n DO f *:= i OD;
f
END # factorial # ;
# returns the binomial coefficient of (n k) #
PROC binomial coefficient = ( INT n, k )INTEGER:
IF n - k > k
THEN factorial over factorial( n, n - k ) OVER factorial( k )
ELSE factorial over factorial( n, k ) OVER factorial( n - k )
FI # binomial coefficient # ;
# returns a string representation of a #
OP TOSTRING = ( FRAC a )STRING:
whole( num OF a, 0 ) + IF den OF a = 1 THEN "" ELSE "/" + whole( den OF a, 0 ) FI;
# returns the pth row of Faulhaber's triangle #
OP FAULHABER = ( INT p )[]FRAC:
BEGIN
FRAC q := -1 // ( p + 1 );
[ 0 : p ]FRAC coeffs;
FOR j FROM 0 TO p DO
coeffs[ p - j ] := binomial coefficient( p + 1, j ) * BERNOULLI j * -=: q
OD;
coeffs
END # faulhaber # ;
FOR i FROM 0 TO 9 DO # show the triabngle's first 10 rows #
[]FRAC frow = FAULHABER i;
FOR j FROM LWB frow TO UPB frow DO
print( ( " ", 6 PAD TOSTRING frow[ j ] ) )
OD;
print( ( newline ) )
OD;
BEGIN # compute the sum of k^17 for k = 1 to 1000 using triangle row 18 #
[]FRAC frow = FAULHABER 17;
FRAC sum := 0 // 1;
INTEGER kn := 1;
FOR j FROM LWB frow TO UPB frow DO
VOID( sum +:= ( kn *:= 1000 ) * frow[ j ] )
OD;
print( ( TOSTRING sum, newline ) )
END
END
</syntaxhighlight>
{{out}}
<pre>
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
0 -1/12 0 5/12 1/2 1/6
1/42 0 -1/6 0 1/2 1/2 1/7
0 1/12 0 -7/24 0 7/12 1/2 1/8
-1/30 0 2/9 0 -7/15 0 2/3 1/2 1/9
0 -3/20 0 1/2 0 -7/10 0 3/4 1/2 1/10
56056972216555580111030077961944183400198333273050000
</pre>
=={{header|C}}==
{{trans|C++}}
<
#include <stdio.h>
#include <stdlib.h>
Line 196 ⟶ 349:
return 0;
}</
{{out}}
<pre> 1
Line 211 ⟶ 364:
=={{header|C sharp|C#}}==
{{trans|Java}}
<
namespace FaulhabersTriangle {
Line 365 ⟶ 518:
}
}
}</
{{out}}
<pre> 1
Line 381 ⟶ 534:
{{trans|C#}}
Uses C++ 17
<
#include <iomanip>
#include <iostream>
Line 503 ⟶ 656:
return 0;
}</
{{out}}
<pre> 1
Line 518 ⟶ 671:
=={{header|D}}==
{{trans|Kotlin}}
<
import std.conv : to;
import std.exception : enforce;
Line 651 ⟶ 804:
}
writeln;
}</
{{out}}
<pre> 1
Line 666 ⟶ 819:
=={{header|F_Sharp|F#}}==
===The Function===
<
// Generate Faulhaber's Triangle. Nigel Galloway: May 8th., 2018
let Faulhaber=let fN n = (1N - List.sum n)::n
Line 673 ⟶ 826:
yield! Faul t (b+1N)}
Faul [] 0N
</syntaxhighlight>
===The Task===
<
Faulhaber |> Seq.take 10 |> Seq.iter (printfn "%A")
</syntaxhighlight>
{{out}}
<pre>
Line 693 ⟶ 846:
=={{header|Factor}}==
<
math.ranges prettyprint sequences ;
Line 700 ⟶ 853:
[ [ nCk ] [ -1 swap ^ ] [ bernoulli ] tri * * * ] 2with map ;
10 [ faulhaber . ] each-integer</
{{out}}
<pre>
Line 717 ⟶ 870:
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<
' compile with: fbc -s console
' uses GMP
Line 804 ⟶ 957:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>The first 10 rows
Line 822 ⟶ 975:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Faulhaber}}
'''Solution'''
The following function creates the Faulhaber's coefficients up to a given number of rows, according to the [http://www.ww.ingeniousmathstat.org/sites/default/files/Torabi-Dashti-CMJ-2011.pdf paper] of of Mohammad Torabi Dashti:
(This is exactly the same as the task [[Faulhaber%27s_formula#F%C5%8Drmul%C3%A6|Faulhaber's formula]])
[[File:Fōrmulæ - Faulhaber 01.png]]
'''Excecise 1.''' To show the first 11 rows (the first is the 0 row) of Faulhaber's triangle:
[[File:Fōrmulæ - Faulhaber 02.png]]
[[File:Fōrmulæ - Faulhaber 03.png]]
In order to show the previous result as a triangle:
[[File:Fōrmulæ - Faulhaber 04.png]]
[[File:Fōrmulæ - Faulhaber 05.png]]
The following function creates the sum of the p-th powers of the first n positive integers as a (p + 1)th-degree polynomial function of n:
Notes. The -1 index means the last element (-2 is the penultimate element, and so on). So it retrieves the last row of the triangle. |x| is the cardinality (number of elements) of x.
(This is exactly the same as the task [[Faulhaber%27s_formula#F%C5%8Drmul%C3%A6|Faulhaber's formula]])
This function can be used for both symbolic or numeric computation of the polynomial:
[[File:Fōrmulæ - Faulhaber 06.png]]
'''Excecise 2.''' Using the 18th row of Faulhaber's triangle, compute the sum <math>\sum_{k=1}^{1000} k^{17}</math>
[[File:Fōrmulæ - Faulhaber 09.png]]
[[File:Fōrmulæ - Faulhaber 10.png]]
Verification:
[[File:Fōrmulæ - Faulhaber 11.png]]
[[File:Fōrmulæ - Faulhaber 10.png]]
=={{header|Go}}==
{{trans|Kotlin}}
Except that there is no need to roll our own Frac type when we can use the big.Rat type from the Go standard library.
<
import (
Line 912 ⟶ 1,103:
}
fmt.Println(sum.RatString())
}</
{{out}}
Line 932 ⟶ 1,123:
=={{header|Groovy}}==
{{trans|Java}}
<
import java.util.stream.LongStream
Line 1,071 ⟶ 1,262:
println(sum.toBigInteger())
}
}</
{{out}}
<pre> 1
Line 1,086 ⟶ 1,277:
=={{header|Haskell}}==
{{works with|GHC|8.6.4}}
<
------------------------ FAULHABER -----------------------
Line 1,158 ⟶ 1,349:
let widest f xs = maximum $ fmap (length . show . f) xs
in ((,) . widest numerator <*> widest denominator) $
concat xss</
{{Out}}
<pre> 1
Line 1,219 ⟶ 1,410:
{{trans|Kotlin}}
{{works with|Java|8}}
<
import java.math.MathContext;
import java.util.Arrays;
Line 1,360 ⟶ 1,551:
System.out.println(sum.toBigInteger());
}
}</
{{out}}
<pre> 1
Line 1,381 ⟶ 1,572:
(Further progress would entail implementing some hand-crafted representation of arbitrary precision integers – perhaps a bit beyond the intended scope of this task, and good enough motivation to use a different language)
<
// Order of Faulhaber's triangle -> rows of Faulhaber's triangle
Line 1,659 ⟶ 1,850:
]
);
})();</
{{Out}}
<pre> 1
Line 1,694 ⟶ 1,885:
(*) The C implementation of jq does not have sufficient numeric precision for the "extra credit" task.
<
# Preliminaries
Line 1,761 ⟶ 1,952:
(faulhabersum(1000; 17) | rpp) ;
testfaulhaber</
{{out}}
<pre>
Line 1,781 ⟶ 1,972:
=={{header|Julia}}==
<
A = Vector{Rational{BigInt}}(undef, n + 1)
for i in 0:n
Line 1,818 ⟶ 2,009:
testfaulhaber()
</
<pre>
1
Line 1,836 ⟶ 2,027:
=={{header|Kotlin}}==
Uses appropriately modified code from the Faulhaber's Formula task:
<
import java.math.BigDecimal
Line 1,956 ⟶ 2,147:
}
println(sum.toBigInteger())
}</
{{out}}
Line 1,976 ⟶ 2,167:
=={{header|Lua}}==
{{trans|C}}
<
if n<0 or k<0 or n<k then return -1 end
if n==0 or k==0 then return 1 end
Line 2,098 ⟶ 2,289:
for i=0,9 do
faulhaber(i)
end</
{{out}}
<pre> 1
Line 2,113 ⟶ 2,304:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
bernoulliB[1] := 1/2
bernoulliB[n_] := BernoulliB[n]
Faulhaber[n_, p_] := 1/(p + 1) Sum[Binomial[p + 1, j] bernoulliB[j] n^(p + 1 - j), {j, 0, p}]
Table[Rest@CoefficientList[Faulhaber[n, t], n], {t, 0, 9}] // Grid
Faulhaber[1000, 17]</
{{out}}
<pre>1
Line 2,131 ⟶ 2,322:
0 -(3/20) 0 1/2 0 -(7/10) 0 3/4 1/2 1/10
56056972216555580111030077961944183400198333273050000</pre>
=={{header|Maxima|}}==
<syntaxhighlight lang="maxima">
faulhaber_fraction(n, k) :=
if n = 0 and k = 1 then 1
else if k >= 2 and k <= n + 1 then (n/k) * faulhaber_fraction(n-1, k-1)
else if k = 1 then 1 - sum(faulhaber_fraction(n, i), i, 2, n+1)
else 0$
faulhaber_row(n):=makelist(faulhaber_fraction(n,k),k,1,n+1)$
/* Example */
triangle_faulhaber_first_ten_rows:block(makelist(faulhaber_row(i),i,0,9),table_form(%%));
</syntaxhighlight>
[[File:Faulhaber.png|thumb|center]]
=={{header|Nim}}==
{{libheader|bignum}}
For the task, we could use the standard module “rationals” but for the extra task we need big numbers (and big rationals). We use third party module “bignum” for this purpose.
<
import bignum
Line 2,191 ⟶ 2,396:
echo ""
let fs18 = faulhaber(17) # 18th row.
echo fs18.evaluate(1000)</
{{out}}
Line 2,206 ⟶ 2,411:
56056972216555580111030077961944183400198333273050000</pre>
=={{header|Pascal}}==
{{libheader|IntXLib4Pascal}}
A console application in Free Pascal, created with the Lazarus IDE.
Row numbering below is 0-based, so row r has r+1 elements. Rather than use a rational number type, the program scales up row r by (r+1)!, which means that all the entries are integers.
<syntaxhighlight lang="pascal">
program FaulhaberTriangle;
uses uIntX, uEnums, // units in the library IntXLib4Pascal
SysUtils;
// Convert a rational num/den to a string, right-justified in the given width.
// Before converting, remove any common factor of num and den.
// For this application we can assume den > 0.
function RationalToString( num, den : TIntX;
minWidth : integer) : string;
var
num1, den1, divisor : TIntX;
w : integer;
begin
divisor := TIntX.GCD( num, den);
// TIntx.Divide requires the caller to specifiy the division mode
num1 := TIntx.Divide( num, divisor, uEnums.dmClassic);
den1 := TIntx.Divide( den, divisor, uEnums.dmClassic);
result := num1.ToString;
if not den1.IsOne then result := result + '/' + den1.ToString;
w := minWidth - Length( result);
if (w > 0) then result := StringOfChar(' ', w) + result;
end;
// Main routine
const
r_MAX = 17;
var
g : array [1..r_MAX + 1] of TIntX;
r, s, k : integer;
r_1_fac, sum, k_intx : TIntX;
begin
// Calculate rows 0..17 of Faulhaner's triangle, and show rows 0..9.
// For a given r, the subarray g[1..(r+1)] contains (r + 1)! times row r.
r_1_fac := 1; // (r + 1)!
g[1] := 1;
for r := 0 to r_MAX do begin
r_1_fac := r_1_fac * (r+1);
sum := 0;
for s := r downto 1 do begin
g[s + 1] := r*(r+1)*g[s] div (s+1);
sum := sum + g[s + 1];
end;
g[1] := r_1_fac - sum; // the scaled row must sum to (r + 1)!
if (r <= 9) then begin
for s := 1 to r + 1 do Write( RationalToString( g[s], r_1_fac, 7));
WriteLn;
end;
end;
// Use row 17 to sum 17th powers from 1 to 1000
sum := 0;
for s := r_MAX + 1 downto 1 do sum := (sum + g[s]) * 1000;
sum := TIntx.Divide( sum, r_1_fac, uEnums.dmClassic);
WriteLn;
WriteLn( 'Sum by Faulhaber = ' + sum.ToString);
// Check by direct calculation
sum := 0;
for k := 1 to 1000 do begin
k_intx := k;
sum := sum + TIntX.Pow( k_intx, r_MAX);
end;
WriteLn( 'by direct calc. = ' + sum.ToString);
end.
</syntaxhighlight>
{{out}}
<pre>
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
0 -1/12 0 5/12 1/2 1/6
1/42 0 -1/6 0 1/2 1/2 1/7
0 1/12 0 -7/24 0 7/12 1/2 1/8
-1/30 0 2/9 0 -7/15 0 2/3 1/2 1/9
0 -3/20 0 1/2 0 -7/10 0 3/4 1/2 1/10
Sum by Faulhaber = 56056972216555580111030077961944183400198333273050000
by direct calc. = 56056972216555580111030077961944183400198333273050000
</pre>
=={{header|Perl}}==
{{libheader|ntheory}}
<
use List::Util qw(sum);
use Math::BigRat try => 'GMP';
Line 2,232 ⟶ 2,526:
my $n = Math::BigInt->new(1000);
my @r = faulhaber_triangle($p+1);
say "\n", sum(map { $r[$_] * $n**($_ + 1) } 0 .. $#r);</
{{out}}
<pre>
Line 2,251 ⟶ 2,545:
=={{header|Phix}}==
{{trans|C#}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">\</span><span style="color: #000000;">pfrac</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> <span style="color: #000080;font-style:italic;">-- (0.8.0+)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">bernoulli</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">a</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">m</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">frac_mul</span><span style="color: #0000FF;">({</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">frac_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">frac_uminus</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">binomial</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">k</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">num</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">denom</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">num</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">k</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">denom</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">num</span> <span style="color: #0000FF;">/</span> <span style="color: #000000;">denom</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">faulhaber_triangle</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">asString</span><span style="color: #0000FF;">=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">coeffs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">frac_zero</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">p</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">frac</span> <span style="color: #000000;">coeff</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">frac_mul</span><span style="color: #0000FF;">({</span><span style="color: #000000;">binomial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">),</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">bernoulli</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">coeffs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">asString</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%5s"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">frac_sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">coeff</span><span style="color: #0000FF;">)}):</span><span style="color: #000000;">coeff</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">coeffs</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">faulhaber_triangle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">),</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">row18</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">faulhaber_triangle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">frac</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">frac_zero</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">bigatom</span> <span style="color: #000000;">nn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">BA_ONE</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">row18</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">frac_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">frac_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">row18</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],{</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}))</span>
<span style="color: #000000;">nn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ba_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"calculating, k=%d...\r"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s \n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">frac_sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,321 ⟶ 2,620:
56056972216555580111030077961944183400198333273050000
</pre>
Note the extra credit takes about 90s, so I disabled it under pwa/p2js.
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
ft_rows(Lz) :-
lazy_list(ft_row, [], Lz).
Line 2,357 ⟶ 2,657:
drop(N, Lz1, Lz2) :-
append(Pfx, Lz2, Lz1), length(Pfx, N), !.
</syntaxhighlight>
{{Out}}
<pre>
Line 2,380 ⟶ 2,680:
{{trans|Haskell}}
{{Works with|Python|3.7}}
<
from itertools import accumulate, chain, count, islice
Line 2,527 ⟶ 2,827:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Faulhaber's triangle:
Line 2,546 ⟶ 2,846:
=={{header|Racket}}==
<
(require math/number-theory)
Line 2,569 ⟶ 2,869:
(require rackunit)
(check-equal? (sum-k^p:formulaic 17 1000)
(for/sum ((k (in-range 1 (add1 1000)))) (expt k 17))))</
{{out}}
<pre>'((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) (0 -1/12 0 5/12 1/2 1/6) (1/42 0 -1/6 0 1/2 1/2 1/7) (0 1/12 0 -7/24 0 7/12 1/2 1/8) (-1/30 0 2/9 0 -7/15 0 2/3 1/2 1/9) (0 -3/20 0 1/2 0 -7/10 0 3/4 1/2 1/10))
Line 2,579 ⟶ 2,879:
{{trans|Sidef}}
<syntaxhighlight lang="raku"
sub infix:<reduce> (\prev, \this) { this.key => this.key * (this.value - prev.value) }
Line 2,604 ⟶ 2,904:
my $p = 17;
my $n = 1000;
say sum faulhaber_triangle($p).kv.map: { $^value * $n**($^key + 1) }</
{{out}}
<pre> 1
Line 2,620 ⟶ 2,920:
=={{header|REXX}}==
<
Do r=0 To 20
ra=r-1
Line 2,718 ⟶ 3,018:
Parse Arg a,b
if b = 0 then return abs(a)
return gcd(b,a//b)</
{{out}}
<pre> 1
Line 2,736 ⟶ 3,036:
=={{header|Ruby}}==
{{trans|D}}
<
attr_accessor:num
attr_accessor:denom
Line 2,862 ⟶ 3,162:
end
main()</
{{out}}
<pre> 1
Line 2,877 ⟶ 3,177:
=={{header|Scala}}==
{{trans|Java}}
<
import scala.collection.mutable
Line 3,028 ⟶ 3,328:
println()
}
}</
{{out}}
<pre> 1
Line 3,040 ⟶ 3,340:
-1/30 0 2/9 0 -7/15 0 2/3 1/2 1/9
0 -3/20 0 1/2 0 -7/10 0 3/4 1/2 1/10 </pre>
=={{header|Scheme}}==
{{works with|Chez Scheme}}
<syntaxhighlight lang="scheme">; Return the first row-count rows of Faulhaber's Triangle as a vector of vectors.
(define faulhabers-triangle
(lambda (row-count)
; Calculate and store the value of the first column of a row.
; The value is one minus the sum of all the rest of the columns.
(define calc-store-first!
(lambda (row)
(vector-set! row 0
(do ((col-inx 1 (1+ col-inx))
(col-sum 0 (+ col-sum (vector-ref row col-inx))))
((>= col-inx (vector-length row)) (- 1 col-sum))))))
; Generate the Faulhaber's Triangle one row at a time.
; The element at row i >= 0, column j >= 1 (both 0-based) is the product
; of the element at i - 1, j - 1 and the fraction ( i / ( j + 1 ) ).
; The element at column 0 is one minus the sum of all the rest of the columns.
(let ((tri (make-vector row-count)))
(do ((row-inx 0 (1+ row-inx)))
((>= row-inx row-count) tri)
(let ((row (make-vector (1+ row-inx))))
(vector-set! tri row-inx row)
(do ((col-inx 1 (1+ col-inx)))
((>= col-inx (vector-length row)))
(vector-set! row col-inx
(* (vector-ref (vector-ref tri (1- row-inx)) (1- col-inx))
(/ row-inx (1+ col-inx)))))
(calc-store-first! row))))))
; Convert elements of a vector to a string for display.
(define vector->string
(lambda (vec)
(do ((inx 0 (1+ inx))
(str "" (string-append str (format "~7@a" (vector-ref vec inx)))))
((>= inx (vector-length vec)) str))))
; Display a Faulhaber's Triangle.
(define faulhabers-triangle-display
(lambda (tri)
(do ((inx 0 (1+ inx)))
((>= inx (vector-length tri)))
(printf "~a~%" (vector->string (vector-ref tri inx))))))
; Task..
(let ((row-count 10))
(printf "The first ~a rows of Faulhaber's Triangle..~%" row-count)
(faulhabers-triangle-display (faulhabers-triangle row-count)))
(newline)
(let ((power 17)
(sum-to 1000))
(printf "Sum over k=1..~a of k^~a using Faulhaber's Triangle..~%" sum-to power)
(let* ((tri (faulhabers-triangle (1+ power)))
(coefs (vector-ref tri power)))
(printf "~a~%" (do ((inx 0 (1+ inx))
(term-expt sum-to (* term-expt sum-to))
(sum 0 (+ sum (* (vector-ref coefs inx) term-expt))))
((>= inx (vector-length coefs)) sum)))))</syntaxhighlight>
{{out}}
<pre>
The first 10 rows of Faulhaber's Triangle..
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
0 -1/12 0 5/12 1/2 1/6
1/42 0 -1/6 0 1/2 1/2 1/7
0 1/12 0 -7/24 0 7/12 1/2 1/8
-1/30 0 2/9 0 -7/15 0 2/3 1/2 1/9
0 -3/20 0 1/2 0 -7/10 0 3/4 1/2 1/10
Sum over k=1..1000 of k^17 using Faulhaber's Triangle..
56056972216555580111030077961944183400198333273050000
</pre>
=={{header|Sidef}}==
<
{ binomial(p, _) * bernoulli(_) / p }.map(p ^.. 0)
}
Line 3,054 ⟶ 3,428:
say ''
say faulhaber_triangle(p+1).map_kv {|k,v| v * n**(k+1) }.sum</
{{out}}
<pre>
Line 3,072 ⟶ 3,446:
Alternative solution:
<
var c = 0
loop {
Line 3,093 ⟶ 3,467:
}
10.times { say faulhaber_triangle(_) }</
{{out}}
<pre>
Line 3,110 ⟶ 3,484:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Class Frac
Line 3,259 ⟶ 3,633:
End Sub
End Module</
{{out}}
<pre> 1
Line 3,271 ⟶ 3,645:
-1/30 0 2/9 0 -7/15 0 2/3 1/2 1/9
0 -3/20 0 1/2 0 -7/10 0 3/4 1/2 1/10</pre>
=={{header|V (Vlang)}}==
{{trans|Go}}
<syntaxhighlight lang="v (vlang)">import math.fractions
import math.big
fn bernoulli(n int) fractions.Fraction {
mut a := []fractions.Fraction{len: n+1}
for m,_ in a {
a[m] = fractions.fraction(1, i64(m+1))
for j := m; j >= 1; j-- {
mut d := a[j-1]
d = fractions.fraction(i64(j),i64(1)) * (d-a[j])
a[j-1]=d
}
}
// return the 'first' Bernoulli number
if n != 1 {
return a[0]
}
a[0] = a[0].negate()
return a[0]
}
fn binomial(n int, k int) i64 {
if n <= 0 || k <= 0 || n < k {
return 1
}
mut num, mut den := i64(1), i64(1)
for i := k + 1; i <= n; i++ {
num *= i64(i)
}
for i := 2; i <= n-k; i++ {
den *= i64(i)
}
return num / den
}
fn faulhaber_triangle(p int) []fractions.Fraction {
mut coeffs := []fractions.Fraction{len: p+1}
q := fractions.fraction(1, i64(p)+1)
mut t := fractions.fraction(1,1)
mut u := fractions.fraction(1,1)
mut sign := -1
for j,_ in coeffs {
sign *= -1
mut d := coeffs[p-j]
t=fractions.fraction(i64(sign),1)
u = fractions.fraction(binomial(p+1, j),1)
d=q*t
d*=u
d*=bernoulli(j)
coeffs[p-j]=d
}
return coeffs
}
fn main() {
for i in 0..10 {
coeffs := faulhaber_triangle(i)
for coeff in coeffs {
print("${coeff:5} ")
}
println('')
}
println('')
}</syntaxhighlight>
{{out}}
<pre>
1/1
1/2 1/2
1/6 1/2 1/3
0/1 1/4 1/2 1/4
-1/30 0/1 1/3 1/2 1/5
0/1 -1/12 0/1 5/12 1/2 1/6
1/42 0/1 -1/6 0/1 1/2 1/2 1/7
0/1 1/12 0/1 -7/24 0/1 7/12 1/2 1/8
-1/30 0/1 2/9 0/1 -7/15 0/1 2/3 1/2 1/9
0/1 -3/20 0/1 1/2 0/1 -7/10 0/1 3/4 1/2 1/10
</pre>
=={{header|Wren}}==
Line 3,277 ⟶ 3,732:
{{libheader|Wren-math}}
{{libheader|Wren-big}}
<
import "./math" for Int
import "./big" for BigRat
var bernoulli = Fn.new { |n|
Line 3,337 ⟶ 3,792:
sum = sum + np*c
}
System.print(sum)</
{{out}}
Line 3,358 ⟶ 3,813:
{{libheader|GMP}} GNU Multiple Precision Arithmetic Library
Uses the code from [[Faulhaber's formula#zkl]]
<
faulhaberFormula(p).apply("%7s".fmt).concat().println();
}
Line 3,366 ⟶ 3,821:
.walk() // -->(0, -3617/60 * 1000^2, 0, 595/3 * 1000^4 ...)
.reduce('+) // rat + rat + ...
.println();</
{{out}}
<pre>
|