The problem statement from the Ole Miss Problems of the Week page is:

The integer 36 is a square number because it equals 6^{2}.
Thirty-six is also a triangular number since it is the sum of the
integers 1 through 8.
Thirty six is the lowest integer greater than one that is both
square and triangular.
What are the next three integers that are both square and
triangular?
You must have all three correct.

This certainly sounds like a search problem to me: find the three smallest integers greater than 36 which are both square and triangular. I suppose we could write a program for the Casio CFX-9850G or FX-7400G calculator to find these. Or I suppose we could ... no, let’s write a program. That’s what we do, after all.

We could generate all numbers, and check whether they are both square and triangular. We could generate triangular numbers, and check whether they are also square numbers. We could generate square numbers, and check whether they are also triangular numbers. Or we could do something else. We always wind up generating one type of number and checking whether it is another type of number, so let’s do something else this time.

We will generate both types of numbers, in parallel, and detect overlaps — when the two streams of numbers have a common element.

We will have two items of state for each generator: the current index,
and the current value.
For example, when the index to the triangular generator is *k*,
the current value will be 1 + 2 + ... + *k*.
We can get to the next triangular number by first incrementing the
index by 1, then incrementing the value by the index.
We can get to the next square number by first incrementing the index
by 1, then either squaring the index to get the value, or adding the
difference between the old square value and the new square value.
If the square index is *n*, the new square value is
*n*^{2}, and the old square value is
(*n*-1)^{2} or *n*^{2}-2*n*+1.
So we can get the new square value by adding 2*n*-1 to
the old square value, and that is what we will do.

Why this odd formula for the square?
Habit from non-calculator days.
The CFX-9850G has only floating point numbers — simply squaring
the number would in fact be quicker than using the formula.
But on most computers, we would do this using integer variables, not
floating point variables.
Computing 2*n*-1 with integer variables is a shift and an
add — which is generally much quicker than a multiply.

We run each generator in turn, as long as the value is less than the value of the other generator. When the values of the two generators are equal, we have computed a number that is both square and triangular. We will want to generate five such numbers: 1, 36, and the three values we are supposed to discover.

The program is given here, and is also available as a text file with .CAT file contents. As usual, a semicolon (“;”) introduces a comment that is not to be entered into the calculator.

Program P040499 (132 bytes):

; Variables: ; A is the index for the triangular number generator ; B is the index for the square number generator ; C is the value for the triangular number generator ; D is the value for the square number generator ; E is the count of triangular square numbers found ; Symbols: ; -> is the assignment arrow ; < is the less than relational ; = is the equality relational ; _ is the display triangle 1->A ; Initialize index for triangular 1->B ; Initialize index for square 1->C ; Initialize value for triangular 1->D ; Initialize value for square 0->E ; Initialize count of square triangular numbers While E<5 ; Loop until 5 square triangular numbers found While C<D ; Run the triangular generator A+1->A ; Increment the triangular index A+C->C ; Compute the triangular number WhileEnd ; [End of run the triangular generator] While D<C ; Run the square generator B+1->B ; Increment the square index 2B-1+D->D ; Compute the square number WhileEnd ; [End of run the square generator If C=D ; Test whether the square and triangular numbers ; are equal Then A_ ; If so, display the triangular index B_ ; and the square index C_ ; and the number E+1->E ; Increment the count of numbers found A+1->A ; Advance the triangular generator A+C->C ; one step to break the tie IfEnd ; [End of test whether square and triangular] WhileEnd ; [End of loop until 5 numbers found] "Done" ; Report completion

We run this program, and it quickly generates the triples:

1 1 1 8 6 36 49 35 1225 288 204 41616 1681 1189 1413721 Done

So the next three numbers that are both square and triangular are 1225, 41616, and 1413721.

We could almost do this problem analytically.
The formula for a square number is *n*^{2}, as we
noted above.
The formula for a triangular number is *m*(*m*+1)/2
or (*m*^{2} + *m*) / 2.
Setting these two equal to one another, we have:

*n*^{2} - ½*m* - ½*m*^{2} = 0

Using the quadratic formula, we can solve for either of *m*
or *n* in terms of the other.
However, restricting the answers to integers — making this
Diophantine — means we still have to search for solutions.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 15 October 2001.