Enigmatic Code

Programming Enigma Puzzles

Enigma 1142: Policies with strings

From New Scientist #2298, 7th July 2001 [link]

Harry used to work for Smallprint, Wriggle, and Payless, a large insurance company. He recalls that every policy number (including some with leading “0”s) had the same number of digits, which was fewer than 20.

He also recalls being passed a neat list of the numbers of five policies for review, and being astonished to find that each number below the first on the list had exactly twice the value of the one above it, and could be obtained from the number above it merely by moving the last digit of that number to its front.

What was the bottom number on his list of five numbers?

[enigma1142]

Advertisements

2 responses to “Enigma 1142: Policies with strings

  1. Jim Randell 7 November 2016 at 6:43 am

    I assumed the policy numbers are all different, otherwise the policy with a value of 0 could just be repeated five times to form the list.

    The following Python program generates a sequence of numbers where each is N times the previous number, and this process is repeated K times. For this puzzle we use N = 2, K = 4. It runs in 44ms.

    from enigma import irange, arg, printf
    
    # generate numbers (as a sequence of digits) of the form:
    #   [d0, d1, ..., dk-1, dk]
    # such that when the number is multipled by <n> the result is:
    #   [dk, d0, d1, ..., dk-1]
    def generate(n, base=10):
      for d in irange(0, base - 1):
        (s, a, c) = ([], d, 0)
        while True:
          s.insert(0, a)
          (c, b) = divmod(a * n + c, base)
          if c == 0 and b == d:
            yield s
            break
          a = b
    
    # rotate (circular shift) right
    def ror(s, n=1):
      return s[-n:] + s[:-n]
    
    # multiply sequence <s> by <n>
    def mul(s, n, base=10):
      (r, c) = ([], 0)
      for a in s[::-1]:
        (c, b) = divmod(a * n + c, base)
        r.insert(0, b)
      if c: r.insert(0, c)
      return r
    
    # check rotate <s> multiplies by <n>, <k> times
    def check(s, n, k):
      r = [s]
      for i in irange(1, k):
        a = ror(r[-1])
        b = mul(r[-1], n)
        if a != b: return None
        r.append(a)
      return r
    
    # multiply by N, K times
    N = arg(2, 0, int)
    K = arg(4, 1, int)
    
    # start the sequence off
    for s0 in generate(N):
      # we need to make K + 1 different cyclic permutations
      if len(s0) < K + 1: continue
      # check we can multiply by N, K times
      ss = check(s0, N, K)
      if ss is None: continue
      # print the sequence of numbers
      printf("{n} digits", n=len(s0))
      for (i, s) in enumerate(ss):
        printf("s[{i}] = {s}")
      printf()
    

    Solution: The last number on the list was 842105263157894736.

    The policy numbers are all 18 digits long. The five policy numbers are:

    052631578947368421
    105263157894736842
    210526315789473684
    421052631578947368
    842105263157894736

    Additional solutions occur for longer policy numbers that are repeats of the numbers above. So, the next smallest solution occurs with policy numbers that are 36 digits long:

    052631578947368421 052631578947368421
    105263157894736842 105263157894736842
    210526315789473684 210526315789473684
    421052631578947368 421052631578947368
    842105263157894736 842105263157894736

    Considered as the digits after a decimal point these numbers correspond to the recurring portion of the fractions 1/19, 2/19, 4/19, 8/19, 16/19.

  2. arthurvause 8 November 2016 at 8:41 am

    I started off with some algebraic analysis with the intention of writing some code to solve the problem, but ended up solving the problem completely with algebra:

    If the policies have N digits, suppose p=10x+y is one of the first four policies, where y is a single digit, then
    2(10x+y) = 10^{N-1}y + x

    so x= \frac{(10^{N-1} -2)}{19}y
    and p = \frac{(10^N-1)}{19}y,
    So 10^N=1 mod 19.
    If N<20, then N=18, i.e. the multiplicative order of 10 mod 19
    (http://oeis.org/A084680)
    The fifth policy is therefore (10^{18}-1)\frac{16}{19} = 842,105,263,157,894,736

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: