HP 25 Fibonacci sequence in one program step

[Dave Britten]

I've been reading "Mathematical Recreations for the Programmable Calculator", and they have a somewhat humorous puzzle regarding the shortest possible program to produce the Fibonacci sequence.

The HP 25 program they concocted is only a single step, plus the typical GTO 00 to halt and reset the program. This short program does require the user to preload the stack and/or memory prior to running, but then subsequent presses of R/S produce the Fibonacci sequence on the display.

I'm curious if anybody can figure out the silly trick that they used in this book.

[rprosperi]

I don't recall what the answer is, but I do recall that Joe Horn showed me this at the PPC clubhouse around 1982. At the time it was with a 41C of course, but I believe he had figured this out on his HP-25, thus solving the author's challenge.

I predict he will reply here with the answer....

[Paul Dale]

RCL+ Y ??


The 34S has the FIB command.



Pauli

[Joe Horn]

(10-13-2021 01:23 PM)rprosperi Wrote:  I don't recall what the answer is, but I do recall that Joe Horn showed me this at the PPC clubhouse around 1982. At the time it was with a 41C of course, but I believe he had figured this out on his HP-25, thus solving the author's challenge.

I predict he will reply here with the answer....

Yikes, really? No idea. I would have guessed that it would require 3 steps on a '25. I can't wait to see the solution!

EDIT: If the program is only required to succeed 3 times, then the program can be just ROLL DOWN, but that's silly.

[Dave Britten]

(10-13-2021 02:02 PM)Joe Horn Wrote:  Yikes, really? No idea. I would have guessed that it would require 3 steps on a '25. I can't wait to see the solution!

I'll warn you, it's both really stupid, and really clever. I'll post a short write-up later if nobody gets it before then.

The important detail is that it's fair for the program to require the user to set up any or all of the stack/memory/display mode/etc. prior to running the program. But program memory only needs one step plus a GTO 00.

[Valentin Albillo]

(10-13-2021 01:03 PM)Dave Britten Wrote:  I've been reading "Mathematical Recreations for the Programmable Calculator", and they have a somewhat humorous puzzle regarding the shortest possible program to produce the Fibonacci sequence.

The HP 25 program they concocted is only a single step, plus the typical GTO 00 to halt and reset the program. This short program does require the user to preload the stack and/or memory prior to running, but then subsequent presses of R/S produce the Fibonacci sequence on the display.

I'm curious if anybody can figure out the silly trick that they used in this book.

.
The one and only step is [x], multiplication.

Of course you must specify FIX 0 and load the stack in an appropriate way, but that's left as an exercise to the reader.

Regards.
V.

[Joe Horn]

(10-13-2021 02:19 PM)Dave Britten Wrote:  I'll warn you, it's both really stupid, and really clever. I'll post a short write-up later if nobody gets it before then.

The important detail is that it's fair for the program to require the user to set up any or all of the stack/memory/display mode/etc. prior to running the program. But program memory only needs one step plus a GTO 00.

Is it just × [multiply] with the stack loaded with something, like the golden ratio perhaps? Even in FIX 0 mode that doesn't get correct results....

Hmmm... maybe with the correct X it works... 0.45 works for a while...

OOPS! Valentin beat me to it! Still looking for the best starting X...

[Dave Britten]

Yup, you guys are on the right track there. The key to making it work is something called Binet's formula mentioned in the footnote (but which I've not yet read up on myself).

EDIT: Oh, I see, I've heard of it before, just didn't recognize it by name.

[C.Ret]

With all the information from each contributor given in this threat, I finally manage to have a Fibonacci Sequence after each [ x ] key pressed :

[attachment=9911]

(I cut the top of my printed trace to let other readers seeking for their own solution)
Nice trick, and really specific to RPN; will have hard time making a one key program with the infinite stack of RPL systems.

[Gerson W. Barbosa]

(10-13-2021 04:00 PM)C.Ret Wrote:  With all the information from each contributor given in this threat, I finally manage to have a Fibonacci Sequence after each [ x ] key pressed :



(I cut the top of my printed trace to let other readers seeking for their own solution)
Nice trick, and really specific to RPN; will have hard time making a one key program with the infinite stack of RPL systems.

RPN: Y, Z, T <- k1; X <-k2

Then * * * …

RPL: Fill the infinite stack with [ [ 1 1 ] [ 1 0 ] ]

Then * * * …

[Dave Britten]

I think you guys have figured out the gist of it.

The solution in the book is to set FIX 0, and fill the stack thusly:

T: phi
Z: phi
Y: phi
X: 1/SQRT(5)

Where phi is the golden ratio: (SQRT(5)+1)/2. The 1/SQRT(5) term is derived from Binet's formula.

Then your HP 25 program need only be:

01 *
02 GTO 00

But that that point, one scarcely needs a program at all.

The calculation gets more and more accurate with each successive term, but the FIX 0 rounding should give you a correct integer result for all terms.

[David Hayden]

I can do it on a 42s (well, free42 on my phone) with a different instruction (i.e., not multiply). Can you guess the instruction?

[Gerson W. Barbosa]

(10-13-2021 06:53 PM)David Hayden Wrote:  I can do it on a 42s (well, free42 on my phone) with a different instruction (i.e., not multiply). Can you guess the instruction?

0 1 +

Then repeat

RCL + ST L

[David Hayden]

(10-13-2021 07:11 PM)Gerson W. Barbosa Wrote:  0 1 +

Then repeat

RCL + ST L

That's it!

[Dave Britten]

(10-13-2021 07:35 PM)David Hayden Wrote:  

(10-13-2021 07:11 PM)Gerson W. Barbosa Wrote:  0 1 +

Then repeat

RCL + ST L

That's it!

Very clever! Does this work on any other models? I can't think of any.

[rprosperi]

Many other models support recall arithmetic (45, 27, 15C, 32S, 32SII, others?) but only the 42S includes recall arithmetic AND stack register access. With Angel's Total Recall module, a 41 can do this too.

[Didier Lachieze]

(10-13-2021 08:34 PM)rprosperi Wrote:  only the 42S includes recall arithmetic AND stack register access.

This works also on the WP-34S.

For RPL, with two keys:
0 ENTER
1 ENTER
Then repeat DUP2 +

And for the HP Prime (non-RPN entry mode), with one key:
0 ENTER
1 ENTER
Ans+Ans(2)
Then repeat ENTER

[Mike T.]

(10-13-2021 06:26 PM)Dave Britten Wrote:  But that that point, one scarcely needs a program at all.

You can even 'run' that on an HP21 !!

[rprosperi]

(10-13-2021 10:07 PM)Didier Lachieze Wrote:  

(10-13-2021 08:34 PM)rprosperi Wrote:  only the 42S includes recall arithmetic AND stack register access.

This works also on the WP-34S.

On the 34S, it's even easier, it has the FIB command built-in (thanks Pauli).

[Gerson W. Barbosa]

(10-14-2021 01:27 AM)rprosperi Wrote:  

(10-13-2021 10:07 PM)Didier Lachieze Wrote:  This works also on the WP-34S.

On the 34S, it's even easier, it has the FIB command built-in (thanks Pauli).

I fear FIB would not be of much help in the OP problem. NEXTFIB – if it existed – would be quite handy.
FIB on the wp34s is very useful, though. Here, for example, it has allowed me to save a lot of steps when compared to the equivalent HP-42S/Free42 program.