# 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: 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
"""
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 * 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.

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