I believe what is wrong is that you should only be checking if the number of decimal places previously seen is the number of the length of the cycle and it was seen just previous to this length.
I think the best way to do this would be to use some good ol' math.
Lets try and devise a way to find the decimal representation of fractions and how to know when there will be repeating decimals.
The best way to know if a fraction will terminate (or repeat) is to look at the factorization (hard problem) of the denominator.
There are many ways to find the factorization, but what we really want to know is, does this number have a prime factor other than 2 or 5. Why? Well a decimal expansion is just some number a / 10 * b. maybe 1/2 = .5 = 5/10. 1/20 = .05 = 5/100. etc.
So the factors of 10 are 2 and 5, so we want to find out if it has any other factors other than 2 and 5. Perfect, thats easy, just keep dividing by 2 until it is not divisible by 2 anymore, than do the same with 5. Or the other way around.
First we may want to find out if it is divisible by 2 or 5 before we start doing some serious work.
def div_by_a_or_b( a, b, number):
return not ( number % a ) or not ( number % b )
Then we divide out all the fives then all the twos and check if the number is 1
def powers_of_only_2_or_5(number):
numbers_to_check = [ 2, 5 ]
for n in numbers_to_check:
while not number % n: # while it is still divisible by n
number = number // n # divide it by n
return number == 1 # if it is 1 then it was only divisble by the numbers in numbers_to_check
I made this a bit more polymorphic so you can change this around if you want to change the base. (all you need is the factors of that base, for instance in base 14 you check 2 and 7 instead of 2 and 5)
Now all thats left to do is find out what we do in the case of non-terminating/repeating fractions.
Now this is super number theory filled, so i'll leave you with the algorithm and let you decide if you want to find out more on mathforum.org or wolfram alpha
Now that we can easily tell if a fraction will terminate and if not, what will be the length of its cycle of repeating digits. Now all thats left to do is find the cycle or how many digits it will start in.
In my search for an efficient algorithm, I found this post on https://softwareengineering.stackexchange.com/ which should be helpful.
some great insight - "When a rational number m/n with (m,n)=1 is expanded, the period begins after s terms and has length t, where s and t are the smallest numbers satisfying
10^s=10^(s+t) (mod n). "
So all we need to do is find s and t:
def length_of_cycle(denominator):
mods = {}
for i in range(denominator):
key = 10**i % denominator
if key in mods:
return [ mods[key], i ]
else:
mods[ key ] = i
Let's generate the numbers of the expansion
def expasionGenerator( numerator, denominator ):
while numerator:
yield numerator // denominator
numerator = ( numerator % denominator ) * 10
Now be careful about using this as it will create an infinite loop in a repeating expansion (as it should ).
Now I think we have all the tools in place to write our function:
def the_expansion( numerator, denominator ):
# will return a list of two elements, the first is the expansion
# the second is the repeating digits afterwards
# the first element's first
integer_part = [ numerator // denominator ]
numerator %= denominator
if div_by_a_or_b( 2, 5, denominator ) and powers_of_only_2_or_5( denominator ):
return [ integer_part, [ n for n in expasionGenerator( numerator, denominator ) ][1:], [0] ]
# if it is not, then it is repeating
from itertools import islice
length_of_cycle = cycleLength( denominator )
generator = expasionGenerator( numerator*10, denominator )
# multiply by 10 since we want to skip the parts before the decimal place
list_of_expansion = [ n for n in islice(generator, length_of_cycle[0]) ]
list_of_repeating = [ n for n in islice(generator, length_of_cycle[1]) ]
return [ integer_part, list_of_expansion, list_of_repeating ]
Now all thats left is to print it, that shouldn't be too bad. I am just going to build a function first that takes a list of numbers to a string:
def listOfNumbersToString(the_list):
string = ""
for n in the_list:
string += str(n)
return string
Then create the convert function:
def convert(numerator, denominator):
expansion = the_expansion(numerator,denominator)
expansion = [ listOfNumbersToString(ex) for ex in expansion ]
return expansion[0] + "." + expansion[1] + "(" + expansion[2] + ")"
interesting read on the topic at http://thestarman.pcministry.com/ and a similar-ish question on stackoverflow
