The previous algorithm I wrote for the Street Numbers problem was unable to decide, in a constant number of steps, whether a given street number contained a solution (house.) It needed to amble down the street for some distance before being able to tell for sure, and this distance would increase for higher street numbers. So the program for displaying solutions had a running time that increased worse than linearly in relation to the number of streets tested.
However, rethinking the problem from first principles can help to uncover a linear time procedure — the straight route alluded to in the title.
What makes a certain house h a solution in street s is that houses on either side of it sum to the same total. This statement can be written in the form of an equation (using the notation Sum(1, h-1) to mean the sum of integers from 1 to h-1):
Sum(1, h-1) = Sum(h+1, s)
Solutions to Street Numbers are those pairs of h and s that satisfy the equation. What I'm trying to do is define a procedure to determine the value of h, if it exists, that can pair up with a known s. That is, to define h as a function of s, or if you like to solve for h. To begin with, rewrite the right side:
Sum(1, h-1) = Sum(1, s) - Sum(1, h)
Sum(1, h) + Sum(1, h-1) = Sum(1, s)
h + 2*Sum(1, h-1) = Sum(1, s)
Continue by expanding the left side using Gauss' formula seen earlier, giving:
h + h*(h-1) = Sum(1, s)
h*h = Sum(1, s)
h = Root(s*(s+1)/2)
The result says that a street s will contain a solution provided the square root of the sum from 1 to s is an integer, with said root being the solution.
It's time to cut some code, people:
;; Interactively display solutions to Street Numbers.
;; Version 3.
(DEFUN SOLVE-STREET-NUMBERS ()
(DO* ((S 1 (1+ S))
(SUM 1 (TRUNCATE (* S (1+ S)) 2))
(H 1 (ISQRT SUM)))
((AND (= SUM (* H H))
(PROGN
(FORMAT T "~&Street ~A, House ~A" S H)
(NOT (Y-OR-N-P "~&More?")))))))
Joy! I get the first 11 solutions out of this within a minute on my system, quite a pleasing improvement over the 7 of last time.
