Puzzlet 79 - The Answer

THE PUZZLET PAGE

PUZZLET 079 - THE SOLUTION

The key to solving this Puzzlet is to be aware of the formula for finding the sum of a series of numbers. If S_n is the sum, and n is the highest number in the list, then:

Let's apply this to the Puzzlet, using m for "my house number" and n as the highest number in the street. We replace n with m in two places. Now subtract 1 from m in two places to compensate for the fact that we're only interested in houses numbered less than m. Then the sum of all the house numbers less than m, S_m-1, is:

The sum of all the house numbers greater than mine will equal the sum of all the houses in the street, minus the sum of all the houses up to and including mine. That is, S_m+1 = S_n - S_m. Therefore,

Now, we know that S_m-1 = S_m+1, so we can say that:

A little algebra now will lead from this to the following formula for my house number, m:

Now we have enough to write some code! Note in the listing that follows that m is replaced with the more meaningful myHseNr, and n is likewise replaced with maxHseNr.

' Puzzlet #079
' The sum of the house numbers less than
' mine in my street is equal to the sum
' of the house numbers which are greater
' than mine.   My house number comprises
' four digits. What is it? Is there more
' than one solution? If so, find all the
' others.
' By Dave Ellis.

' Declarations
declare PrintResult()
def myHseNr: double
def maxHseNr: int

' Screen SetUp
color 11, 0: cls
openconsole
print "Searching ...": print
print "My house   Last house": print
color 14, 0

' Initialisations
maxHseNr = 1001

' Main Routine
do
   myHseNr = sqrt(maxHseNr*(maxHseNr + 1)/2)
   if myHseNr = int(myHseNr): 'result!
    PrintResult(): 'print result
   endif
   maxHseNr = maxHseNr + 1: 'get next house nr
until maxHseNr > 9999

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

' +++ Subroutines and Functions +++

sub PrintResult
' pretty printer
print " ", myHseNr,
print space$(7), MaxHseNr
return



PROGRAM NOTES

Once you have the formula, the program almost writes itself. The Variable maxHseNr is iterated through the legal range for 4-digit integers, 1001 to 9999. Why doesn't it start at 1000? myHseNr is less than maxHseNr, and it's also a 4-digit number, so it can't be less 1,000. Therefore maxHseNr can't be less than 1,001.

For each value of maxHseNr the derived formula is used to extract myHseNr. Now, the nature of house numbers is that they must be integers. Mind you, for Jamaicans this isn't always true! Houses in Kingston sometimes have numbers such as 23½. However, assuming you don't live in such a place, an integer test is all that's needed on myHseNr to determine if it's a solution.

If the test if myHseNr = int(myHseNr) returns TRUE, the subroutine PrintResult() prints it to the computer screen in a formatted manner. Note: I originally made myHseNr a float type. This would ordinarily be good enough to capture square roots that aren't exact (that is, having a decimal component). However, one of them was so close that the decimal part was very small, and slipped through - house number 4552. This was picked up by Patrick Curteis of Sydney, Australia. Thanks, Patrick! Click here to see Patrick's input. I resolved the problem by making myHseNr a double type. This increases the decimal precision from single to double.

When the program is run, it generates the inset screen. There are two solutions.

Each solution depends on living in a different length street, always with house numbers up to four digits.