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

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (48G/50g) Binomial Transform, Difference Table (/thread-12217.html)

(48G/50g) Binomial Transform, Difference Table - John Keith - 01-17-2019 04:56 PM

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 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 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.

RE: (48G/50g) Binomial Transform, Difference Table - John Keith - 05-27-2019 04:07 PM

Following on from the last two posts, a much faster binomial transform program for sequences defined by simple polynomials. Sequences defined by an nth degree polynomial are binomial transforms of a sequence beginning with n+1 terms followed by an arbitrary number of zeros. For instance, A000292, the tetrahedral numbers, is the binomial transform of { 1 3 3 1 0 0 0... }.

The following program requires a list of the non-zero terms on level 2 and a number on level 1 which is the number of terms to return. For example, with { 1 3 3 1 } on level 2 and 12 on level 1, the program will return a list of the first 12 tetrahedral numbers.

Code:

\<< OVER SIZE 2. - \-> n s
  \<< EVAL n LASEQ 1. s
    START SWAP
      \<< +
      \>> Scanl
    NEXT
  \>>
\>>

This program is HP 50g only since it uses commands from the external libraries ListExt and GoferLists.

The following version is compatible with the HP-48G. It is longer and slower than the HP 50 version but still reasonably fast.

Code:

\<< OVER SIZE 2 - ROT OBJ\-> 2 + ROLL LASTARG ROLL \-> m n s
  \<< n m * OVER + 1 -
    FOR j j m
    STEP n \->LIST 1 s
    START 1
      \<< OVER +
      \>> DOLIST +
    NEXT
  \>>
\>>