Enigmatic Code

Programming Enigma Puzzles

Enigma 375: Miles out

From New Scientist #1524, 4th September 1986 [link]

A French friend had a road journey to make from London and he knew the shortest distance in miles, so he wanted to know what fraction to multiply by to make it into kilometres.

“Just multiply by 2.”
“No, 3/2 is better.”
“No, 5/3 is more accurate.”
“No, 8/5 is more usual.”

Those were the suggestions made to him and each would have led him to calculate the distance as a whole number of kilometres.

The suggested fractions were, by chance, all obtained by taking a pair of successive terms in the well-known sequence 1, 2, 3, 5, 8, … where new terms are calculated by adding the two previous terms. This led me, knowing that one mile is 1.60934 kilometres, to calculate which pair of successive terms of the sequence would give the best fraction to use. I reported my findings to my French friend and this fraction, too, led him to calculate his distance as a whole number of kilometres.

How far, in miles, was his journey?

[enigma375]

Advertisements

2 responses to “Enigma 375: Miles out

  1. Jim Randell 16 December 2016 at 7:59 am

    This code checks the first 100 terms of the Fibonacci sequence. It runs in 62ms.

    from fractions import Fraction as F
    from enigma import first, lcm, printf
    
    # generate successive terms in a fibonacci sequence
    def fib(a, b):
      while True:
        yield (a, b)
        (a, b) = (b, a + b)
    
    # 1 mile = (160934 / 100000) km
    t = F(160934, 100000)
    
    # find the closest approximation
    d = F(999, 1)
    for (a, b) in first(fib(1, 2), 100):
      f = F(b, a)
      r = abs(t - f)
      if r < d:
        x = lcm(30, f.denominator)
        printf("fraction = {f}, distance is multiple of {x}")
        d = r
    

    Solution: The distance is 390 miles.

    Actually any multiple of 390 miles works, but it is hard to make a continuous road trip of more than about 700 miles from London without taking a somewhat indirect route, so we use the shortest possible distance.

    The question defines the ratio of one mile to one kilometre as 1.60934 = 80467/50000, but the puzzle also works if we use the actual value of 1.609344 = 25146/15625.

    The best approximation occurs at 21/13, which occurs at indices 7 and 8 in the standard Fibonacci sequence (indexed from 0), (0, 1, 1, 2, 3, 5, 8, 13, 21, …).

    The limit of the ratio of successive terms of the Fibonacci sequence is the Golden Ratio = φ = (1 + √5)/2 ≈ 1.618… so there won’t be a better solution by considering further terms in the sequence.

  2. Hugh Casement 16 December 2016 at 8:23 am

    If we don’t confine ourselves to terms in the Fibonacci sequence, then successive improvements to 21/13 are 29/18, 37/23, 66/41, 103/64, 449/279, 552/343, 655/407, 758/471, 861/535, and 1619/1006 which is good for six digits after the decimal point.

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: