Search code examples
mathfractions

Determine x/y fraction has repeating decimal expansion

Is there any quick method to determine that x/y fraction based only on integers giving in result repeating part in the end? Thank you.

def repeatless(x, y):
    // some code here...
    return True
Solution

  • Given integers x and y, the fraction x/y has a repeating decimal expansion if and only if:

    1. y / gcd(x, y) has factors other than 2 and 5, and
    2. the remainder after dividing x by y is not zero

    NOTE: as pointed out in the comments, my original answer had a flaw in that it only worked if x/y was an irreducible fraction (in lowest terms). This is remedied by first dividing y by gcd(x, y) so that you're checking whether the denominator of the equivalent irreducible fraction has factors other than powers of 2 and 5.

    The second condition is pretty easy to check:

    HasRepeatingDecimal(x, y)
1. if x % y == 0 then return false

    Now we need to see if y / gcd(x, y) has factors other than 2 and 5. We can do this by repeatedly dividing y / gcd(x, y) by 5 and then by 2 and see if we end up with the number 1:

    HasRepeatingDecimal(x, y)
1. if x % y == 0 then return false
2. y = y / gcd(x, y)
3. while (y % 5 == 0) y = y / 5
4. while (y % 2 == 0) y = y / 2
5. if y == 1 then return true else return false

    The reason you can check the denominator's divisibility by 2 and 5 is that the decimal system has base 10 and 2 and 5 are the only prime factors of 10. If you were using base-21, you'd check for y / gcd(x, y) being of the form 3^a x 7^b instead.