HHC 2019 will be in Reno, Nevada, Sept 21-22

[David Hayden]

Here is my entry, which won the "Modern RPN" prize.

Rather than going through the numbers 100-999 and extracting digits, this goes through the digits and constructs the number. I figured that this would be faster (unverified), but I see from other posts that it results in much larger code (63 steps with the label and END vs. mid-high 30's).

Let's call the digits in the number X,Y,Z. So when considering the number 123, X=1, Y=2 and Z=3.

The program loops through possible values of X, then Y, then Z. Along the way it computes the partial sums of cubes:
S1 = X^3
S2 = X^3+Y^3
S3 = X^3+Y^3+Z^3
and also stores the partial values of the number:
N1 = X00
N2 = XY0
N3 = XYZ

all of this is to minimize the computation needed in the innermost loop.

The program breaks out of the "Z" loop if it determines that the partial sum-of-cubes is larger than any possible value that would be considered in the loop. This cuts the number of iterations in the Z loop to 440. A similar test in the Y loop could avoid some iterations of Z completely but I decided that one pass through the Z loops was worth saving the space and time of the duplicate check.

In pseudocode-Prime code, the program is:

Code:

// Pre-compute 0^3..9^3
for X from 1 to 9 do          // No leading zeros
  S1 := X^3;
  N1 := 100*X;
  for Y from 0 to 9 do
    S2 := S1 + Y^3;
    N2 := N1 + 10*Y
    for Z from 0 to 9 do
      S3 := S2 + Z^3;
      N3 := N2+Z;
      if (S3 = N3) then
        print N3;  // Got it!
      END;
      if S3 > N2+9 then break; end;    // No future value of Z will work
    END;
  END;
END;

Registers (in the end I didn't need some of these)
R0..R9 0^3 - 9^3
R10..R11 Partial sums S1..S3
R13..R15 Partial numbers N1..N3
R16..R18 Digits X, Y, and Z
R19 Index to store results
R20..R23 Results

Labels:
L02..L04 Top of X, Y, and Z loops
L05 Bottom of Y loop
L06 Bottom of Z loop

Code:

01 LBL "CUBES"
02 9            ; pre-compute 0^3 .. 9^3 into R00..R09
03 LBL 01
04 RCL ST X
05 3
06 Y^X
07 STO IND ST Y
08 X<>Y
09 DSE ST X
10 GTO 01
11 STO 00        ; X=0 when you get here

12 23          ; R19 is index register for storing results
13 STO 19

14 1.009        ; for X digit = 1 to 9
15 STO 16
16 LBL 02
17 RCL IND 16    ; X^3
18 STO 10      ; S1 = X^3
19 RCL 16
20 IP
21 100
22 *
23 STO 13        ; N1 = X*100

24 .009        ; for Y digit = 0 to 9
25 STO 17
26 LBL 03
27 RCL IND 17    ; Y^3
28 RCL+ 10
29 STO 11        ; S2 = X^3 + Y^3
30 RCL 17
31 IP
32 10
33 *            ; Y*10
34 RCL+ 13        ; X*100 + Y*10
35 STO 14        ; N2 = X*100 + Y*10

36 .009        ; For Z digit = 0 to 9
37 STO 18
38 LBL 04
39 RCL IND 18    ; Z^3
40 RCL +11     ; X^3 + Y^3 + Z^3 (S3)
41 RCL 18
42 IP
43 RCL+ 14        ; X*100 + Y*10 + Z (N3)
44 X=Y?        ; if X^3+Y^3+Z^3 = N3
45 STO IND 19    ; then store it
46 X=Y?           ; and increment the
47 DSE 19        ; result index register
48 9            ; DSE never faills
49 +
50 X<Y?        ; if S3 > N3+9 then no value for Z will work.
51 GTO 05        ; go to bottom of Y loop
52 ISG 18        ; Next Z
53 GTO 04

54 LBL 05        ; Next Y
55 ISG 17
56 GTO 03

57 ISG 16        ; Next X
58 GTO 02

59 RCL 23        ; Recall the 4 results to the stack
60 RCL 22
61 RCL 21
62 RCL 20
63 END