Post Reply 
HP 25 Fibonacci sequence in one program step
10-13-2021, 01:03 PM
Post: #1
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. Smile
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 01:23 PM
Post: #2
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.

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

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
10-13-2021, 01:30 PM
Post: #3
RE: HP 25 Fibonacci sequence in one program step
RCL+ Y ??


The 34S has the FIB command.



Pauli
Find all posts by this user
Quote this message in a reply
10-13-2021, 02:02 PM (This post was last modified: 10-13-2021 02:22 PM by Joe Horn.)
Post: #4
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.

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.

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 02:19 PM
Post: #5
RE: HP 25 Fibonacci sequence in one program step
(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.
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 02:30 PM
Post: #6
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. 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.

  
All My Articles & other Materials here:  Valentin Albillo's HP Collection
 
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 02:36 PM (This post was last modified: 10-13-2021 02:39 PM by Joe Horn.)
Post: #7
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. 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...

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 02:43 PM (This post was last modified: 10-13-2021 02:44 PM by Dave Britten.)
Post: #8
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.
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 04:00 PM
Post: #9
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 :

[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.
Find all posts by this user
Quote this message in a reply
10-13-2021, 04:42 PM
Post: #10
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 * * * …
Find all posts by this user
Quote this message in a reply
10-13-2021, 06:26 PM
Post: #11
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. 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.
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 06:53 PM
Post: #12
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?
Find all posts by this user
Quote this message in a reply
10-13-2021, 07:11 PM
Post: #13
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
Find all posts by this user
Quote this message in a reply
10-13-2021, 07:35 PM
Post: #14
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! Smile
Find all posts by this user
Quote this message in a reply
10-13-2021, 07:47 PM
Post: #15
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! Smile

Very clever! Does this work on any other models? I can't think of any.
Visit this user's website Find all posts by this user
Quote this message in a reply
10-13-2021, 08:34 PM
Post: #16
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
Find all posts by this user
Quote this message in a reply
10-13-2021, 10:07 PM
Post: #17
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
Find all posts by this user
Quote this message in a reply
10-13-2021, 11:34 PM
Post: #18
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. Smile
You can even 'run' that on an HP21 !!

Mike T.

HP21, HP25, HP32E, HP33C, HP34C, HP10C, HP11C, HP12C, HP32S, HP22S
Find all posts by this user
Quote this message in a reply
10-14-2021, 01:27 AM
Post: #19
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). Smile

--Bob Prosperi
Find all posts by this user
Quote this message in a reply
10-14-2021, 03:45 AM
Post: #20
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). 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.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: