Puzzlet 80 - The Answer

THE PUZZLET PAGE

PUZZLET 080 - THE SOLUTION

' Puzzlet #080
' To find four different cubes, each
' having a 2-digit root, whose sum is
' exactly one million.
' By Dave Ellis.

def root1, root2, root3, root4: int
def sumRoots, flag: int
def rootsArray[100]: int
declare LoadRootsArray()
declare GetSumRoots()
declare PrintResult()

openconsole
LoadRootsArray()
print "Searching ...": print
root1 = 0
do
    root2 = root1 + 1
    do
        root3 = root2 + 1
        do
            root4 = root3 + 1
            flag = -1
            do
                sumRoots = GetSumRoots()
                if sumRoots > 1000000
                    flag = 0
                endif
                if sumRoots = 1000000
                    printResult()
                    flag = 0
                else
                    root4 = root4 + 1
                endif
            until flag = 0 | root4 > 99
            root3 = root3 + 1
        until root3 > 98 | (root3 => root4)
        root2 = root2 + 1
    until root2 > 78 | (root2 => root3)
    root1 = root1 + 1
until root1 > 77

print: print "No more!"
print: print "Press any key to exit ..."
do: until inkey$ <> ""
closeconsole
end

sub LoadRootsArray
' puts cubes of all 2-digit integers into
' rootsArray for later use by program
def i: int
for i = 10 to 109
    rootsArray[i - 10] = i*i*i
next i
return

sub GetSumRoots
' retrieves the cube roots of root1, root2,
' root3, and root4, sums them, and returns
' the total to the calling routine
def sum: int
sum = rootsArray[root1]
sum = sum + rootsArray[root2]
sum = sum + rootsArray[root3]
sum = sum + rootsArray[root4]
return sum

sub PrintResult
' pretty printer
print str$(root1 + 10) + "^3 +",
print str$(root2 + 10) + "^3 +",
print str$(root3 + 10) + "^3 +",
print str$(root4 + 10) + "^3 = 1,000,000"
return



PROGRAM NOTES

We commence by thinking about the possible range of cubes to work with. The minimum value is easy to determine, since it has to be two digits long - 10³.
What about the maximum value? It can't be greater than 99³, or it won't be two digits long. This equals 970,299, which is less than one million and therefore ok. It will have three other cubes added to it, but they can be just 10³, 11³, and 12³, and the whole shebang only adds up to 984,358 (still less than one million), so a maximum of 99³ is the right maximum cube.

The program commeces in the main routine by loading all legal cubes into array rootsArray[] by calling subroutine LoadRootsArray(), which places all the relevant cube-roots into cells 10 to 99 of rootsArray[].

Now all legal combinations of four cube-root values are investigated by nesting four DO loops. This has the same effect as nesting four FOR-NEXT loops. The reason for doing it this way is that IBasic doesn't have an EXIT FOR instruction. Iterators root1, root2, root3, and root4 are used for this operation. Note that root1 never exceeds 77 and root2 never exceeds 78. A few moments with a calculator will show why this is necessary.

For each of the legal combinations of the four cube-roots, the sum of their cubes is calculated by calling function GetCubeRoots() and storing the value in variable sumRoots. If this happens to equal 1,000,000 exactly, we have a valid solution, and subroutine PrintResult() is called to print it out.

When the program is run, it generates the screen shown below. There are a total of four solutions. The third line is interesting because the cube-roots form an Arithmetic Progression.

Searching ...

28^3 + 60^3 + 66^3 + 78^3 = 1,000,000
37^3 + 44^3 + 48^3 + 91^3 = 1,000,000
55^3 + 60^3 + 65^3 + 70^3 = 1,000,000
56^3 + 58^3 + 67^3 + 69^3 = 1,000,000

No more!

Press any key to exit ...

	Searching ... 28^3 + 60^3 + 66^3 + 78^3 = 1,000,000 37^3 + 44^3 + 48^3 + 91^3 = 1,000,000 55^3 + 60^3 + 65^3 + 70^3 = 1,000,000 56^3 + 58^3 + 67^3 + 69^3 = 1,000,000 No more! Press any key to exit ...