CODEWITHSUNDEEP
pythonpython-3.6fractionsrecurring
G.A.
G.A.

Reputation: 51

Calculate period length of recurring decimal fraction

I want to do a program in python (3.6.5) that tell the length of e.g. 1/7. The output should be for this example something like: "length: 6, repeated numbers: 142857". I got this so far:

n = int(input("numerator: "))
d = int(input("denominator: "))

def t(n, d):
    x = n * 9
    z = x
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1
        print ("length:", k)
        print ("repeated numbers:", t)

    return k, z / d

t(n, d)

Upvotes: 3

Views: 2698

Answers (2)

gcurse
gcurse

Reputation: 11

This is a rewritten Python Implementation of https://www.geeksforgeeks.org/find-recurring-sequence-fraction/

def repeating_sequence_of_fraction(numerator, denominator):
    """ This function returns the repeating sequence of a fraction.
        If a repeating sequence doesn't exit, then returns an empty string """

    # Create a map to store already seen remainders
    # remainder is used as key and its position in
    # result is stored as value. Note that we need
    # position for cases like 1/6.  In this case,
    # the recurring sequence doesn't start from first
    # remainder.
    result = ""
    mapping = {}

    # Find first remainder
    remainder = numerator % denominator

    # Keep finding remainder until either remainder
    # becomes 0 or repeats
    while remainder != 0 and remainder not in mapping:

        # Store this remainder
        mapping[remainder] = len(result)

        remainder = remainder * 10

        # Append remainder / denominator to result
        #result_part = int(remainder / denominator)
        result_part = remainder // denominator
        result += str(result_part)
        # print(f"Result: {result}")

        # Update remainder
        remainder = remainder % denominator
        # print(f"Map: {mapping}")

    # Return result
    if (remainder == 0):
        return ""
    else:
        return result[mapping[remainder]:]

if __name__ == '__main__':
    #result = repeating_sequence_of_fraction(1, 3)
    #result = repeating_sequence_of_fraction(9, 11)
    #result = repeating_sequence_of_fraction(7, 12)
    result = repeating_sequence_of_fraction(1, 7)
    #result = repeating_sequence_of_fraction(1, 81)
    #result = repeating_sequence_of_fraction(5, 74)
    if result == "":
        print("No repeating sequence")
    else:
        print(f"\nLenght of repeating sequence: {len(result)}")
        print(f"\nRepeating sequence is {result}\n")

Upvotes: 1

PM 2Ring
PM 2Ring

Reputation: 55499

Doing print ("repeated numbers:", t) prints the representation of the t function itself, not its output.

Here's a repaired version of your code. I use a Python 3.6+ f-string to convert the repeating digits to a string, and add zeros to the front to make it the correct length.

def find_period(n, d):
    z = x = n * 9
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1

    digits = f"{z // d:0{k}}"
    return k, digits

# Test

num, den = 1, 7
period, digits = find_period(num, den)
print('num:', num, 'den:', den, 'period:', period, 'digits:', digits)

num, den = 1, 17
period, digits = find_period(num, den)
print('num:', num, 'den:', den, 'period:', period, 'digits:', digits)

output

num: 1 den: 7 period: 6 digits: 142857
num: 1 den: 17 period: 16 digits: 0588235294117647

This line may be a bit mysterious:

f"{z // d:0{k}}"

It says: Find the largest integer less than or equal to z divided by d, convert it to a string, and pad it on the left with zeroes (if necessary) to give it a length of k.

As Goyo points out in the comments, this algorithm is not perfect. It gets stuck in a loop if the decimal contains any non-repeating part, that is, if the denominator has any factors of 2 or 5. See if you can figure out a way to deal with that.

Upvotes: 2

Related Questions