# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1140: A long, long road

From New Scientist #2296, 23rd June 2001 [link]

George lives in a long road in which the houses are numbered from one with no numbers missing. He has calculated that the total of all the house numbers less than his is equal to the total of all the house numbers greater than his.

George’s brothers, Dave, Ernest and Fred, live in shorter roads than George, but they can each make the same claim regarding house numbers. The brothers’ four house numbers have different numbers of digits.

Hearing this story, George’s drinking friend scribbled on a beer mat for a while, then he asked: “George, does your road have nearly 10,000 houses?”

“No, not nearly that many,” George replied.

How many houses are there in total in the four roads? And what answer would the man in the pub have given to that question before being corrected?

[enigma1140]

### 2 responses to “Enigma 1140: A long, long road”

1. Jim Randell 21 November 2016 at 8:38 am

This Python program calculates possible (n, m) pairs where n is the number of houses in the street, and m is the “triangular median” – i.e. the house number where the sum of all house numbers lower than m is equal to the sum of all house numbers higher than m. It runs in 63ms.

```from enigma import irange, tri, is_triangular, printf

# suppose joe lives at number m
for m in irange(1, 10000):
# sum of the numbers below joes
s = tri(m - 1)
# so the sum of all the houses in the street is...
t = m + 2 * s
n = is_triangular(t)
if n is None: continue

printf("m={m} s={s} t={t} n={n}")
```

Solution: The total number of houses in all four streets is 2026. The man in the pub would have given the answer 10145, before being corrected (assuming he had come up with a viable solution).

The number of houses in the four streets are: 8, 49, 288, 1681. The final value is the number of houses in George’s street.

The corresponding “triangular medians” are: 6, 35, 204, 1189, so George lives in house 1189 of 1681.

The next largest number of houses in a street is 9800 (“nearly 10,000”), with a triangular median of 6930.

After that the next largest number of houses is 57121, with a triangular median of 40391.

If there are n houses in the street and the triangular median is m then we have:

T(m − 1) = T(n) − T(m)

Which simplifies to:

m² = n(n + 1)/2 = T(n)

So we are interested in triangular numbers that are also square, see [ https://en.wikipedia.org/wiki/Square_triangular_number ], which can be generated as follows:

ST[0] = 0
ST[1] = 1
ST[k + 2] = 34 × ST[k + 1] − ST[k] + 2

The sequence N[] where ST[k] = T(N[k]) (i.e. ST[k] is the N[k]th triangular number) can be generated as follows:

N[0] = 0
N[1] = 1
N[k + 2] = 6 × N[k + 1] − N[k] + 2

The sequence M[] where ST[k] = M[k]² (i.e. ST[k] is the M[k]th square number) can be generated as follows:

M[0] = 0
M[1] = 1
M[k + 2] = 6 × M[k + 1] − M[k]

The following Python program will generate as many (n, m) pairs as you like (the number can be specified on the command line) such that m² = T(n).

```from enigma import arg, printf

# generate (m, n) such that m^2 = T(n)
def generate():
(n0, n1) = (0, 1)
(m0, m1) = (0, 1)
yield (m0, n0)
while True:
yield (m1, n1)
(n0, n1) = (n1, 6 * n1 - n0 + 2)
(m0, m1) = (m1, 6 * m1 - m0)

N = arg(8, 0, int) - 1

for (k, (m, n)) in enumerate(generate()):
assert 2 * m * m == n * n + n
printf("[k={k}] n={n} m={m}")
if not(k < N): break
```

The default is to generate the first 8 elements of the sequence, which is sufficient to solve this problem:

```% python enigma1140b.py
[k=0] n=0 m=0
[k=1] n=1 m=1
[k=2] n=8 m=6
[k=3] n=49 m=35
[k=4] n=288 m=204
[k=5] n=1681 m=1189
[k=6] n=9800 m=6930
[k=7] n=57121 m=40391
```

2. Brian Gladman 21 November 2016 at 3:55 pm

A solution using my number theory library:

```from collections import defaultdict
from itertools import combinations, product
from number_theory import Qde

# Let the person's house number be n in a street with N houses.  We
# then have n.(n - 1) / 2 = N.(N + 1) / 2 - n.(n + 1) / 2, giving:
#
#   (2N + 1)^2 - 8.n^2 = 1
#
# which is known as a Quadratic Diophantine Equation (QDE)

# map the brother's house number lengths to lists of QDE solutions
n2s = defaultdict(list)
for x, y in Qde(8, 1).solve(limit=8):
if x > 1:
n2s[len(str(y))].append((y, x // 2))

# for storing solutions
sol = []
# select four different lengths for the brother's house numbers
for n4 in combinations(n2s.keys(), 4):
# and compose solutions for these lengths
for s4 in product(*(n2s[n] for n in n4)):
tot = sum(x[1] for x in s4)
sol.append((tot, s4))

# output solutions in order of increasing house totals
for t, s in sorted(sol):
print('Total {}, (<house> in <houses>)[4]: {}'.format(t, s))
```