Binomial transform: Difference between revisions
Line 366: | Line 366: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
<syntaxhighlight lang="julia">""" https://rosettacode.org/wiki/Binomial_transform """ |
<syntaxhighlight lang="julia">""" https://rosettacode.org/wiki/Binomial_transform """ |
||
The binomial function is a built-in function in Julia. |
|||
""" forward binomial transform """ |
""" forward binomial transform """ |
Revision as of 20:57, 6 May 2023
The binomial transform is a bijective sequence transform based on convolution with binomial coefficients.
It may be thought of as an nth forward difference with odd differences carrying a negative sign.
There are two common variants of binomial transforms, one of which is self-inverting; reapplying the transform to a transformed sequence returns the original sequence, and one which has separate "forward" and "inverse" transform operations.
The two variants only differ in placement and quantity of signs. The variant standardized on by OEIS, with the 'forward' and 'inverse' complementary operations, will be used here.
In this variant, to transform the sequence a to sequence b and back:
the forward binomial transform is defined as:
and the inverse binomial transform is defined as:
where is the binomial operator 'n choose k'
For reference, the self inverting binomial transform is defined as:
- Task
- Implement both a forward, and inverse binomial transform routine.
- Use those routines to compute the forward binomial transform, the inverse binomial transform, and the inverse of the forward transform (should return original sequence) of a few representative sequences.
- Show at least the first 15 values in each sequence.
- You may generate the sequences, or may choose to just hard code the values.
- Use the following sequences for testing:
- Catalan numbers:
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440
- Prime flip flop sequence: (for an: 1 if prime, 0 otherwise):
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0
- Fibonacci sequence:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
- Padovan sequence: (starting with values 1,0,0):
1 0 0 1 0 1 1 1 2 2 3 4 5 7 9
- Catalan numbers:
- See also
- first sequence
- second sequence
- third sequence
- fourth sequence
C
#include <stdio.h>
#include <stdint.h>
uint64_t factorial(int n) {
if (n > 20) return 0; // too big for uint64_t
if (n < 2) return 1;
uint64_t fact = 1;
int i = 2;
for (i = 2; i <= n; ++i) fact *= i;
return fact;
}
uint64_t binomial(int n, int k) {
return factorial(n) / factorial(n-k) / factorial(k);
}
void btForward(int64_t b[], const int64_t a[], size_t c) {
int n, k;
for (n = 0; n < c; ++n) {
b[n] = 0;
for (k = 0; k <= n; ++k) {
b[n] += (int64_t)binomial(n, k) * a[k];
}
}
}
void btInverse(int64_t a[], const int64_t b[], size_t c) {
int n, k, sign;
for (n = 0; n < c; ++n) {
a[n] = 0;
for (k = 0; k <= n; ++k) {
sign = (n-k) & 1 ? -1 : 1;
a[n] += (int64_t)binomial(n, k) * b[k] * sign;
}
}
}
void btSelfInverting(int64_t b[], const int64_t a[], size_t c) {
int n, k, sign;
for (n = 0; n < c; ++n) {
b[n] = 0;
for (k = 0; k <= n; ++k) {
sign = k & 1 ? -1 : 1;
b[n] += (int64_t)binomial(n, k) * a[k] * sign;
}
}
}
int main() {
int i, j;
int64_t fwd[20], res[20], seqs[4][20] = {
{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190},
{0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181},
{1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37}
};
const char *names[4] = {
"Catalan number sequence:",
"Prime flip-flop sequence:",
"Fibonacci number sequence:",
"Padovan number sequence:"
};
for (i = 0; i < 4; ++i) {
printf("%s\n", names[i]);
for (j = 0; j < 20; ++j) printf("%ld ", seqs[i][j]);
printf("\nForward binomial transform:\n");
btForward(fwd, seqs[i], 20);
for (j = 0; j < 20; ++j) printf("%ld ", fwd[j]);
printf("\nInverse binomial transform:\n");
btInverse(res, seqs[i], 20);
for (j = 0; j < 20; ++j) printf("%ld ", res[j]);
printf("\nRound trip:\n");
btInverse(res, fwd, 20);
for (j = 0; j < 20; ++j) printf("%ld ", res[j]);
printf("\nSelf-inverting:\n");
btSelfInverting(fwd, seqs[i], 20);
for (j = 0; j < 20; ++j) printf("%ld ", fwd[j]);
printf("\nRe-inverted:\n");
btSelfInverting(res, fwd, 20);
for (j = 0; j < 20; ++j) printf("%ld ", res[j]);
if (i < 3) printf("\n\n"); else printf("\n");
}
return 0;
}
- Output:
Catalan number sequence: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 Forward binomial transform: 1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965 Inverse binomial transform: 1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 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 Prime flip-flop sequence: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Forward binomial transform: 0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952 Inverse binomial transform: 0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914 Round trip: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Self-inverting: 0 -1 -1 0 3 10 25 56 118 237 456 847 1540 2795 5173 9918 19761 40528 84235 174914 Re-inverted: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Fibonacci number sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 Forward binomial transform: 0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 Inverse binomial transform: 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181 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 Padovan number sequence: 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 Forward binomial transform: 1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192 Inverse binomial transform: 1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926 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
Go
package main
import "fmt"
func factorial(n int) uint64 {
if n > 20 {
return 0 // too big for uint64
}
if n < 2 {
return 1
}
fact := uint64(1)
i := 2
for i <= n {
fact *= uint64(i)
i++
}
return fact
}
func binomial(n, k int) uint64 {
return factorial(n) / factorial(n-k) / factorial(k)
}
func btForward(a []int64) []int64 {
c := len(a)
b := make([]int64, c)
for n := 0; n < c; n++ {
b[n] = int64(0)
for k := 0; k <= n; k++ {
b[n] += int64(binomial(n, k)) * a[k]
}
}
return b
}
func btInverse(b []int64) []int64 {
c := len(b)
a := make([]int64, c)
for n := 0; n < c; n++ {
a[n] = int64(0)
for k := 0; k <= n; k++ {
sign := int64(-1)
if (n-k)&1 == 0 {
sign = 1
}
a[n] += int64(binomial(n, k)) * b[k] * sign
}
}
return a
}
func btSelfInverting(a []int64) []int64 {
c := len(a)
b := make([]int64, c)
for n := 0; n < c; n++ {
b[n] = int64(0)
for k := 0; k <= n; k++ {
sign := int64(-1)
if k&1 == 0 {
sign = 1
}
b[n] += int64(binomial(n, k)) * a[k] * sign
}
}
return b
}
func main() {
seqs := [][]int64{
{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190},
{0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0},
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181},
{1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37},
}
names := []string{
"Catalan number sequence:",
"Prime flip-flop sequence:",
"Fibonacci number sequence:",
"Padovan number sequence:",
}
for i, seq := range seqs {
fmt.Println(names[i])
fmt.Println(seq)
fmt.Println("Forward binomial transform:")
fwd := btForward(seq)
fmt.Println(fwd)
fmt.Println("Inverse binomial transform:")
fmt.Println(btInverse(seq))
fmt.Println("Round trip:")
fmt.Println(btInverse(fwd))
fmt.Println("Self-inverting:")
si := btSelfInverting(seq)
fmt.Println(si)
fmt.Println("Re-inverted:")
fmt.Println(btSelfInverting(si))
if i < len(seqs)-1 {
fmt.Println()
}
}
}
- Output:
Catalan number sequence: [1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190] Forward binomial transform: [1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965] Inverse binomial transform: [1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595] 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] Prime flip-flop sequence: [0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0] Forward binomial transform: [0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952] Inverse binomial transform: [0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914] Round trip: [0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0] Self-inverting: [0 -1 -1 0 3 10 25 56 118 237 456 847 1540 2795 5173 9918 19761 40528 84235 174914] Re-inverted: [0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0] Fibonacci number sequence: [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181] Forward binomial transform: [0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169] Inverse binomial transform: [0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181] 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] Padovan number sequence: [1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37] Forward binomial transform: [1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192] Inverse binomial transform: [1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926] 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]
Julia
""" https://rosettacode.org/wiki/Binomial_transform """
The binomial function is a built-in function in Julia.
""" forward binomial transform """
binomial_transform(seq) =
[sum(binomial(n, k) * seq[k+1] for k in 0:n) for n in 0:length(seq)-1]
""" inverse binomial transform """
function inverse_binomial_transform(seq)
return [sum((-1)^(n - k) * binomial(n, k) * seq[k+1] for k in 0:n) for n in 0:length(seq)-1]
end
const test_sequences = [
"Catalan number sequence" => [
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440,
9694845,
35357670,
129644790,
477638700,
1767263190,
],
"Prime flip-flop sequence" =>
[0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0],
"Fibonacci number sequence" => [
0,
1,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
],
"Padovan number sequence" =>
[1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37],
]
for (s, a) in test_sequences
println("\n$s:\n", join(a, " "))
println("Forward binomial transform:\n", join(binomial_transform(a), " "))
println("Inverse binomial transform:\n", join(inverse_binomial_transform(a), " "))
println("Re-inverted:\n", join(inverse_binomial_transform(binomial_transform(a)), " "))
end
- Output:
Same as C, Go, etc.
Python
from math import factorial
from math import pow
from typing import Iterable
from typing import Sequence
def binomial(n: int, k: int) -> int:
return factorial(n) // (factorial(n - k) * factorial(k))
def binomial_transform(seq: Sequence) -> Iterable[int]:
for n in range(len(seq)):
yield sum(binomial(n, k) * seq[k] for k in range(n + 1))
def inverse_binomial_transform(seq: Sequence) -> Iterable[int]:
for n in range(len(seq)):
yield int(sum(pow(-1, n - k) * binomial(n, k) * seq[k] for k in range(n + 1)))
test_sequences = {
"Catalan number sequence": [
1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440,
9694845,
35357670,
129644790,
477638700,
1767263190,
],
"Prime flip-flop sequence": [
0,
1,
1,
0,
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
0,
0,
1,
0,
1,
0,
],
"Fibonacci number sequence": [
0,
1,
1,
2,
3,
5,
8,
13,
21,
34,
55,
89,
144,
233,
377,
610,
987,
1597,
2584,
4181,
],
"Padovan number sequence": [
1,
0,
0,
1,
0,
1,
1,
1,
2,
2,
3,
4,
5,
7,
9,
12,
16,
21,
28,
37,
],
}
if __name__ == "__main__":
import pprint
for desc, seq in test_sequences.items():
print(desc + ":")
pprint.pprint(seq, compact=True, indent=2)
print("Forward binomial transform:")
pprint.pprint(list(binomial_transform(seq)), compact=True, indent=2)
print("Inverse binomial transform:")
pprint.pprint(list(inverse_binomial_transform(seq)), compact=True, indent=2)
print("Round trip:")
pprint.pprint(
list(inverse_binomial_transform(list(binomial_transform(seq)))),
compact=True,
indent=2,
)
print()
- Output:
Catalan number sequence: [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190] Forward binomial transform: [ 1, 2, 5, 15, 51, 188, 731, 2950, 12235, 51822, 223191, 974427, 4302645, 19181100, 86211885, 390248055, 1777495635, 8140539950, 37463689775, 173164232965] Inverse binomial transform: [ 1, 0, 1, 1, 3, 6, 15, 36, 91, 232, 603, 1585, 4213, 11298, 30537, 83097, 227475, 625992, 1730787, 4805595] Round trip: [ 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190] Prime flip-flop sequence: [0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0] Forward binomial transform: [ 0, 1, 3, 6, 11, 20, 37, 70, 134, 255, 476, 869, 1564, 2821, 5201, 9948, 19793, 40562, 84271, 174952] Inverse binomial transform: [ 0, 1, -1, 0, 3, -10, 25, -56, 118, -237, 456, -847, 1540, -2795, 5173, -9918, 19761, -40528, 84235, -174914] Round trip: [0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0] Fibonacci number sequence: [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] Forward binomial transform: [ 0, 1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765, 17711, 46368, 121393, 317811, 832040, 2178309, 5702887, 14930352, 39088169] Inverse binomial transform: [ 0, 1, -1, 2, -3, 5, -8, 13, -21, 34, -55, 89, -144, 233, -377, 610, -987, 1597, -2584, 4181] Round trip: [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] Padovan number sequence: [1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37] Forward binomial transform: [ 1, 1, 1, 2, 5, 12, 28, 65, 151, 351, 816, 1897, 4410, 10252, 23833, 55405, 128801, 299426, 696081, 1618192] Inverse binomial transform: [ 1, -1, 1, 0, -3, 10, -24, 49, -89, 145, -208, 245, -174, -176, 1121, -3185, 7137, -13920, 24301, -37926] Round trip: [1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37]
Raku
Generates the sequences on the fly.
sub binomial { [×] ($^n … 0) Z/ 1 .. $^p }
sub binomial-transform (*@seq) {
@seq.keys.map: -> \n { sum (0..n).map: -> \k { binomial(n,k) × @seq[k] } }
}
sub inverse-binomial-transform (*@seq) {
@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;
for 'Catalan number', (1, {[+] @_ Z× @_.reverse}…*),
'Prime flip-flop', (1..*).map({.is-prime ?? 1 !! 0}),
'Fibonacci number', (0,1,*+*…*),
'Padovan number', (1,0,0, -> $c,$b,$ {$b+$c}…*)
-> $name, @seq {
say qq:to/BIN/;
$name sequence:
{@seq[^$upto]}
Forward binomial transform:
{binomial-transform(@seq)[^$upto]}
Inverse binomial transform:
{inverse-binomial-transform(@seq)[^$upto]}
Round trip:
{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
}
- Output:
Catalan number sequence: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 Forward binomial transform: 1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965 Inverse binomial transform: 1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 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 Prime flip-flop sequence: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Forward binomial transform: 0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952 Inverse binomial transform: 0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914 Round trip: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Self inverting: 0 -1 -1 0 3 10 25 56 118 237 456 847 1540 2795 5173 9918 19761 40528 84235 174914 Re inverted: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Fibonacci number sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 Forward binomial transform: 0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 Inverse binomial transform: 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181 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 Padovan number sequence: 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 Forward binomial transform: 1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192 Inverse binomial transform: 1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926 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
Wren
This hard-codes the sequences to be tested as I couldn't see much point in repeating code from the related tasks.
import "./long" for Long, ULong
class BT {
static forward(a) {
var c = a.count
var b = List.filled(c, null)
for (n in 0...c) {
b[n] = Long.zero
for (k in 0..n) b[n] = b[n] + ULong.binomial(n, k).toLong * a[k]
}
return b
}
static inverse(b) {
var c = b.count
var a = List.filled(c, null)
for (n in 0...c) {
a[n] = Long.zero
for (k in 0..n) {
var sign = ((n - k) % 2 == 0) ? 1 : -1
a[n] = a[n] + ULong.binomial(n, k).toLong * b[k] * sign
}
}
return a
}
static selfInverting(a) {
var c = a.count
var b = List.filled(c, null)
for (n in 0...c) {
b[n] = Long.zero
for (k in 0..n) {
var sign = k % 2 == 0 ? 1 : -1
b[n] = b[n] + ULong.binomial(n, k).toLong * a[k] * sign
}
}
return b
}
}
var seqs = [
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190],
[0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0],
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181],
[1, 0, 0, 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37]
]
var names = [
"Catalan number sequence:",
"Prime flip-flop sequence:",
"Fibonacci number sequence:",
"Padovan number sequence:"
]
var saved
for (i in 0...seqs.count) {
System.print(names[i])
System.print(seqs[i].join(" "))
System.print("Forward binomial transform:")
System.print((saved = BT.forward(seqs[i])).join(" "))
System.print("Inverse binomial transform:")
System.print(BT.inverse(seqs[i]).join(" "))
System.print("Round trip:")
System.print(BT.inverse(saved).join(" "))
System.print("Self-inverting:")
System.print((saved = BT.selfInverting(seqs[i])).join(" "))
System.print("Re-inverted:")
System.print(BT.selfInverting(saved).join(" "))
if (i < seqs.count - 1) System.print()
}
- Output:
Catalan number sequence: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 Forward binomial transform: 1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965 Inverse binomial transform: 1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 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 Prime flip-flop sequence: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Forward binomial transform: 0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952 Inverse binomial transform: 0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914 Round trip: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Self-inverting: 0 -1 -1 0 3 10 25 56 118 237 456 847 1540 2795 5173 9918 19761 40528 84235 174914 Re-inverted: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Fibonacci number sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 Forward binomial transform: 0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 Inverse binomial transform: 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181 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 Padovan number sequence: 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 Forward binomial transform: 1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192 Inverse binomial transform: 1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926 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
XPL0
func real Factorial(N);
int N, I;
real F;
[F:= 1.;
for I:= 2 to N do F:= F * float(I);
return F;
];
func real Binomial(N, K);
int N, K;
return Factorial(N) / Factorial(N-K) / Factorial(K);
proc BinomialFwd(A, B, M);
real A, B; int M;
int N, K;
[for N:= 0 to M-1 do
[B(N):= 0.;
for K:= 0 to N do
B(N):= B(N) + Binomial(N, K) * A(K);
];
];
proc BinomialInv(A, B, M);
real A, B; int M;
int N, K, Sign;
[for N:= 0 to M-1 do
[A(N):= 0.;
for K:= 0 to N do
[Sign:= if N-K & 1 then -1 else 1;
A(N):= A(N) + float(Sign) * Binomial(N, K) * B(K);
];
];
];
real Fwd(20), Inv(20), Seqs;
int Title, I, J;
[Seqs:= [
[1., 1., 2., 5., 14., 42., 132., 429., 1430., 4862., 16796., 58786., 208012.,
742900., 2674440., 9694845., 35357670., 129644790., 477638700., 1767263190.],
[0., 1., 1., 0., 1., 0., 1., 0., 0., 0., 1., 0., 1., 0., 0., 0., 1., 0., 1., 0.],
[0., 1., 1., 2., 3., 5., 8., 13., 21., 34., 55., 89., 144., 233., 377., 610.,
987., 1597., 2584., 4181.],
[1., 0., 0., 1., 0., 1., 1., 1., 2., 2., 3., 4., 5., 7., 9., 12., 16., 21., 28., 37.]];
Title:= [
"Catalan number sequence:",
"Prime flip-flop sequence:",
"Fibonacci number sequence:",
"Padovan number sequence:" ];
Format(1,0);
for I:= 0 to 4-1 do
[Text(0, Title(I)); CrLf(0);
for J:= 0 to 20-1 do [RlOut(0, Seqs(I,J)); ChOut(0, ^ )];
Text(0, "^m^jForward binomial transform:^m^j");
BinomialFwd(Seqs(I), Fwd, 20);
for J:= 0 to 20-1 do [RlOut(0, Fwd(J)); ChOut(0, ^ )];
Text(0, "^m^jInverse binomial transform:^m^j");
BinomialInv(Inv, Seqs(I), 20);
for J:= 0 to 20-1 do [RlOut(0, Inv(J)); ChOut(0, ^ )];
Text(0, "^m^jRound trip:^m^j");
BinomialInv(Inv, Fwd, 20);
for J:= 0 to 20-1 do [RlOut(0, Inv(J)); ChOut(0, ^ )];
if I < 3 then CrLf(0);
CrLf(0);
];
]
- Output:
Catalan number sequence: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 Forward binomial transform: 1 2 5 15 51 188 731 2950 12235 51822 223191 974427 4302645 19181100 86211885 390248055 1777495635 8140539950 37463689775 173164232965 Inverse binomial transform: 1 0 1 1 3 6 15 36 91 232 603 1585 4213 11298 30537 83097 227475 625992 1730787 4805595 Round trip: 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670 129644790 477638700 1767263190 Prime flip-flop sequence: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Forward binomial transform: 0 1 3 6 11 20 37 70 134 255 476 869 1564 2821 5201 9948 19793 40562 84271 174952 Inverse binomial transform: 0 1 -1 0 3 -10 25 -56 118 -237 456 -847 1540 -2795 5173 -9918 19761 -40528 84235 -174914 Round trip: 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 Fibonacci number sequence: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 Forward binomial transform: 0 1 3 8 21 55 144 377 987 2584 6765 17711 46368 121393 317811 832040 2178309 5702887 14930352 39088169 Inverse binomial transform: 0 1 -1 2 -3 5 -8 13 -21 34 -55 89 -144 233 -377 610 -987 1597 -2584 4181 Round trip: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 Padovan number sequence: 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 Forward binomial transform: 1 1 1 2 5 12 28 65 151 351 816 1897 4410 10252 23833 55405 128801 299426 696081 1618192 Inverse binomial transform: 1 -1 1 0 -3 10 -24 49 -89 145 -208 245 -174 -176 1121 -3185 7137 -13920 24301 -37926 Round trip: 1 0 0 1 0 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37