Problem 26: Reciprocal cycles

• 🔒 Problem
  • 🔐 Key Idea
• 🔑 Solution
  • 🧭 Initial idea
  • 🧮 Remainder method (from Mike Zubko in solution thread)

🔒 Problem

Find the value of $ d < 1000 $ for which $ 1 / d $ contains the longest recurring cycle in its decimal fraction part.

🔐 Key Idea

using the special relation between fraction and remainders

avoiding brute forcing using mathematical properties

🔑 Solution

🧭 Initial idea

$O(n^3)$ complexity.

Brute force through every possible patterns (repeating decimals) with string comparison and check whether the pattern is found multiple times in the decimals.

from decimal import Decimal as d, getcontext

getcontext().prec = 5000

def get_pattern(s):
    l = len(s)
    for start_pos in range(l):
        for pattern_length in range(1, l // 2 + 1):
            # maximum pattern length is l // 2 because of the precision limitation
            # can't determine whether it is repeating or not if it's longer than l // 2
            pattern = s[start_pos:start_pos + pattern_length]

            # print(f'\nstart_pos = {start_pos}, pattern = \'{pattern}\'')

            # compare the pattern to the rest of the string
            found = None

            for find_pos in range(start_pos + pattern_length, l, pattern_length):
                compare = s[find_pos:find_pos + pattern_length]

                # print(f'  comparing \'{pattern}\' and \'{compare}\'')

                if pattern != compare:
                    if found is not None and len(pattern) > len(compare):
                        # pattern does match but goes over the precision limit
                        found = pattern
                    else:
                        # pattern does not match
                        found = None
                        break
                else:
                    found = pattern
            
            if found is not None:
                found = pattern
                return found  # pattern match found
    
    # no pattern is found in the fraction
    return ''

max = [('', 0)]  # pattern, n (of 1/n)

for i in range(1, 1000):
    # d(1) / d(6) = 0.1666666666666666666666666667
    #                 └   string stored in f    ┘
    #           f = '166666666666666666666666666'
    # trim first 2 characters and last 1 character if exists
    f = str(d(1) / d(i))[2:-1]
    
    if len(f) < 20:
        continue  # not reciprocal

    result = get_pattern(f)
    
    if len(result) > len(max[0][0]):
        max = [(result, i, f)]
    elif len(result) == len(max[0][0]):
        max.append((result, i, f))

print(max[0][1])

983

Note: Python’s count() function could’ve been used in this case. No need to write a custom string comparator.

🧮 Remainder method (from Mike Zubko in solution thread)

$O(n^2)$ complexity. Key idea explained in Repeating decimal from Wikipedia.

It follows that any repeating decimal with period n, and k digits after the decimal point that do not belong to the repeating part, can be written as a (not necessarily reduced) fraction whose denominator is $ (10^n − 1)10^k $.

Conversely the period of the repeating decimal of a fraction $ c/d $ will be (at most) the smallest number n such that $ 10^n − 1 $ is divisible by $ d $.

For example, the fraction $ 2/7 $ has $ d = 7 $, and the smallest k that makes $ 10^k − 1 $ divisible by 7 is k = 6, because $ 999999 = 7 × 142857 $. The period of the fraction $ 2/7 $ is therefore 6.

Using the fact the problem only requires the period of the repeating decimal (length of the pattern), we can derive the period without calculating the actual decimals.

NOTE:Look for shortcuts to the answer. By finding the smallest p for the given i with the following code, we can efficiently calculate the period of the repeating decimal.

while p < i and (10 ** p) % i != 1:
    p += 1

n = 0  # the n with the longest period
max_period = 0

for i in range(1, 1000, 2):  # step of 2 to skip every even number
    if i % 5 != 0:  # skip every multiple of 5
        p = 1  # period for current i
        while p < i and (10 ** p) % i != 1:
            p += 1
        if p > max_period:
            max_period = p
            n = i

print(ans)

983