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

The sum of 48 and 1 is a perfect square: 48 + 1 = 49 and √49 = 7. The sum of one-half of 48 and 1 is also a perfect square: ½48 + 1 = 24 + 1 = 25 and √25 = 5. Find the next greatest integer with this unique property.

Aha! “Find”! That means a search — and a search means an automaton — and an automaton means (for us, at least) a programmable calculator. Fortunately, we have a CFX-9850G or FX-7400G here, which, as it happens, appears to be a programmable calculator.

Isn’t it amazing that we always wind up writing a program for these things? I guess we are just one-trick ponies.

Anyway, we want to search some space for solutions to the question above. We could search the integers directly for the solution desired — that would be perfectly straightforward. That would also, we suspect, be very slow. Doubtless there are a great many integers which do not have either of the properties desired: they are perfect squares after you add 1 to them, and they are perfect squares after you halve them and add 1.

So, we insure that we generate numbers that match at least one of the properties. Let us pick the second property: we want the numbers to be perfect squares after we halve them and add 1. A way to guarantee this is to generate integers and square them — these are the perfect squares. Subtract one and double, and we have the number that satisfies the property. All that remains is to add one to the resulting number and see if it is a perfect square.

The obvious way to see if a number is a perfect square is to take its square root and see if the square root is an integer. Unfortunately, square roots are generally not exact — the square root of 16 might be computed as 4.00000000000001 or 3.99999999999999, which are not integral. While the calculator corrects for this to some extent — numbers “close to” integers may be treated as if they were the actual integers, for example — it is better to deal with this explicitly. If we round the computed square root to the nearest integer, then square that integer, and then compare that to the original number, we have a much better test of whether the original number is a perfect square. The square root function can be wrong by quite a bit before the more elaborate test fails. So this is what we will do.

The search program is given below, and is also available as a text file with .CAT file contents. Semicolon (“;”) starts a comment that is not to be entered into the calculator.

Program P041600 (76 bytes):

; Variables: ; A is lower square root ; B is candidate number ; C is candidate number plus 1 ; D is perfect square nearby to C ; Symbols: ; -> is assignment arrow ; x^2 is square operator ; sqrt is square root operator ; = is equal relational ; _ is display triangle 0->A ; Initialize lower square root Do ; Loop forever 1+A->A ; Add one to lower root 2(Ax^2-1)->B ; Square, decrement, and double B+1->C ; Increment (Int (.5+sqrtC))x^2->D ; Find nearby perfect square If C=D ; Test if is perfect square Then B_ ; If so, display the number IfEnd ; [End of test if is perfect square] LpWhile 1 ; [End of loop forever]

We run this program, and it generates the output:

0 48 1680 57120 1940448

The program would generate more of these numbers — we did write the program to loop forever, after all — but we can stop it here. So “the next greatest integer with this unique property” is 1680.

[ Previous page | Top of page | Next page ]

Copyright © 2001 Brian Hetrick

Page last updated 25 November 2001.