(50g) Euler Transform

[Thomas Klemm]

Your link to the Binomial transform made me write this implementation of the binomial transform T:

Code:

\<< { } SWAP
  WHILE
    DUP SIZE 1 >
  REPEAT
    SWAP OVER HEAD +
    SWAP \GDLIST NEG
  END +
\>>

This can now be used to define a function ΣL to create the partial sum of a list:

Code:

\<< T 0 SWAP + NEG T \>>

And ΔL is just the transformation of TAIL negated:

Code:

\<< T TAIL NEG T \>>

Of course ΔL and the built-in ΔLIST are the same.
But since T is an involution we can see that « ΣL ΔL » is the identity:

Code:

\<< T 0 SWAP + NEG T T TAIL NEG T \>>

=

Code:

\<< T 0 SWAP + NEG TAIL NEG T \>>

=

Code:

\<< T NEG NEG T \>>

=

Code:

\<< T T \>>

=

Code:

\<< \>>

We notice that the binomial transform of a polynomial is 0 after a while.
E.g. in case of the cubes of the natural numbers we get:

[0 1 8 27 64 125 216 343 512 729]
T
[0 -1 6 -6 0 0 0 0 0 0]

So if we want to calculate the partial sum of this list we negate it and add 0 at its head:

[0 0 1 -6 6 0 0 0 0 0 0]
T
[0 0 1 9 36 100 225 441 784 1296 2025]


We might try to figure out the pattern of \(T(n^k)\) for \(k \in \mathbb{N}\):

[1 0 0 0 0 0 0 0 0 0]
[0 -1 0 0 0 0 0 0 0 0]
[0 -1 2 0 0 0 0 0 0 0]
[0 -1 6 -6 0 0 0 0 0 0]
[0 -1 14 -36 24 0 0 0 0 0]
[0 -1 30 -150 240 -120 0 0 0 0]
[0 -1 62 -540 1560 -1800 720 0 0 0]
[0 -1 126 -1806 8400 -16800 15120 -5040 0 0]
[0 -1 254 -5796 40824 -126000 191520 -141120 40320 0]
[0 -1 510 -18150 186480 -834120 1905120 -2328480 1451520 -362880]


Or then check the powers of 2:

[1 2 4 8 16 32 64 128 256 512]
T
[1 -1 1 -1 1 -1 1 -1 1 -1]


What about Fibonacci?

[0 1 1 2 3 5 8 13 21 34 55 89]
T
[0 -1 -1 -2 -3 -5 -8 -13 -21 -34 -55 -89]


What else can you come up with?

Cheers
Thomas