HP Forums
HP 25 Fibonacci sequence in one program step - Printable Version

+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: HP 25 Fibonacci sequence in one program step (/thread-17577.html)

Pages: 1 2


HP 25 Fibonacci sequence in one program step - Dave Britten - 10-13-2021 01:03 PM

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


RE: HP 25 Fibonacci sequence in one program step - rprosperi - 10-13-2021 01:23 PM

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


RE: HP 25 Fibonacci sequence in one program step - Paul Dale - 10-13-2021 01:30 PM

RCL+ Y ??


The 34S has the FIB command.



Pauli


RE: HP 25 Fibonacci sequence in one program step - Joe Horn - 10-13-2021 02:02 PM

(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? Huh No idea. I would have guessed that it would require 3 steps on a '25. Confused 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.


RE: HP 25 Fibonacci sequence in one program step - Dave Britten - 10-13-2021 02:19 PM

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

I'll warn you, it's both really stupid, and really clever. Big Grin 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.


RE: HP 25 Fibonacci sequence in one program step - Valentin Albillo - 10-13-2021 02:30 PM

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

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


RE: HP 25 Fibonacci sequence in one program step - Joe Horn - 10-13-2021 02:36 PM

(10-13-2021 02:19 PM)Dave Britten Wrote:  I'll warn you, it's both really stupid, and really clever. Big Grin 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! Smile Still looking for the best starting X...


RE: HP 25 Fibonacci sequence in one program step - Dave Britten - 10-13-2021 02:43 PM

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.


RE: HP 25 Fibonacci sequence in one program step - C.Ret - 10-13-2021 04:00 PM

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.


RE: HP 25 Fibonacci sequence in one program step - Gerson W. Barbosa - 10-13-2021 04:42 PM

(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 * * * …


RE: HP 25 Fibonacci sequence in one program step - Dave Britten - 10-13-2021 06:26 PM

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

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.


RE: HP 25 Fibonacci sequence in one program step - David Hayden - 10-13-2021 06:53 PM

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?


RE: HP 25 Fibonacci sequence in one program step - Gerson W. Barbosa - 10-13-2021 07:11 PM

(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


RE: HP 25 Fibonacci sequence in one program step - David Hayden - 10-13-2021 07:35 PM

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

Then repeat

RCL + ST L
That's it! Smile


RE: HP 25 Fibonacci sequence in one program step - Dave Britten - 10-13-2021 07:47 PM

(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! Smile

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


RE: HP 25 Fibonacci sequence in one program step - rprosperi - 10-13-2021 08:34 PM

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.


RE: HP 25 Fibonacci sequence in one program step - Didier Lachieze - 10-13-2021 10:07 PM

(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


RE: HP 25 Fibonacci sequence in one program step - Mike T. - 10-13-2021 11:34 PM

(10-13-2021 06:26 PM)Dave Britten Wrote:  But that that point, one scarcely needs a program at all. Smile
You can even 'run' that on an HP21 !!


RE: HP 25 Fibonacci sequence in one program step - rprosperi - 10-14-2021 01:27 AM

(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). Smile


RE: HP 25 Fibonacci sequence in one program step - Gerson W. Barbosa - 10-14-2021 03:45 AM

(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). Smile

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.