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]

Advertisements

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
    

    See also OEIS A001108, A001109, A001110.

  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))
    

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: