(48G/50g) Binomial Transform, Difference Table

[John Keith]

Difference tables and the binomial transform are powerful methods for analyzing integer sequences and their underlying logic. See also Conway and Guy, "The Book of Numbers", chapter 3.

Difference tables can be easily created using the \GDLIST (Delta-LIST) command on many HP calculators. Given a list of integers on level 1, the following program returns a difference table as a list of lists:

Code:


\<< DUP DUP SIZE \-> n
  \<< 2. n
    START \GDLIST DUP
    NEXT DROP n \->LIST
  \>>
\>>

A simple modification of the program above will return the inverse binomial transform of the list on level 1:

Code:


\<< DUP SIZE \-> n
  \<< 2. n
    START DUP HEAD NEWOB SWAP \GDLIST
    NEXT EVAL n \->LIST
  \>>
\>>

Modifying the above program by inserting NEG after \GDLIST will produce the variation described by Thomas Klemm in this post.


And finally another modification returns the binomial transform, the inverse of the function of the program above:

Code:


\<< DUP HEAD SWAP DUP SIZE \-> n
  \<< 2. n
    START 2.
      \<< +
      \>> DOSUBS DUP HEAD NEWOB SWAP
    NEXT DROP n \->LIST
  \>>
\>>

Unlike \GDLIST, the two programs above do not shorten the list. If a list of integers is transformed by one program followed by the other, the original list will return unchanged.



...And one more useful variation, called "inverse summation" in this paper.

Code:


\<< DUP HEAD NEWOB SWAP \GDLIST +
\>>

This is the exact inverse of the cumulative or partial sum, and does not shorten the list.

Edited 9/20/2019 to add NEWOB to binomial transform, inverse binomial transform, and inverse summation programs. This simple addition allows the programs to process much larger lists and makes the programs run somewhat faster.