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]

Advertisements

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
                digits.add(dgt)
              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.

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: