Best calculator for recurrence relations

[carey]

I have begun using recurrence relations (mainly three-term) and am wondering if anyone finds a particular calculator model's sequence/recursive mode to be more powerful than others? While not difficult to write programs to work with expressions like A(n) = A(n-1) + A(n-2), the convenience of a built-in feature is nice. I'm curious if anyone knows of any calculator model with a sequence/recursive mode that handles simultaneous recurrence relations or more than three terms? Thanks!

[Gerald H]

HP 38G does this very well - indeed, range of N catered for is greater than in the Prime.

[Dave Britten]

The TI-84 Plus CE will let you do A(n), A(n+1), or A(n+2), and also lets you set the starting value of n (default is 1). Not sure how other members of the 84 family compare, but they're likely similar.

[John Keith]

(02-18-2020 05:21 AM)Gerald H Wrote:  HP 38G does this very well - indeed, range of N catered for is greater than in the Prime.

The Sequence app in the Prime has a very nice interface, too bad it is limited to 12-digit approximate numbers. If it could be updated to use exact integers, it would be truly useful.

[Gerald H]

Prime will only accept N up to 32767, thereafter declares NaN.

[David Hayden]

The 50g (and other RPLs?) have the SEQ command.

[Dave Britten]

(02-18-2020 09:30 PM)David Hayden Wrote:  The 50g (and other RPLs?) have the SEQ command.

Does that do recursive sequences? I thought it just generates a list of values at regular intervals by evaluating an expression. e.g. can you use it to generate the Fibonacci sequence?

[John Keith]

(02-18-2020 09:30 PM)David Hayden Wrote:  The 50g (and other RPLs?) have the SEQ command.

The SEQ command (HP48g and later) is just a "user friendly" FOR..STEP loop, and cannot do recursive sequences. Recursive sequences can only be done by programming, which can be difficult for complex sequences such as Hofstadter Q-sequences.

[Gerald H]

The programme below will return the Nth Fibonacci number for natural number N input:

Code:

« 0 1
  « SWAP OVER +
  » 'X' 1 6 ROLL 1 SEQ DROP
»

[John Keith]

Neat, but can you do this with SEQ?

[Csaba Tizedes]

(02-23-2020 07:09 PM)John Keith Wrote:  Neat, but can you do this with SEQ?

a(1)=a(2)=1; for n>2, a(n)=a(a(n-2))+a(n-a(n-2))
1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 9, 10, 10, 11, 12, 12, 13, 14, 15, 16, 16, 17, 17, 18, 19, 19, ...

I don't know how it is works on HPs, but on TI-83 you can do something like this:

first decide the max. index of your list: N
then generate the list, let's say Z: seq(1,X,1,N,1)->LZ
finally generate the sequence: augment({1,1},seq(LZ(LZ(X-2))+LZ(X-LZ(X-2)),X,3,N,1))->LZ
and press ENTER until the result list is not change.

Just an idea, must to check, but I'm sure it is works.

There are models where sequences are implemented, maybe you can do it on those models (HP38/39 models, some CASIO models), but I am not sure the result is a list, maybe a table in an application.

Csaba

[Dave Britten]

(02-25-2020 03:08 PM)Csaba Tizedes Wrote:  I don't know how it is works on HPs, but on TI-83 you can do something like this:

first decide the max. index of your list: N
then generate the list, let's say Z: seq(1,X,1,N,1)->LZ
finally generate the sequence: augment({1,1},seq(LZ(LZ(X-2))+LZ(X-LZ(X-2)),X,3,N,1))->LZ
and press ENTER until the result list is not change.

Just an idea, must to check, but I'm sure it is works.

Should work, though it'll be fairly slow for large lists, since you'll have to run it about as many times as you have list elements.

Here's a little 84 Plus CE program that prompts for all the inputs. This uses toString() to show the subscript when prompting for constants; this would have to be changed for an 83 (probably Disp X followed by an Input). Also, some of the prompt messages would need to be wrapped to fit the monochrome LCD models.

Code:

Input "NUMBER OF CONSTANTS? ",C
C→dim(L₁)
For(X,1,C
"L₁("+toString(X)+")="→Str1
Input Str1,V
V→L₁(X)
End
Disp "EXPRESSION?"
Disp "USE L₁(N-X) TO REFER"
Disp "TO PRIOR TERMS."
Disp "N=CURRENT TERM SUBSCRIPT
Input Str1
StringEqu(Str1,Y₁)
Input "MAX N? ",M
For(N,C+1,M
Y₁→L₁(N)
End
L₁

The terms are calculated one at a time in increasing subscript order, and the list dimension increases by one with each term appended. Forward references will fail with a dimension error, i.e. you can only refer to prior (already calculated) list elements.

You can rcl Y1 at the expression entry prompt if you want to run the program again with the same recursive formula, but different constants or max N.

I tested it with the example - L1(1)=L1(2)=1, L1(N)=L1(L1(N-2))+L1(N-L1(N-2)) - and got the same first 20 terms.

[DavidM]

(02-23-2020 07:09 PM)John Keith Wrote:  Neat, but can you do this with SEQ?

Well, it won't win any awards for speed, but the subscripting allowed in symbolic expressions on the 50g does allow a fairly straightforward way to do this. It's not recursive, of course, but this does seem to work for the samples I've tested:

Code:

\<<
   1 R\->I 2. NDUPN \->LIST                  @ build initial result
   \-> max a                                 @ local variables
   \<<
      0.                                     @ placeholder for result
      \<<
         a                                   @ recall current list
         'a(a(n-2))+a(n-a(n-2))' EVAL R\->I  @ obtain next element
         +                                   @ add new element to result
         DUP 'a' STO                         @ update result list
         NIP                                 @ delete previous result
      \>>
      'n' 3. max 1. SEQ                      @ execute SEQuence
   \>>
\>>

Notes:
1) There's no error checking of the input argument (the maximum "n", which must be >2)
2) SEQ wants to build a final list from the results of each iteration of the executable, but in this case the result is simply appended to the existing array for future computations. There's nothing new on the stack for SEQ to encapsulate when it completes, and the stack-based result is not included since it was created before SEQ executes.

It's not particularly elegant, but it works. This could probably be sped up by doing the computations on the stack instead of with a symbolic expression, but the readability would take a significant hit (IMHO).

[John Keith]

(02-25-2020 07:15 PM)DavidM Wrote:  This could probably be sped up by doing the computations on the stack instead of with a symbolic expression, but the readability would take a significant hit (IMHO).

This is indeed the case. You end up with lots of PICKs and GETs and the programs are as hard to write as they are to read. They are also a lot faster.

For example, here is a program for a similar sequence:

Code:


%%HP: T(3)A(R)F(.);
@ Returns A070867, a highly chaotic sequence, which is sequence 'F' from S. Wolfram,
@ 'A New Kind of Science', p.129.
@ Expression: A(0) = A(1) = 1; A(n) = A(n-A(n-1)-1) + A(n-A(n-2)-1)
\<< \-> s
  \<< 1 1 3 s
    FOR n OVER n SWAP - n SWAP - 1 + PICK OVER n SWAP - n SWAP - 2 + PICK +
    NEXT s \->LIST
  \>>
\>>

[DavidM]

This program seemed like a good example of where pre-compiling the executable passed to SEQ would help, so I decided to try a version that did that:

Code:

\<<
   1 R\->I 2. NDUPN \->LIST                  @ build initial result
   0. DUP                                    @ placeholders for locals
   \-> max a n exe                           @ assign local variables
   \<<
      'a(a(n-2))+a(n-a(n-2))' \->PRG         @ pre-compile executable
      'exe' STO                              @ ...and store it

      \<<                                    @ executable code for SEQ
         a                                   @ recall current list
         exe EVAL                            @ obtain next element
         +                                   @ add new element to result
         'a' STO                             @ update result list
      \>>
      'n' 3. max 1. SEQ                      @ execute SEQuence

      a                                      @ recall final result list
   \>>
\>>

"Precompiling" the symbolic expression is done with the →PRG command (on page 3 of the built-in Development Library menu [#256]). There's a subtlety here that needs to be noted: the variables in the symbolic will be compiled as either globals or locals depending on the context of where they are used in the program. That's why I went ahead and pre-allocated the locals in this version -- this ensures that the compiled program will correctly use locals as opposed to globals when it is executed by SEQ. This issue can be explicitly dealt with by using "precompiled locals", but I believe that syntax gets more messy than it's worth in situations like this.

Precompiling the executable makes this version about 59% faster on my 50g. There was also a redundant R→I in the original version which was removed. That impact was negligible, though.

[John Keith]

That is really cool! I never realized that you could do that with SEQ. While it is a lot slower than the stack-based version, your program allows one to type (or paste) in a formula directly and see the result. Additionally there is the advantage of exact integers so no restrictions like the Prime Sequence app.

I have learned a lot from you and Gerald here, as is often the case.