In my drive to optimize the performance of the Street Numbers problem solver, I had not taken the time to look at how others had attacked the problem. This was somewhat deliberate on my part, as I didn't want to 'peek at the answer' before having given it my best shot. But recently I came across the On-line Encyclopedia of Integer Sequences, a database put together by a group led by Neil Sloane, featuring a search box into which you can type a short sequence and ask for matching sequences from the database. Well I couldn't resist entering the first few street number solutions 1, 8, 49, 288, 1681, and was presented with not only the exact sequence I was after, but also enough notes and references to teach me something about the underlying mathematics.
For starters: the OEIS indexes the street number sequence as A001108 and the corresponding house number sequence as A001109. As I found out last time, the relation between these two hinges on a third sequence, what number theorists call square triangular numbers (OEIS ID A001110.) Each square triangular, t, is simultaneously 'square', because t equals the square of some integer h, and 'triangular' meaning that t equals the sum from 1 to some integer s. In the context of street numbers, street s is a solution, while the corresponding h represents the house located in s.
Theory aside, what I am most interested in is how the sequences are computed. It turns out that there are recurrence relations for determining any member of either sequence based simply on the 2 previous members. This fact relegates my solvers, relying as they do on laborious testing of successive natural numbers, to the category of brute force algorithms. Solving this problem by exhaustive search is just overkill.
According to the OEIS, the formula for the n-th street number is:
- s(n) = n, for n=0, n=1
- s(n) = 6*s(n-1) - s(n-2) + 2, for n>1
And for house numbers:
- h(n) = n, for n=0, n=1
- h(n) = 6*h(n-1) - h(n-2), for n>1
To round off, an implementation in Common Lisp:
;; Returns a list of the first HOW-MANY solutions to Street
;; Numbers, of the form (HOUSE STREET).
(DEFUN STREET-NUMBER-SOLUTIONS (&OPTIONAL (HOW-MANY 20))
(DO ((SOLUTIONS (LIST) (CONS (LIST H S) SOLUTIONS))
(H 1 (- (* 6 H) H-1))
(S 1 (- (* 6 S) S-1 -2))
(H-1 0 H)
(S-1 0 S))
((MINUSP (DECF HOW-MANY))
(NREVERSE SOLUTIONS))))
