I was doodling yesterday in meeting, and found a closed-form solution to the 2008 Ulam Spiral mini-challenge that has been haunting me for three years from: this thread.

Usage: Enter a Number (N) and execute the program. It will return the non-trivial solutions for adjacent numbers in Ulam's spiral.
For example:

         17 yields 36, 38

         16 yields 05, 35

         14 yields 03, 33

         13 yields 30, 32

example spiral:

         37 36 35 34 33 32 31

         38 17 16 15 14 13 30 

          . 18 05 04 03 12 29 

          . 19 06 01 02 11 28

          . 20 07 08 09 10 27

          . 21 22 23 24 25 26

          .  .  .  .  . etc..

If you're interested, I've made a Stack Diagram describing how the STAT registers and careful stack discipline can be combined to accumulate terms without local variables, and only using two numbers in the program. (integers 3 and 5)

This program has a very concise check to see if
. It returns and

for corner numbers such as 31,37,43.

Otherwise it returns and

This closed form approach allows a 30% reduction in program space, AND an order of magnitude reduction in runtime. The new program is O(1) constant runtime, 37 bytes (28 steps max for all values with no looping)- The previous version from 2008 was O(N) and 54 bytes and 43 program lines with some considerable sized loops.

' 37-byte HP 42S ULAM spiral solution Allen T. 2/5/2011

00 { 37-Byte Prgm }

01 LBL 00

02 CL\Sigma    @ Clear Stat registers

03 ENTER

04 ENTER       @ Fill the stack up with input

05 3

06 5

07 \Sigma+     @ add 3 and 5 to Stat regs

08 +           @ add the 3 and 1 to get four	

09 STO× ST T   @ Put 4*N on level T

10 Rv          @ ROLLDN

11 \Sigma+     @ Add N to each of the Stat regs

12 STO- ST Z   @ Put 4N-2 on Stack level Z

13 R^          @ ROLLUP

14 +/-         @ NEG

15 RCL+ ST T   @ Put 4N-6 on Stack Level T

16 SQRT        

17 IP          

18 STO+ ST X   @ find 2*floor(sqrt(4N-2))  < doubles the number in X without loosing STACK(T) 3 bytes same cost as "2 *"

19 R^

20 SQRT

21 IP

22 STO+ ST X   @ find 2*floor(sqrt(4N-6))

23 X=Y?        @ if the numbers are the same, then it's a SIDE 

24 +/-         @ Need to subtract 2* the Side number

25 ENTER		  	

26 ABS         

27 \Sigma+     @ Otherwise add 2*Side number to both stat regs

28 RCL 13      @ Recall SUM(Y) register

29 RCL 11      @ Recall SUM(X) Register

30 .END.

Thanks to Thomas for his tutorial on using formulas. I did not follow the teacher exactly, but managed to get the formulas here anyway.

* NOTE - I do not believe this program is compatible with the HP41C due to the specific use of the linear stat register and the STO/RCL arithmetic (line 15). Caveat Emptor.

Five Reasons I think this is a nice demonstration program for the 42S and RPN flexibility:

1) Lines 04 and 09 allow use of STACK(T) copies as the lower stack items are consumed in operations

2) It's one of the very few RPN programs I've seen use both ROLLUP and ROLLDN

3) Byte-saving tricks like "STO+ ST X" to double a number without disturbing the stack. (Is there a better RPN way?)

4) Uses 3 stat registers rather than local variables

5) Wherever possible uses output from the STAT accumulator instead of entering numbers (byte conservation)

Edited: 5 Feb 2011, 11:11 p.m.

Amazing work, Allen, congratulations.

I was thinking about entering this code on my 32sii but I notice several references to things like STO * STO T and STO - STO Z. I assume these are 42s commands to put values directly on the stack, correct? And I don't believe these commands exist on the 32sii, is that correct?

Many thanks for this great work in algorithm development.

Hi Allen

You could reverse clearing the statistic registers and filling the stack thus saving one precious byte:

02 ENTER       @ Fill the stack up with input

03 CL\Sigma    @ Clear Stat registers

Clearing the statistic registers enables the stack lift. Since 3 and 5 follow only one ENTER is needed. Furthermore you could replace the two last statements with SUM. This instruction uses two bytes as well, so no gain with that change, but this makes the program independent of the setting of \GSREG. However this instruction is missing in the HP-41C.

Quote:

---

Thanks to Thomas for his tutorial on using formulas. I did not follow the teacher exactly, but managed to get the formulas here anyway.

---

Did you just save the images or did you find another ingenious way? In the latter case I could add it to the article. Which reminds me to add Egan's method he once posted as well.

It's a clever idea to use the statistic functions for some kind of parallel processing.

Kind regards

Thomas

Edited: 6 Feb 2011, 5:13 a.m.

Quote:

---

I was thinking about entering this code on my 32sii but I notice several references to things like STO * STO T and STO - STO Z.

---

The HP41-series offers direct access to the stack registers - they can be used in the same way as the usual numbered registers. So STO Z directly stores X in stack register Z, or ST+ T adds X to register T. This allows very effective programming and elegant solutions like ST+ X for doubling a number (even without affecting LastX).

The 42s adds two more features: Since it can also use named storage registers a simple "STO T" might be confusing because it may refer to stack register T as well as a variable named T. That's why there's an additional "ST" for "stack" in commands referring to stack registers: STO T stores a value in variable T, while STO ST T stores it in the top stack tegister T. On the other hand, the 42s can also do all this with recall-arithmetics as well: RC+ ST Z adds the content of stack register Z to the value in X without affecting the stack otherwise.

No, all this can't be done on the 32s and similar calculators.

Dieter

Thomas,
This is fantastic, Thanks! I made the change- yes even to save 1 byte. I also did not realize about the SUM function- I've always been concerned until now about making it independent of the REG settings- now I know how!!

Don noted ULAM shows a correlation between meeting doodles and math.. perhaps I should go to more meetings!

I made it work with the 41C by changing line 15 from

15 RCL+ ST T

to

15 R^

16 STO+ ST Y

17 Rv

Mark, Thanks for your 41C Fix!! I made the output from FREE42 and used HP41UC to create a 41C barcode, then scanned it in using my wand- sure it may have been faster just to type the thing in, but I'm not sure how to type R^ in the 41c.

Thomas, I incorporated your Stack lift saving 1 byte and SUM features, I also found a way to save 4 more bytes by getting rid of some of the 2-Byte STO+ instructions from above. Now it's down to 32 Bytes- Not sure I can do much better than that.

Quote:

---

but I'm not sure how to type R^ in the 41c

---

Special characters are listed on the back of the calculator:

So the keystrokes would be:

• XEQ
  
• ALPHA
  
• 7
  
• Shift
  
• ENTER^
  
• ALPHA
  

HTH

Thomas