# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1182: Recurring decimals

From New Scientist #2338, 13th April 2002 [link]

Some fractions expressed as decimals consist of a decimal point followed immediately by a set of digits that recurs ad infinitum: for example 2/37 = 0.054054054…

In this example the digits that form the fraction and the recurring decimal are all different from each other, but there are only six of them (2, 3, 7, 0, 5, 4).

Your task is to find another fraction written in its simplest form that when expressed as a decimal consists of a decimal point followed immediately by a set of digits that recurs ad infinitum. The digits that form the fraction and the recurring decimal must all be different from each other and there must be nine of them.

What is the fraction?

[enigma1182]

### 16 responses to “Enigma 1182: Recurring decimals”

1. Jim Randell 1 February 2016 at 5:13 am

This Python program uses the recurring() function, which I wrote for Enigma 1247 and added to the enigma.py library. (I knew it would come in handy again!). It runs in 40ms.

```from itertools import count
from enigma import irange, gcd, recurring, printf

# generate d digit solutions
def generate(d):
# consider fractions of the form a/b, a < b
for b in count(1):
# b must have distinct digits
s1 = str(b)
ds1 = set(s1)
if len(ds1) != len(s1): continue

for a in irange(1, b - 1):
# a/b should be in lowest form
if gcd(a, b) != 1: continue
# a, b must have distinct digits
s2 = str(a)
ds2 = ds1.union(s2)
if len(ds2) != len(s1) + len(s2): continue
# compute the recurring decimal for a/b
(i, nr, rr) = recurring(a, b)
# there should be no non-recurring part
if nr: continue
# a, b, rr must have distinct digits
ds3 = ds2.union(rr)
n = len(ds3)
if n != len(s1) + len(s2) + len(rr): continue
# return solutions
if n == d: yield (a, b, rr)

# find a solution using 9 digits
for (a, b, rr) in generate(9):
printf("{a}/{b} = 0.({rr})...")
break
```

Solution: The fraction is 23/41.

23/41 = 0.(56097)…

This expression uses all the digits except 8.

• Jim Randell 1 February 2016 at 9:38 am

Here’s another solution (in Python 3), that uses a neat method for generating coprime pairs. It runs in 60ms.

```from enigma import recurring, printf

# generate coprime pairs (a, b), a < b
def coprime_pairs():
ps = [(1, 2), (1, 3)]
while True:
yield from ps
ps2 = list()
for (a, b) in ps:
ps2.extend([(b, 2 * b - a), (b, 2 * b + a), (a, 2 * a + b)])
ps = ps2

# generate d digit solutions
def generate(d):
for (a, b) in coprime_pairs():
# a and b must have no repeated digits
(s1, s2) = (str(a), str(b))
s = s1 + s2
ds1 = set(s)
if len(ds1) != len(s): continue

# compute the recurring decimal for a/b
(i, nr, rr) = recurring(a, b)
# there should be no non-recurring part
if nr: continue
# a, b, rr must have distinct digits
ds3 = ds1.union(rr)
n = len(ds3)
if n != len(s) + len(rr): continue
# return solutions
if n == d: yield (a, b, rr)

# find a solution using 9 digits
for (a, b, rr) in generate(9):
printf("{a}/{b} = 0.({rr})...")
break
```
2. Brian Gladman 1 February 2016 at 11:19 am
```from itertools import count

def find():
# search through increasing denominators
for den in count(1):
# ensure different digits in denominator
s_den = str(den)
if len(set(s_den)) == len(s_den):
# consider numerators that form a fraction
for num in range(1, den):

# ensure that all digits so far are different
s_num = str(num)
ln = len(s_num + s_den)
set_nd = set(int(x) for x in s_num + s_den)
if len(set_nd) == ln:

# now collect digits in the decimal representation
# of the fraction num / den looking for a total of
# nine different digits
digits, rem, cnt = set(), num, 0
while len(digits) == cnt and not digits & set_nd:
if ln + cnt == 9:
return num, den, cnt
dgt, rem = divmod(10 * rem, den)
cnt += 1
else:
continue

num, den, cnt = find()
s = '{:.12f}'.format(num / den)[:cnt + 2]
print('{}/{} = {}...'.format(num, den, s))
```
• Jim Randell 2 February 2016 at 10:59 am

I appreciate that your program does produce the answer, but is it really checking all the necessary conditions?

I don’t see where it ensures the fraction is in its lowest terms, and without this there are multiple solutions (fortunately the one with the lowest valued denominator appears first). Here’s the complete list (44 solutions, ordered by the value of the denominator. Only in the first one is the fraction in its lowest terms):

```23/41 = 0.(56097)...
9/63 = 0.(142857)...
364/518 = 0.(702)...
364/702 = 0.(518)...
798/1254 = 0.(63)...
48/1296 = 0.(037)...
390/1485 = 0.(26)...
930/1485 = 0.(62)...
459/1683 = 0.(27)...
976/2013 = 0.(48)...
1589/2043 = 0.(7)...
780/2145 = 0.(36)...
1869/2403 = 0.(7)...
806/2574 = 0.(31)...
1830/2745 = 0.(6)...
2098/3147 = 0.(6)...
594/3267 = 0.(18)...
218/3597 = 0.(06)...
460/3795 = 0.(12)...
1692/3807 = 0.(4)...
2790/4185 = 0.(6)...
792/4356 = 0.(18)...
3018/4527 = 0.(6)...
987/4653 = 0.(21)...
3190/4785 = 0.(6)...
1609/4827 = 0.(3)...
1694/5082 = 0.(3)...
946/5203 = 0.(18)...
318/5247 = 0.(06)...
689/5247 = 0.(13)...
4109/5283 = 0.(7)...
964/5302 = 0.(18)...
972/5346 = 0.(18)...
1809/5427 = 0.(3)...
1908/5724 = 0.(3)...
2058/6174 = 0.(3)...
780/6435 = 0.(12)...
3840/6912 = 0.(5)...
1564/7038 = 0.(2)...
3960/7128 = 0.(5)...
3980/7164 = 0.(5)...
482/7953 = 0.(06)...
6419/8253 = 0.(7)...
572/9438 = 0.(06)...
```

Also if I start the search for the denominator at 47 (instead of 1) I get a solution at 5/47, so is it really checking that there are the correct number of digits in the recurring part of the decimal, or just that there are at least enough digits?

• Brian Gladman 2 February 2016 at 4:16 pm

No, it doesn’t check all the conditions. A call to gcd would be needed for a general solution but a more serious issue is that I was lucky in the loop to detect the recurring decimal digits. This loop doesn’t detect the initial and recurring part of the decimal expansion for the general case.

• Brian Gladman 3 February 2016 at 2:00 pm

Here is a better version using the neat coprime generator that you found (a worthwhiloe addition to your library and my own).

```from itertools import count
from math import gcd
from sys import argv

def coprime_pairs():
ps = [(1, 2), (1, 3)]
while True:
yield from ps
ps = sum(([(n, 2 * n - m), (n, 2 * n + m),  (m, 2 * m + n),
] for m, n in ps), [])

def find(d):
# search through increasing denominators
for num, den in coprime_pairs():
# ensure different digits in denominator
s_den = str(den)
if len(set(s_den)) == len(s_den):
# ensure that all digits so far are different
s_num = str(num)
ln = len(s_num + s_den)
if ln > d - 1:
return
set_nd = set(int(x) for x in s_num + s_den)
if len(set_nd) == ln:
# now collect digits in the decimal representation
# of the fraction num / den looking for a total of
# nine different digits
rem, rems, dgts = num, [], set()
while rem and rem not in rems:
rems += [rem]
dgt, rem = divmod(10 * rem, den)
# exit as soon as we have duplicate or too many digits
if dgt in (dgts | set_nd) or len(dgts) > d - ln:
break
dgts.update([dgt])
else:
if rem and not rems.index(rem) and len(dgts) + ln == d:
yield num, den, len(dgts)

d = 9 if not argv[1] else int(argv[1])
for num, den, cnt in find(d):
s = '{:.12f}'.format(num / den)[:cnt + 2]
print('{}/{} = {}...'.format(num, den, s))
```

This runs exhaustively in about 20 seconds on the original problem and in about 5 minutes for a 10 digit search (giving no solutions). The only other solution I found was for 6 digits 8/37 = 0.216…

• Jim Randell 3 February 2016 at 3:46 pm

Yes, the only other solutions (for fractions in their lowest terms) have 6 different digits:

```2/37 = 0.(054)...
4/37 = 0.(108)...
8/37 = 0.(216)...
```

(There’s also a solution with 3 different digits: 2/3 = 0.(6)…).

• Brian Gladman 3 February 2016 at 4:33 pm

nteresting, I didn’t find those – there must be another bug somewhere 😦

• Brian Gladman 3 February 2016 at 4:48 pm

The outer loop termination condition is wrong because the order of the fractions delivered by the coprime generator is not monotonic. I wonder if there is a generator that can deliver them in such an order?

• Jim Randell 4 February 2016 at 7:20 am

I was using the technique described on this Wikipedia page [ https://en.wikipedia.org/wiki/Coprime_integers#Generating_all_coprime_pairs ], which will generate all coprime pairs, considered as fractions the later terms generally have larger denominators, but the ordering isn’t strict. The sequence is however exhaustive and non-redundant.

If we place a limit on the denominator we can use a Farey sequence [ https://en.wikipedia.org/wiki/Farey_sequence ] to generate fractions in numerical order:

```from enigma import printf

def farey(n):
(a, b, c, d) = (0, 1, 1, n)
while d > 1:
k = (n + b) // d
(a, b, c, d) = (c, d, k * c - a, k * d - b)
yield (a, b)

from sys import argv
N = (12 if len(argv) < 2 else int(argv[1]))

for (a, b) in farey(N):
printf("{a}/{b} = {f}", f=float(a) / float(b))
```
```% python farey.py 6
1/6 = 0.166666666667
1/5 = 0.2
1/4 = 0.25
1/3 = 0.333333333333
2/5 = 0.4
1/2 = 0.5
3/5 = 0.6
2/3 = 0.666666666667
3/4 = 0.75
4/5 = 0.8
5/6 = 0.833333333333
```
• Brian Gladman 4 February 2016 at 7:49 am

I also played with Farey sequences yesterday but using these naively with increasing n values involves a lot of duplication. I started looking at how to choose increasing but not consecutive n values to counter this but I didn’t get very far. I also looked at Stern-Brocot trees. Even though the original sequence is not ordered on denominators, I wonder if there is any way of knowing or detecting a position in the sequence(s) beyond which all denominators will not be less than a specified value.

• Jim Randell 4 February 2016 at 8:10 am

For any node (a, b) in the tree the child nodes are (b, 2b − a), (b, 2b + a), (a, 2a + b). In each case the denominator (second element) is strictly larger than b. So if we want to limit the denominator we can prune away nodes as soon as they exceed the limit.

This is the version that I included in enigma.py:

```def coprime_pairs(n=None):
fn = ((lambda p: p[1] <= n) if n else (lambda p: True))
ps = filter(fn, ((1, 2), (1, 3)))
while ps:
ps2 = list()
for (a, b) in ps:
yield (a, b)
ps2.extend(filter(fn, ((b, 2 * b - a), (a, 2 * a + b), (b, 2 * b + a))))
ps = ps2
```

Although if n is specified I think it is more computationally efficient to use the Farey sequence (given above).

• Jim Randell 4 February 2016 at 9:14 am

How about keeping the pairs in a heap rather than a list, then the pairs can be generated in “denominator” order:

```from heapq import heapify, heappop, heappush

def coprime_pairs(n=None):
fn = ((lambda p: p[0] <= n) if n else (lambda p: True))
ps = list(filter(fn, ((2, 1), (3, 1))))
heapify(ps)
while ps:
(b, a) = heappop(ps)
yield (a, b)
for p in ((2 * b - a, b), (2 * b + a, b), (2 * a + b, a)):
if fn(p): heappush(ps, p)
```
3. Brian Gladman 4 February 2016 at 11:56 am

Interesting solutions Jim, I will take a look at them. Thanks for looking at this – its certainly wothwhile to be able to generate coprime pairs easily.

• Brian Gladman 4 February 2016 at 12:12 pm

Generating in denominator order seems to cost around double when compared with just pruning. Nevertheless this is an attractive option.

• Jim Randell 4 February 2016 at 6:49 pm

FWIW: I generated the first 100 million coprime pairs using the heap based version. It took 22 minutes, and the Python process used up 9.4GB of memory.

Incidentally this kind of enumeration of the rational numbers allows you to show that the rationals are indeed a countable set.