# 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]

### 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$

This site uses Akismet to reduce spam. Learn how your comment data is processed.