Faulhaber's triangle: Difference between revisions
(New draft task) |
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Add a Perl6 example) |
||
Line 35: | Line 35: | ||
* [https://en.wikipedia.org/wiki/Faulhaber%27s_formula Faulhaber's formula (Wikipedia)] |
* [https://en.wikipedia.org/wiki/Faulhaber%27s_formula Faulhaber's formula (Wikipedia)] |
||
* [http://www.ww.ingeniousmathstat.org/sites/default/files/Torabi-Dashti-CMJ-2011.pdf Faulhaber's triangle (PDF)] |
* [http://www.ww.ingeniousmathstat.org/sites/default/files/Torabi-Dashti-CMJ-2011.pdf Faulhaber's triangle (PDF)] |
||
=={{header|Perl 6}}== |
|||
{{works with|Rakudo|2017.05}} |
|||
{{trans|Sidef}} |
|||
<lang perl6># Helper subs |
|||
sub infix:<reduce>(\prev, \this) { this.key => this.key * (this.value - prev.value) } |
|||
sub next-bernoulli ( (:key($pm), :value(@pa)) ) { |
|||
$pm + 1 => [ map *.value, [\reduce] ($pm + 2 ... 1) Z=> FatRat.new(1, $pm + 2), |@pa ] |
|||
} |
|||
constant bernoulli = (0 => [1.FatRat], &next-bernoulli ... *).map: { .value[*-1] }; |
|||
sub binomial (Int $n, Int $p) { combinations($n, $p).elems }; |
|||
sub asRat(FatRat $r) { $r ?? $r.denominator == 1 ?? $r.numerator !! $r.nude.join('/') !! 0 }; |
|||
# The task |
|||
sub faulhaber_triangle ($p) { map { binomial($p+1, $_) * bernoulli[$_] / ($p+1) }, ($p ... 0) } |
|||
# First 10 rows of Faulhaber's triangle: |
|||
say faulhaber_triangle($_)».&asRat.fmt('%6s') for ^10; |
|||
say ''; |
|||
# Extra credit: |
|||
my $p = 17; |
|||
my $n = 1000; |
|||
say sum faulhaber_triangle($p).kv.map: { $^value * $n**($^key + 1) };</lang> |
|||
{{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|Sidef}}== |
=={{header|Sidef}}== |
Revision as of 22:13, 6 June 2017
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 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:
- Task
- show the first 10 rows of Faulhaber's triangle.
- using the 17th row of Faulhaber's triangle, compute the sum: (extra credit).
- See also
- Bernoulli numbers
- Evaluate binomial coefficients
- Faulhaber's formula (Wikipedia)
- Faulhaber's triangle (PDF)
Perl 6
<lang perl6># Helper subs
sub infix:<reduce>(\prev, \this) { this.key => this.key * (this.value - prev.value) }
sub next-bernoulli ( (:key($pm), :value(@pa)) ) {
$pm + 1 => [ map *.value, [\reduce] ($pm + 2 ... 1) Z=> FatRat.new(1, $pm + 2), |@pa ]
}
constant bernoulli = (0 => [1.FatRat], &next-bernoulli ... *).map: { .value[*-1] };
sub binomial (Int $n, Int $p) { combinations($n, $p).elems };
sub asRat(FatRat $r) { $r ?? $r.denominator == 1 ?? $r.numerator !! $r.nude.join('/') !! 0 };
- The task
sub faulhaber_triangle ($p) { map { binomial($p+1, $_) * bernoulli[$_] / ($p+1) }, ($p ... 0) }
- First 10 rows of Faulhaber's triangle:
say faulhaber_triangle($_)».&asRat.fmt('%6s') for ^10; say ;
- Extra credit:
my $p = 17; my $n = 1000; say sum faulhaber_triangle($p).kv.map: { $^value * $n**($^key + 1) };</lang>
- Output:
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
Sidef
<lang ruby>func faulhaber_triangle(p) {
gather { for j in (p+1 ^.. 0) { take(binomial(p+1, j) * bernoulli(j) / (p+1)) } }
}
-
- First 10 rows of Faulhaber's triangle:
for p in (0 .. 9) {
say faulhaber_triangle(p).map{ '%6s' % .as_rat }.join
}
-
- Extra credit:
const p = 17 const n = 1000
say say faulhaber_triangle(p).map_kv{|k,v| v * n**(k+1) }.sum</lang>
- Output:
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