HP 25 Fibonacci sequence in one program step
10-13-2021, 01:03 PM
Post: #1
 Dave Britten Senior Member Posts: 2,168 Joined: Dec 2013
HP 25 Fibonacci sequence in one program step
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.
10-13-2021, 01:23 PM
Post: #2
 rprosperi Super Moderator Posts: 5,529 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
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.

--Bob Prosperi
10-13-2021, 01:30 PM
Post: #3
 Paul Dale Senior Member Posts: 1,770 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
RCL+ Y ??

The 34S has the FIB command.

Pauli
10-13-2021, 02:02 PM (This post was last modified: 10-13-2021 02:22 PM by Joe Horn.)
Post: #4
 Joe Horn Senior Member Posts: 1,903 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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.

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.

<0|ɸ|0>
-Joe-
10-13-2021, 02:19 PM
Post: #5
 Dave Britten Senior Member Posts: 2,168 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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.
10-13-2021, 02:30 PM
Post: #6
 Valentin Albillo Senior Member Posts: 912 Joined: Feb 2015
RE: HP 25 Fibonacci sequence in one program step
(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.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

10-13-2021, 02:36 PM (This post was last modified: 10-13-2021 02:39 PM by Joe Horn.)
Post: #7
 Joe Horn Senior Member Posts: 1,903 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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...

<0|ɸ|0>
-Joe-
10-13-2021, 02:43 PM (This post was last modified: 10-13-2021 02:44 PM by Dave Britten.)
Post: #8
 Dave Britten Senior Member Posts: 2,168 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
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.
10-13-2021, 04:00 PM
Post: #9
 C.Ret Member Posts: 218 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
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.
10-13-2021, 04:42 PM
Post: #10
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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 * * * …
10-13-2021, 06:26 PM
Post: #11
 Dave Britten Senior Member Posts: 2,168 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
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.
10-13-2021, 06:53 PM
Post: #12
 David Hayden Senior Member Posts: 412 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
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?
10-13-2021, 07:11 PM
Post: #13
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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
10-13-2021, 07:35 PM
Post: #14
 David Hayden Senior Member Posts: 412 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(10-13-2021 07:11 PM)Gerson W. Barbosa Wrote:  0 1 +

Then repeat

RCL + ST L
That's it!
10-13-2021, 07:47 PM
Post: #15
 Dave Britten Senior Member Posts: 2,168 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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.
10-13-2021, 08:34 PM
Post: #16
 rprosperi Super Moderator Posts: 5,529 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
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.

--Bob Prosperi
10-13-2021, 10:07 PM
Post: #17
 Didier Lachieze Senior Member Posts: 1,539 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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
10-13-2021, 11:34 PM
Post: #18
 Mike T. Member Posts: 96 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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 !!

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
10-14-2021, 01:27 AM
Post: #19
 rprosperi Super Moderator Posts: 5,529 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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).

--Bob Prosperi
10-14-2021, 03:45 AM
Post: #20
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: HP 25 Fibonacci sequence in one program step
(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.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)