### Random Post

### Recent Posts

### Recent Comments

Jim Randell on Enigma 1691: Factory part… | |

Jim Randell on Puzzle 52: Football on the Isl… | |

geoffrounce on Enigma 1691: Factory part… | |

Hugh Casement on Enigma 1070: Time to work | |

Jim Randell on Enigma 1070: Time to work |

### Archives

### Categories

- article (11)
- enigma (1,157)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,808 hits

Advertisements

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.