Previous page Next page Navigation bar

Puzzles

Prior to 2001 Puzzles

4 April 1999 (Squares and Triangles)

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

The integer 36 is a square number because it equals 62. 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 n2, and the old square value is (n-1)2 or n2-2n+1. So we can get the new square value by adding 2n-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 2n-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 n2, as we noted above. The formula for a triangular number is m(m+1)/2 or (m2 + m) / 2. Setting these two equal to one another, we have:

n2 - ½m - ½m2 = 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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 15 October 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

Index

3 December 2000

27 October 2000

16 April 2000

9 April 2000

19 March 2000

13 February 2000

6 February 2000

28 November 1999

12 September 1999

8 August 1999

25 July 1999

11 July 1999

30 May 1999

4 April 1999

29 April 1996

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data