S&SMC#12: My original solutions and comments Message #33 Posted by Valentin Albillo on 28 Nov 2005, 7:28 a.m., in response to message #1 by Valentin Albillo
Hi all:
First of all, many thanks for the overwhelming number of excellent solutions you've posted in so many versions for so many different HP models (and the odd SHARP), it's been really great to see so many of you interested in my humble challenge. Also, your kind comments are much appreciated, even by the ones who couldn't post a solution this time (Hi, Bram!), thank you so much.
Now these are my two original solutions, the reference one for the HP71B, and the one derived from it for the HP15C. As I told Mr. Barbosa in an early post, they aren't optimal in any sense, because though I fully knew about the formulae that could compute the sum of N cubes directly, without iteratively adding the cubes up, one at a time, I decided I would provide a solution similar to the one an individual not knowing the existence of said formulae could come up with, by using common engineering sense to speed the search instead of blindly relying in a pure brute force approach.
The HP71B reference solution
That being so, the reference solution for the HP71B does not use any formula at all, as seen in the following 3line, 129 byte, GOTOless program (arbitrary line numbers):
1 FOR N=15 TO 500 @ S=N*N @ L=INT((S/4)^(1/3)) @ FOR C=L TO 3 STEP 1
2 S=SC*C*C @ IF S=0 THEN DISP N;C;L @ END ELSE IF S<0 THEN S=S+L*L*L @ L=L1
3 NEXT C @ NEXT N @ DISP "Not found"
>RUN
312 14 25
which takes some 9 seconds under Emu71 @ 2.4 Ghz, and a few minutes in a physical HP71B. A brief explanation of its workings:
 Since the challenge asks for more than three consecutive cubes, and 1^{3} is not legal, we must search from 2^{3}+3^{3}+4^{3}+5^{3} = 224 > 14.96^2 up, so we begin our search at N=15.
 We further arbitrarily restrict our search up to N=500, but this value doesn't affect execution time at all since the search will end as soon as the minimum solution is found, so we could put N=1000000 instead and it would make no difference.
 Since there must be at least 4 consecutive cubes in the solution, we'll start adding cubes from a maximum value depending on N, and go down till either we find a solution, or we reach 1. The maximum value for each cube must be near 1/4th of the value of N, since at least four of them will be added up and they're roughly the same size.
 Then, starting from the greater four cubes, we keep on adding smaller cubes till a solution is found. If our sum exceeds N, we subtract the largest cube and keep on adding smaller ones, and this process is repeated until either we've found a solution or we've reached to 1. In that case, this value of N can't be so expressed and we proceed to the next value for N.
Eventually the solution is found:
312^{2} = 14^{3} + 15^{3} + 16^{3} + 17^{3} + 18^{3} + 19^{3} + 20^{3} + 21^{3} + 22^{3} + 23^{3} + 24^{3} + 25^{3} = 97344
for a total of 12 (S&SMC#12) consecutive cubes being added up. As some people discovered, there's a nearsolution:
315^{2} = 25^{3} + 26^{3} + 27^{3} + 28^{3} + 29^{3} = 99225
adding up only 5 cubes. But the requirements were for the minimum value of N, and 312 is less than 315.
The HP15C derived solution
There are two main points in creating a reference solution for the HP71B, namely:
 Anyone can enter and run it, regardless of they having a physical HP71B, thanks to the incredible and free Emu71, a nearperfect emulator for the HP71B created by JeanFrançois Garnier, with the added advantages of much faster execution times and the convenience of full PC keyboard and screen. A solution for other models would only be accessible for people having those physical models or their emulators, possibly nonfree, or much more onerous to get and install.
 HP71B BASIC is extremely easy to understand, most specially for native English speakers, being quite similar to natural language, so it's actually very easy to translate the reference solution to any other programming language such as RPN, RPL, or C#, say. That wouldn't be the case for an RPN and, most specially, RPL solution that by their very nature are extremely cryptic and difficult to convert to nonstack machines.
To demonstrate this, the following HP15C RPN solution was produced from the above reference solution for the HP71B:
01 LBL A 19 RCL RAN# 33 X=0? 47 GTO 0
02 3 20 Y^X 34 GTO 3 48 LBL 3
03 1/X 21 INT 35 TEST 3 49 RCL 0
04 STO RAN# 22 STO 1 36 GTO 4 50 R/S
05 .003 23 RCL+I 37 RCL 1 51 RCL 3
09 STO I 24 STO 3 38 RCL*1 52 INT
10 15 25 LBL 1 39 RCL*1 53 R/S
12 STO 0 26 RCL 3 40 STO+2 54 RCL 1
13 LBL 0 27 INT 41 DSE 1
14 RCL 0 28 ENTER 42 LBL 4
15 X^2 29 X^2 43 DSE 3
16 STO 2 30 * 44 GTO 1
17 4 31 STO2 45 ISG 0
18 / 32 RCL 2 46 LBL 0
which is 54 steps long and takes 1 h 45 min to find the solution. You can insert a pause statement (PSE) after step 14 RCL 0, in order to see how the search progresses. To run it:
RUN > N
R/S > C
R/S > L
The conversion process (i.e.: compilation) from reference 71B BASIC to 15C RPN is easy and almost automatic, and goes like this:
 First, let's map the BASIC variables used to RPN registers, like this:
0: N
1: L
2: S
3: C
 Also, we'll optmize for speed by storing a needed constant (the lower limit of the cube search, in RPN's ISG/DSE convention) in register I, and 1/3 (for cube roots) in register #RAN:
I : 0.003
#RAN: 1/3
Now, we'll simple translate statement for statement, like this:
 (required RPN setup)
01 LBL A (entry point)
02 3
03 1/X
04 STO RAN# (speed optimization, for cube roots)
05 .003
09 STO I (speed optimization, for ISG/DSE)
 1 FOR N=15 TO 500
10 15
12 STO 0 (N=15; the upper limit is ignored, search till a solution is found)
13 LBL 0 (it's a FOR, so we'll loop to here)
 @ S=N*N
14 RCL 0 (N)
15 X^2
16 STO 2 (S=N^2)
 @ L=INT((S/4)^(1/3))
17 4
18 / (S/4)
19 RCL RAN# (1/3)
20 Y^X
21 INT
22 STO 1 (L=INT(S/4)^(1/3))
 @ FOR C=L TO 3 STEP 1
23 RCL+I (we construct L.003, for ISG/DSE)
24 STO 3 (C=L.003)
25 LBL 1 (it's a FOR so we'll loop to here
 2 S=SC*C*C
26 RCL 3 (C, with .003 attached)
27 INT (C by itself)
28 ENTER
29 X^2 (C^2)
30 * (C^3)
31 STO2 (S=SC^3)
 @ IF S=0 THEN DISP N;C;L @ END
32 RCL 2 (S)
33 X=0? (S=0?)
34 GTO 3 (yes, go deal with that case)
...
48 LBL 3 (here we deal with a solution)
49 RCL 0 (N)
50 R/S (stop for the user to see it)
51 RCL 3 (C with 0.003 attached)
52 INT (C by itself)
53 R/S (stop for the user to see it
54 RCL 1 (L, and last step: end program execution)
 ELSE IF S<0 THEN S=S+L*L*L
35 TEST 3 (did we exceed N?)
36 GTO 4 (not yet, go on)
37 RCL 1 (yes, recall L)
38 RCL*1 (L^2)
39 RCL*1 (L^2)
40 STO+2 (put it back in the running sum)
 @ L=L1
41 DSE 1 (decrease L by one)
42 LBL 4 (the search continues here)
 3 NEXT C
43 DSE 3 (decrease C by one and see if we can loop)
44 GTO 1 (yes, go loop)
 @ NEXT N
45 ISG 0 (increment N by one)
46 LBL 0 (place holder, we'll loop indefinitely)
47 GTO 0 (go loop for another N)
 @ DISP "Not found"
(no code, it never happens)
That's all. Thanks for your interest and
Best regards from V.
