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

### Like this:

Like Loading...

This Python program uses the

recurring()function, which I wrote forEnigma 1247and added to theenigma.pylibrary. (I knew it would come in handy again!). It runs in 40ms.Solution:The fraction is 23/41.23/41 = 0.(56097)…

This expression uses all the digits except 8.

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

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

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?

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.

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

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…

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

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

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

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?

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:

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.

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 thanb. 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:Although if

nis specified I think it is more computationally efficient to use the Farey sequence (given above).How about keeping the pairs in a heap rather than a list, then the pairs can be generated in “denominator” order:

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.

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

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.