(50g) Numeric List Commands

[John Keith]

The following are RPL implementations of some commands from the Wolfram Language (aka Mathematica) that I find useful. Both programs require the ListExt Library.

The first command generates a list of integers based on the linear recurrence of the integer sequence. It is similar to the Wolfram Language command LinearRecurrence except that the order of the lists is reversed.

Level 3 should contain a list of the initial terms of the sequence.
Level 2 should contain a list of coefficients.
Level 1 should contain an integer representing the number of terms to be generated.

The list on level 2 cannot be longer than the list on level 3.

Code:


\<< I\->R SWAP REV DUP SIZE \-> n c s
  \<< OBJ\-> 1. + n
    START s DUPN s \->LIST c * LSUM
    NEXT n \->LIST
  \>>
\>>

For example, if level 3 contains the list { 0 1 }, level 2 contains the list { 1 1 }, and level 1 the number 10, the program will return the first 10 Fibonacci numbers.

While not as fast as an efficient program for computing e.g. Fibonacci numbers, this program makes it easy to explore a wide variety of integer sequences. Many examples can be found here.


The next program performs convolution of lists. It is similar to the Wolfram Language command ListConvolve but again the order of the lists is reversed. The input list should be on level 2, and the kernel on level one. Convolution in this sense is related to the dot product of vectors except that the two lists do not have to be the same length.

Code:


\<< REV DUP SIZE \-> s
  \<< SWAP s
    \<< s \->LIST
    \>> DOSUBS DUP SIZE UNROT LXIL SWAP ROT LMRPT * s LSDIV
    \<< \GSLIST
    \>> DOLIST LXIL
  \>>
\>>

[John Keith]

Here is another list convolution program. It takes two lists (which must be the same length) and returns a list of convolutions of increasing subsets of the input lists.

The program will run on the HP48G if UNROT is replaced with ROT ROT.

The 0 + in the program is necessary because \GSLIST will error with a list size of 1.

Code:


\<< DUP SIZE \-> n
  \<< 1. n
    FOR k OVER 1. k SUB OVER 1. k SUB REVLIST * 0 + \GSLIST UNROT
    NEXT DROP2 n  \->LIST
  \>>
\>>

An example from http://oeis.org/A000330:

Code:


Input:
{ 0 1 2 3 4 5 }
{ 1 3 5 7 9 11 }

Output:
{ 0 1 5 14 30 55 }

[John Keith]

Updating this thread to add a program for deconvolution. Given a list on level 2 that is the (suspected) result of the convolution of two lists, and a "test" list on level 1, the program will return the list which must be convolved with the level 1 list to produce the level 2 list.

Note that unlike convolution, deconvolution is sensitive to the order of the lists. If the stack order of the lists is reversed, the program will return nonsense results. Also, the lengths of the two lists must be the same.

As an example, in level 2, { 1 6 20 50 105 196 336 } which are the 4-dimensional pyramidal numbers and on level 1,
{ 1 3 5 7 9 11 13 } - the odd numbers. The program returns { 1 3 6 10 15 21 28 } - the triangular numbers.

Code:


\<< OVER HEAD OVER HEAD / 1. \->LIST UNROT 2. OVER SIZE
  FOR k PICK3 OVER 2. k SUB REVLIST * 0 + \GSLIST PICK3 k GET PICK3 HEAD * SWAP - 4. ROLL SWAP + UNROT
  NEXT DROP2
\>>

For HP-48G compatibility, replace UNROT with ROT ROT and replace PICK3 with 3 PICK.

[John Keith]

Updating again with two more related programs.

First, the convolution inverse. This is the sequence which, when convolved with the input sequence, produces { 1 0 0 0 ... }, the identity sequence of convolution. The program assumes that you have the program from post #3 above, named DECONV, on your calculator.

Code:


\<< 1 0 PICK3 SIZE 1. - NDUPN \->LIST + SWAP DECONV
\>>

Next, the convolution square root. The "convolution square" as defined in the OEIS is the convolution of a sequence with itself. The "convolution square root" is the sequence which must be convolved with itself to produce the input sequence.

For example, the triangular numbers { 1 3 6 10 15 21 ... } convolved with themselves (using e.g. the program from post #2 above) returns { 1 6 21 56 126 252 ... }. The convolution square root of this sequence is as expected the triangular numbers.

Note that if the input list to this program is not a convolution square, the terms in the output list will not be integers. For instance, the convolution square root of the triangular numbers is { 1 '3/2' '15/8' '35/16' '315/128' '693/256' ... }.

Code:


\<< DUP HEAD \v/ OVER 2. GET OVER 2 * / 2. \->LIST 2. PICK3 SIZE 1. -
  FOR k DUP HEAD 2 * OVER TAIL DUP REVLIST * 0 + \GSLIST 4. PICK k 1. + GET SWAP - SWAP / EVAL +
  NEXT NIP
\>>

This program will run on the HP-48G if PICK3 is replaced with 3 PICK and NIP is replaced with SWAP DROP. The EVAL in the third line can also be removed.