(50g) Euler Transform
03-12-2019, 10:17 PM (This post was last modified: 08-07-2019 11:27 AM by John Keith.)
Post: #1
 John Keith Senior Member Posts: 493 Joined: Dec 2013
(50g) Euler Transform
Following are programs for computing the Euler transform and its inverse for sequences of integers. Both require the ListExt Library. The inverse transform also requires Gerald Hillier's MOB program which computes the Moebius Mu function.

Euler transform:

Code:

\<< DUP SIZE R\->I \-> n
\<< DUP HEAD SWAP 2 n
FOR k k DIVIS DUP2 LPICK * LSUM SWAP
NEXT DROP n \->LIST DUP 1. 1. SUB 2 n
FOR j OVER 1 j 1 - SUB OVER REV * LSUM PICK3 j GET + j / +
NEXT NIP
\>>
\>>

Inverse Euler transform:

Code:

\<< DUP SIZE R\->I \-> n
\<< DUP 1. 1. SUB 2 n
FOR j OVER 1 j 1 - SUB OVER REV * LSUM PICK3 j GET j * SWAP - +
NEXT NIP 1 n
FOR k k DIVIS DUP2 LPICK SWAP REV MOB * LSUM k / SWAP
NEXT DROP n \->LIST
\>>
\>>
03-14-2019, 07:49 PM
Post: #2
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: (50g) Euler Transform
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
03-16-2019, 09:12 PM
Post: #3
 John Keith Senior Member Posts: 493 Joined: Dec 2013
RE: (50g) Euler Transform
Thanks for another enlightening post, Thomas.

Your program T is similar to the second program in my post here.

The difference is, of course the negation that happens after the ΔLIST. Your other programs ΣL and ΔL do not return the same results without the negation.

My programs are those described in the last paragraph of the "Definitions" section of the Wikipedia page you linked to, which are not self-inverse.

I have linked my binomial transform thread to this one as it seems your version would be of interest to anyone reading that thread.
08-07-2019, 11:32 AM
Post: #4
 John Keith Senior Member Posts: 493 Joined: Dec 2013
RE: (50g) Euler Transform
I just updated post #1 to fix an erroneous program listing for the inverse transform and to replace both programs with shorter, faster versions. Please delete previous versions if you have them.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)