' Puzzlet #015.
' Three successive 3-digit integers are all
' the sum of two squares: 520, 521, 522.
' (520 = 6^2 + 22^2, 521 = 11^2 + 20^2, and
' 522 = 9^2 + 21^2).
' Are there any other triplets of successive
' 3-digit integers with this property?
' By Dave Ellis.

declare loadSquares()
declare loadSumsOfSquares()
declare sortArray()
declare setDuplicatesToZero()
declare printRuns()
def squares[32]: int
def sumSquares[466, 4]: int

openconsole
print "Checking ..."
loadSquares()
loadSumsOfSquares()
sortArray()
setDuplicatesToZero()
sortArray()
printRuns()
print "No more found."
print: print "Press any key to close ..."
do: until inkey$ <> ""
closeconsole
end

sub loadSquares
' Loads all legal squares into squares[]
def i: int
for i = 1 to 31
    squares[i] = i*i
next i
return

sub loadSumsOfSquares
' Loads all combinations of 2 different legal
' squares into sumSquares[].
def count, i, j: int
count = 0
for i = 1 to 30
    for j = i + 1 to 31
        count = count + 1
        sumSquares[count, 1] = squares[i] + squares[j]
        sumSquares[count, 2] = squares[i]
        sumSquares[count, 3] = squares[j]
    next j
next i
return

sub sortArray
' Sorts the contents of sumsquares[] into
' ascendingorder using a simple Bubble Sort.
def endpoint, flag, n: int
do
    endpoint = 464
    flag = -1
    for n = 1 to endpoint
        if sumSquares[n, 1] > sumSquares[n + 1, 1]
            flag = 0
            sumSquares[0, 1] = sumSquares[n, 1]
            sumSquares[n, 1] = sumSquares[n + 1, 1]
            sumSquares[n + 1, 1] = sumSquares[0, 1]
            sumSquares[0, 2] = sumSquares[n, 2]
            sumSquares[n, 2] = sumSquares[n + 1, 2]
            sumSquares[n + 1, 2] = sumSquares[0, 2]
            sumSquares[0, 3] = sumSquares[n, 3]
            sumSquares[n, 3] = sumSquares[n + 1, 3]
            sumSquares[n + 1, 3] = sumSquares[0, 3]
        endif
    next n
    endpoint = endpoint - 1
until flag = -1
return

sub setDuplicatesToZero
' Resets value of all duplicates in sumSquares[]
' to zero.
def i, j: int    
for i = 1 to 465
    j = 1
    do
        if i + j < 466
            if sumSquares[i, 1] = sumSquares[i + j, 1]
                sumSquares[i + j, 1] = 0
            endif
            j = j + 1
        endif
    until i + j = 466
next i   
return

sub printRuns
' Prints all runs of 3 or more successive values
' in sumSquares[].
def flag, i, j, k: int
print
i = 1
do
    j = 1
    flag = -1
    do
        if i + j < 466
            if sumSquares[i, 1] + j = sumSquares[i + j, 1]
                j = j + 1
            else
                flag = 0
            endif
        else
            flag = 0
        endif
    until flag = 0
    if j >  2
        for k = i to i + j - 1
            print using ("###", sumSquares[k, 2]),
            print " + ",
            print using ("###", sumSquares[k, 3]),
            print " = ",
            print using ("###", sumSquares[k, 1])
        next k
        print
    endif
    i = i + j
until i > 465
return

PROGRAM NOTES

This program uses the top-down approach.  Its operation is described in a handful of commands whose functions are more or less self-explanatory.  Each command calls a subroutine which breaks the task down into smaller tasks.

There are six of these macro-level commands:

1.  loadSquares()
2.  loadSumsOfSquares()
3.  sortArray()
4.  setDuplicatesToZero()
5.  sortArray()
6.  printRuns()


1.  loadSquares()

The largest possible 3-digit integer is 999.  This has to be the sum of 2 squares. The smallest possible square is 1.  Therefore the largest possible is 999 - 1 = 998. The square root of 998 is 31.59.  The largest practical square is going to be 31. So we can limit the range of numbers to generate squares as 1 to 31 inclusive. loadsquares() generates every square from 1 to 31 and places the values into the array squares[] ready for further processing.


2.  loadSumsOfSquares()

This subroutine's job is to use the squares already saved in the array squares[] to load the array sumSquares[] with all possible sums of pairs of those squares. So, we're looking for the number of ways you can take two items at a time from 31.  Using your calculator, you will see that ³¹15₂ = 465, and that is the size of the target array.

We need to keep track of where all those individual sums came from, so  sumSquares[] was set up as a 2-dimensional array.  The first dimension is 465 elements, and the second is 3 cells, one for the sum, one for the first square it was derived from, and the last cell for the second square.  Each of the 465 elements will thus hold a sum and the two squares which made the sum.

Using variables i and j as iterators, and variable count  as pointer to the cells within each of the 465 elements, every sum and its two squares are soon safely stored in sumSquares[].


3.  sortArray()

We're looking for sums of squares in sequence.  If we scan the contents of sumSquares[] as it stands, nothing will be learned - they're not in any sort of order.  The subroutine sortArray's job is to sort this problem out - literally.  Using a simple bubble sort, it arranges all those sums into ascending order, taking care that the pairs of squares from which the various sums were derived stay with their particular sums.  


4.  setDuplicatesToZero()

A lot of the sums of squares will be duplicates of each other.  These can be discarded, and setDuplicatesToZero accomplishes this.  


5.  sortArray() (again!)

After the duplicate squares have been set to zero, those zeroes will be scattered liberally in the list of 465, making scanning for sequences very much a hit and miss affair.  By resorting the array, easily accomplished by calling sortArray again, all those zeroes will be swept to the front, leaving all non-zeroe squares neatly in ascending order at the rear or the queue.


6.  printRuns()

Finally, we're ready to actually scan for runs of three successive squares, since they're all neatly in ascending order with all duplicates removed.  Variable i is used as a placeholder in the queue of 465 squares.  Variable j is used to check that the succeeding square is an increment of the one i is currently pointing to. If it is, j is incremented to look at the next square as well.  If that's an increment of its predecessor, we have a sequence of three squares, and variable k is used as an iterator to print out all three.

When you run the code,  it pro- duces the inset screen.  There are five solutions in all. The triplets beginning at 232, 520, 584, 800, 809 each contain three integers all of which are are the sum of two squares.

Checking ...  36 + 196 = 232  64 + 169 = 233    9 + 225 = 234   36 + 484 = 520 121 + 400 = 521   81 + 441 = 522 100 + 484 = 584     9 + 576 = 585 225 + 361 = 586   16 + 784 = 800 225 + 576 = 801 361 + 441 = 802 324 + 484 = 808   25 + 784 = 809   81 + 729 = 810 No more found. Press any key to close ...