Enigmatic Code

Programming Enigma Puzzles

Enigma 1247: Recurring decimal

From New Scientist #2403, 12th July 2003 [link]

George has written down a proper fraction whose numerator and denominator each have four digits, and has calculated the corresponding decimal fraction, thus:

Enigma 1247

All the digits of the fraction and its decimal equivalent have been replaced by # marks. Moreover, the bar over the decimal expression indicates that its value comprises one decimal digit that is followed by a recurring decimal with a seven-digit cycle.

The numerator, the denominator and the non-recurring decimal digit include nine different digits.

If the numerator is a prime, what are the seven digits under the bar?

[enigma1247]

8 responses to “Enigma 1247: Recurring decimal

  1. Jim Randell 20 March 2015 at 6:36 am

    I thought I’d write a generic routine for calculating recurring decimals (although I may have gone a bit over the top with the “base” argument – for example 5/17 = 0.(4B)… as a recurring hexadecimal).

    This Python program runs in 303ms.

    from itertools import permutations
    from enigma import int2base, Primes, irange, concat, printf
    
    # find recurring decimal representation of <a> / <b>
    # return strings (<integer-part>, <non-recurring-decimal-part>, <recurring-decimal-part>)
    # if you want rationals that normally terminate represented as non-terminating set <recur>
    def recurring(a, b, recur=False, base=10):
      # the integer part
      (i, a) = divmod(a, b)
      if recur and a == 0: (i, a) = (i - 1, b)
      # record dividends
      r = dict()
      s = ''
      n = 0
      while True:
        try:
          # have we had this dividend before?
          j = r[a]
          return (int2base(i, base), s[:j], s[j:])
        except KeyError:
          # no, we haven't
          r[a] = n
          n += 1
          (d, a) = divmod(base * a, b)
          if recur and a == 0: (d, a) = (d - 1, b)
          if not(d == a == 0):
            # add to the digit string
            s += int2base(d, base)
    
    
    # x / y = 0 . a (bcdefgh...)
    
    digits = set('0123456789')
    
    # x is a 4 digit prime composed of different digits
    for x in Primes(9876).range(1023, 9876):
      s1 = set(str(x))
      if len(s1) != 4: continue
    
      # y is a larger 4 digit number composed from 4 of the remaining digits
      for s2 in permutations(digits.difference(s1), 4):
        y = int(concat(*s2))
        if not(x < y): continue
    
        # z = 99999990 x / y = abcdefgh - a
        (z, m) = divmod(99999990 * x, y)
        if m > 0: continue
    
        # a is the leading digit of z
        a = str(z // 10000000)
        # and does not occur in x or y
        if a in s1 or a in s2: continue
    
        # find x/y as a recurring decimal
        (i, nr, rr) = recurring(x, y)
        # is it the right shape?
        if not(len(nr) == 1 and len(rr) == 7): continue    
    
        printf("{x} / {y} = {i}.{nr}({rr})...")
    

    Solution: The seven digits in the recurring part of the decimal are 2217573.

    The full expression for the solution is (with the repeating section in brackets):

    1487 / 2390 = 0.6(2217573)…

    If we allow non-canonical recurring decimals we could claim that the following are also solutions:

    1609 / 4827 = 0.3(3333333)…, but we would normally write this as 0.(3)…

    3079 / 6158 = 0.4(9999999)…, but we would normally write this as 0.5.

  2. Naim Uygun 20 March 2015 at 10:26 am
    def prime(n):   
        if n<2: return 0
        if n in [2,3,5,7]: return 1
        r=int(n**0.5)+2
        for i in range(2,r):
            if n%i==0: return 0
        return 1
    
    from decimal import Decimal
    p=[i for i in range(1001,9999,2) if prime(i)==1]
    for a in p:
        for i in range(a+1,9999):        
          q,r=divmod(a,i)     
          f=10*r/i
          d=int(f)     
          s=str(a)+str(i)+str(d)
          u=len(set(s))
          if u != 9 : continue
          m=str(Decimal.from_float(f))
          t1=m[2:9]
          if len(t1) != 7: continue
          if len(set(t1)) ==1 : continue
          t2=m[9:16]
          if t1 != t2: continue      
          print("Prime=",a,"denominator=",i,"digit=",d,"repetead part=",t1)
          """
            Output:
            Prime= 1487 denominator= 2390 digit= 6 repetead part= 2217573       
          """
    

    Hi Jim,
    It seems there is no answer for this question,
    because, the repeated part repeats only 2 times.
    The division 1487/2390 gives 0.6_2217573_2217573_251858766525401733815670013427734375

    • Jim Randell 20 March 2015 at 11:10 am

      You’ll never get an exact representation for an infinitely recurring decimal expansion using the Python decimal module (or float). Although you can increase the precision of Decimal (default is 28 decimal places) to get a more accurate approximation.

  3. Paul 20 March 2015 at 12:37 pm

    MMa Code

    Timing[a=Cases[IntegerDigits/@Prime[Range[172,1218]],{a_,b_,c_,d_}/;a!=b!=c!=d];
    Do[b=Complement[{1,0,2,3,4,5,6,7,8,9},a[[q]]];
    c=Select[Select[FromDigits/@Permutations[b,{4}],IntegerLength[#]==4&],#>FromDigits[a[[q]]]&];Do[d=ToString[N[FromDigits[a[[q]]]/c[[w]],16]];e=StringTake[d,{4,10}];f=StringTake[d,{11,17}];g=FromDigits[StringTake[d,{3}]];If[e==f&&Length[Intersection[Join[a[[q]],IntegerDigits[c[[w]]]],{g}]]==0,
    Print[FromDigits[a[[q]]]," , ",c[[w]]," , ",FromDigits[a[[q]]]/c[[w]]," , ",d]],
    {w,1,Length[c]}],{q,1,Length[a]}]]
    1487 , 2390 , 1487/2390 , 0.6221757322175732
    1609 , 4827 , 1/3 , 0.3333333333333333
    2069 , 4138 , 1/2 , 0.5000000000000000
    2309 , 4618 , 1/2 , 0.5000000000000000
    3209 , 6418 , 1/2 , 0.5000000000000000
    {1.544410, Null}
    

    3079 / 6158 = 1/2 exactly and so shouldn’t get on the list as it already has a 5 in the denominator, rounding errors again. to 50 DP.
    1487/2390 = 62217573221757322175732217573221757322175732217573221757322175732217573221757

    One of the things I like about MMa is you don’t have to worry about any accuracy. I knew I needed to work to 16 dp for this, so set the 16 in this part of code d=ToString[N[FromDigits[a[[q]]]/c[[w]],16]]; it could have easily been 100 or 1000, at 100 dp the timing was 1.82 and at 1000 it went up to 4.2

    Paul.

    • Paul 20 March 2015 at 1:09 pm

      while we are talking timings, I tend to forget one other great aspect of MMA, it’s scalability. I can wrap round the whole code one word ‘Parallelize’ and the above program ran in
      {0.046800, Null}. My licence is only for 4 cores, but there is no limit to how many cores it can use.
      Paul.

  4. Brian Gladman 20 March 2015 at 2:19 pm

    This one runs in 51ms using shell based timing (9ms using profile).

    from number_theory import divisors, Primes
    
    # We have with t = top, b = bottom and M = 10 ** 7 - 1:
    #
    #   t / b = u * 10 **-1 + v * 10 **-8 / (1 - 10 **-7)
    #   10 * t / b = u + v  / (10 ** 7 - 1)
    #   10 * M * t = (M * u + v) * b
    #
    # Hence bottom is a four digit divisor of 10 * M 
    
    M = 10 ** 7 - 1
    # four digit values without duplicate digits for the bottom
    b_values = {x:frozenset(int(y) for y in str(x)) 
                  for x in divisors(10 * M) if 1000 <= x <= 10000}
    b_values = {x:y for x, y in b_values.items() if len(y) == 4}
    
    # select a value for the bottom
    for bottom, b_digits in b_values.items():
      # select a four digit prime value for the top
      for top in Primes().generate(1000, bottom):
        # only consider primes without duplicate digits
        # and without any of the digits in bottom
        t_digits = set(int(x) for x in str(top))
        if len(t_digits) == 4 and not t_digits & b_digits:
          tb_digits = t_digits | b_digits
          # now compute the non-recurring digit and the
          # seven digit recurring sequence 
          u, v = divmod(10 * M * top // bottom, M)
          # and check that the single diigit is not in top or bottom
          if u < 10 and not tb_digits.intersection([u]):
            print('{} / {} == 0.{}({})...'.format(top, bottom, u, v))
    
  5. saracogluahmet 20 March 2015 at 4:01 pm

    I have used the general division technique. This is not so fast, its execution time on my machine is almost 450 miliseconds. If I want faster one, I would rather use C++.

    
    
    from prime import Isprime
    
    def FindRecurring(diff,denominator,strtimes):
        Numerator=diff*10
        times=(Numerator)//denominator
        diff=Numerator-(times*denominator)
        strtimes=strtimes+str(times)
    
        return diff,strtimes
    
    def Solve():
        for numerator in range(1000,10000):
            if Isprime(numerator):
                strnumerator=str(numerator)
                digits=set(strnumerator)
    
                if len(digits)==len(strnumerator):
                    for denominator in range(numerator+1,10000):
                        strdenominator=str(denominator)
                        digits1=set(str(denominator))
                        if len(set(strdenominator))==len(strdenominator):
                            if len(set.intersection(digits,digits1))==0:
                                
                                Numerator=numerator*10
                                times=(Numerator)//denominator
                                settimes=set(str(times))
                            
                                if len(set.intersection(digits,settimes))==len(set.intersection(digits1,settimes))==0:
                                #print(numerator,denominator,times)
                                    diff=Numerator-(times*denominator)
                                    strtimes=''
                                    
                                    for j in range(7):
                                        diff,strtimes=FindRecurring(diff,denominator,strtimes)
                                        
    
                                    for j in range(7,14):
                                         
                                         diff,strtimes=FindRecurring(diff,denominator,strtimes)
                                         for k in range(7,j):
                                             if strtimes[7-k]!=strtimes[k]:
                                                 break
                                        
                                           
                                    if strtimes[0:7]==strtimes[7:14]:
                                        print("Found=",numerator,denominator,strtimes)
                                        return
    Solve()
    
    
  6. Jim Randell 22 March 2015 at 10:30 am

    Here is an alternative version of my code, that uses the observation that y divides 99999990x, and x is prime. So y is either a 4-digit multiple of x (and the only 1-digit multipliers that are also divisors of 99999990 are 2, 3, 5, 6, 9), or y is a 4-digit divisor of 99999990 (and it must consist of 4-different digits, so the only candidates are 2390 and 4302).

    Note that if y is a multiple of x, then the fraction is not in its lowest terms, but the puzzle doesn’t explicitly state that it is. It says it is a “proper” fraction, which technically just means that x < y.

    It also doesn't need the full power of the generic [[ recurring() ]] function from my original program (which is a shame, because it was a fun bit of code to write). Once we have the 7-digit recurring part of the decimal, as 7 is prime we know that if the recurring part includes multiple whole repeats then it must be 7 repeats of a 1-digit cycle, so we can just test for that.

    This code runs in 42ms.

    from enigma import int2base, base2int, Primes, concat, irange, printf
    
    # x / y = 0 . a (bcdefgh...)
        
    digits = set('0123456789')
    
    # x is a 4 digit prime composed of different digits
    for x in Primes(9876).range(1023, 9876):
      s1 = set(int2base(x))
      if len(s1) != 4: continue
    
      # generate (<y>, <s2>) pairs, where <y> is a possible denominator
      # and <s2> is the set of distinct digits in <x> and <y>
      # candidates are passed in as sequences of increasing numbers
      def denominator(*args):
        seen = dict()
        for ys in args:
          for y in ys:
            # check y is allowable
            if not(x < y < 10000): break
    
            # check y is new
            if y in seen: continue
            seen[y] = 1
    
            # check digits in x and y are distinct
            s2 = s1.union(int2base(y))
            if len(s2) != 8: continue
    
            yield (y, s2)
    
      # y is a 4-digit multiple of 99999990 or a 4 digit multiple of x
      # composed of different digits
      # the only possible 4-digit divisors of 99999990 are 2390 and 4302
      # the only possible 1-digit divisors of 99999990 are 2, 3, 5, 6, 9
      for (y, s2) in denominator((2390, 4302), (i * x for i in (2, 3, 5, 6, 9))):
    
        # calculate the digit a, which should not be in x or y
        a = (10 * x - 1) // y
        if int2base(a) in s2: continue
    
        # calculate the recurring part (as a 7-digit string)
        r = int2base((99999990 * x) // y - 9999999 * a).zfill(7)
    
        # 7 is prime, so we only need to weed out single digit repeats
        if r == r[0] * 7: continue
    
        printf("{x} / {y} = 0.{a}({r})... [= {f}]", f=float(x) / float(y))
    

    Like my previous program all the computation takes place using integers, so there is no dependence on any fixed or floating point implementation.

    If you remove the final check (line 46) you see that the candidate solutions are the same as my first program finds:

    1487 / 2390 = 0.6(2217573)…
    1609 / 4827 = 0.3(3333333)…
    3079 / 6158 = 0.4(9999999)…

    It doesn’t produce the additional candidates that Paul’s Mathematica program finds:

    2069 / 4138 = 0.5(0000000)…
    2309 / 4618 = 0.5(0000000)…
    3209 / 6418 = 0.5(0000000)…

    because in the convention I am using 0.5(0)… is not the non-terminating decimal representation of 1/2. Rather it is 1/2 = 0.4(9)…, and these three solutions already use the digit 4 in the denominator and so are disallowed.

    If you want to allow 0.5(0)… as the valid representation of 1/2 you can remove the [[ - 1 ]] in line 39.

    If you want to see more decimal places in the decimal representation of the solution you can use the Python [[ Decimal() ]] class, and set [[ f = Decimal(x) / Decimal(y) ]] in line 48.

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 )

Connecting to %s

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

%d bloggers like this: