Binomial transform: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (Show self inverting variant for reference) |
Thundergnat (talk | contribs) m (→{{header|Raku}}: Show self inverting variant also, other minor twiddles) |
||
Line 487: | Line 487: | ||
sub inverse-binomial-transform (*@seq) { |
sub inverse-binomial-transform (*@seq) { |
||
@seq.keys.map: -> \n { sum (0..n).map: -> \k { |
@seq.keys.map: -> \n { sum (0..n).map: -> \k { binomial(n,k) × @seq[k] × exp(n - k, -1) } } |
||
} |
|||
sub si-binomial-transform (*@seq) { #self inverting |
|||
@seq.keys.map: -> \n { sum (0..n).map: -> \k { binomial(n,k) × @seq[k] × exp(k, -1) } } |
|||
} |
} |
||
my $upto = 20; |
my $upto = 20; |
||
for 'Catalan number', (1, { |
for 'Catalan number', (1, {[+] @_ Z× @_.reverse}…*), |
||
'Prime flip-flop', (1..*). |
'Prime flip-flop', (1..*).grep(&is-prime).map(+*), |
||
'Fibonacci number', (0 |
'Fibonacci number', (0,1,*+*…*), |
||
'Padovan number', (1,0,0, -> $c,$b,$ {$b+$c}…*) |
'Padovan number', (1,0,0, -> $c,$b,$ {$b+$c}…*) |
||
-> $name, @seq { |
-> $name, @seq { |
||
Line 506: | Line 510: | ||
Round trip: |
Round trip: |
||
{inverse-binomial-transform(binomial-transform(@seq))[^$upto]} |
{inverse-binomial-transform(binomial-transform(@seq))[^$upto]} |
||
Self inverting: |
|||
{si-binomial-transform(@seq)[^$upto]} |
|||
Re inverted: |
|||
{si-binomial-transform(si-binomial-transform(@seq))[^$upto]} |
|||
BIN |
BIN |
||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Catalan number sequence: |
<pre style="height:40ex;overflow:scroll;">Catalan number sequence: |
||
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 |
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 |
||
Forward binomial transform: |
Forward binomial transform: |
||
Line 516: | Line 524: | ||
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 |
1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 |
||
Round trip: |
Round trip: |
||
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 |
|||
Self inverting: |
|||
1 0 1 -1 3 -6 15 -36 91 -232 603 -1585 4213 -11298 30537 -83097 227475 -625992 1730787 -4805595 |
|||
Re inverted: |
|||
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 |
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 |
||
Prime flip-flop sequence: |
Prime flip-flop sequence: |
||
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 |
|||
Forward binomial transform: |
Forward binomial transform: |
||
2 5 13 33 83 205 495 1169 2707 6169 13889 30993 68701 151469 332349 725837 1577751 3413221 7349029 15751187 |
|||
0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952 |
|||
Inverse binomial transform: |
Inverse binomial transform: |
||
2 1 1 -1 3 -9 23 -53 115 -237 457 -801 1213 -1389 445 3667 -15081 41335 -95059 195769 |
|||
Round trip: |
Round trip: |
||
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 |
|||
Self inverting: |
|||
2 -1 1 1 3 9 23 53 115 237 457 801 1213 1389 445 -3667 -15081 -41335 -95059 -195769 |
|||
Re inverted: |
|||
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 |
|||
Fibonacci number sequence: |
Fibonacci number sequence: |
||
Line 534: | Line 550: | ||
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181 |
0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181 |
||
Round trip: |
Round trip: |
||
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 |
|||
Self inverting: |
|||
0 -1 -1 -2 -3 -5 -8 -13 -21 -34 -55 -89 -144 -233 -377 -610 -987 -1597 -2584 -4181 |
|||
Re inverted: |
|||
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 |
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 |
||
Line 543: | Line 563: | ||
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926 |
1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926 |
||
Round trip: |
Round trip: |
||
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 |
|||
Self inverting: |
|||
1 1 1 0 -3 -10 -24 -49 -89 -145 -208 -245 -174 176 1121 3185 7137 13920 24301 37926 |
|||
Re inverted: |
|||
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37</pre> |
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37</pre> |
||