Project Euler problem 26 in Python

Question

Question statement:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2   =   0.5
1/3   =   0.(3)
1/4   =   0.25
1/5   =   0.2
1/6   =   0.1(6)
1/7   =   0.(142857)
1/8   =   0.125
1/9   =   0.(1)
1/10  =   0.1 

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

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

Link: https://projecteuler.net/problem=26

I tried to solve it in Python:

My approach:

• For every d, assume you are solving for 1 / d by hand.

• In case the 1 is completely divisible by d, it means the cycle length is 0.

• If a value you have already divided appears again, it means you've found the cycle.

• The cycle would have length of the number of times you've repeated the first step minus the first time the cycled value appears as we have to remove non-cycling values.

Here's my code following the above steps in Python:

LIMIT = 1000

# The maximum length
maxi = 0

# The 'd' that has maximum length
maxi_d = 1

for d in range(1, LIMIT):
    quotient = [] # Stores the decimal quotient
    cur_value = 1 # Variable used to perform division as if by hand

    len_recur = 0 # Recurring length

    # Performing division as if by hand.
    while cur_value not in quotient:
        if not cur_value:   # If the value is not recurring:
            break           # break as the rucurring length must be 0

        len_recur += 1
        quotient.append(cur_value)

        cur_value = (cur_value % d) * 10

    if not cur_value:
        continue

    # Remove number of values that do not recur
    len_recur -= quotient.index(cur_value) + 1

    if len_recur > maxi:
        maxi = len_recur
        maxi_d = d

print(maxi_d)

I'd like to make this code as fast as possible. This currently takes ~3.5 seconds for LIMIT = 2000 and grows exponentially larger.

PS: I know len_recur can be replaced by len(quotient), but I want the code to be as fast as possible.

Answer 1

Boosting time performance:

Starting with minor naming issues: maxi is better named as max_len (as stated in comment). maxi_d is renamed to max_d.
It's good to move the processing into a separate function, called like calc_longest_recur_cycle.

The main time-performance hits in your implementation is caused by quotient list and its expensive list operations:

• quotient.append
• quotient.index
• cur_value not in quotient

According to that fact that quotient and len_recur are reset on each outer for loop iteration and on the level of while loop the fragment

len_recur += 1
quotient.append(cur_value)

tells that cur_value is appended synchronously with incrementing len_recur i.e. the cur_value will get the position equal to len_recur. That means that, on this level, cur_value can be mapped to its position contained in len_recur.
Thus, quotient is initiated as dictionary (instead of list): quotient = {} or even quotient = {0: 0} as AJNeufeld suggested to eliminate cur_value evaluation on the while loop condition.

---

The construction:

while cur_value not in quotient:
    if not cur_value:  # If the value is not recurring:
        break

is essentially a verbose equivalent to:

while cur_value and cur_value not in quotient:

---

List indexing

len_recur -= quotient.index(cur_value) + 1 

is now efficiently replaced with dict indexing (where values are positions)

len_recur -= quotient[cur_value]

---

Now, with quotient as dict, we have O(1) complexity for membership check (cur_value not in quotient) and indexing operation (len_recur -= quotient[cur_value])

The final version:

LIMIT = 5000

def calc_longest_recur_cycle():
    max_len = 0   # The maximum length
    max_d = 1     # The 'd' that has maximum length

    for d in range(1, LIMIT):
        quotient = {0: 0}  # Stores the decimal quotient
        cur_value = 1      # Variable used to perform division as if by hand
        len_recur = 0      # Recurring length

        # Performing division as if by hand
        while cur_value not in quotient:  # while the value is not recurring
            len_recur += 1
            quotient[cur_value] = len_recur
            cur_value = (cur_value % d) * 10

        if not cur_value:
            continue

        # Remove number of values that do not recur
        len_recur -= quotient[cur_value]
        # quotient.clear()

        if len_recur > max_len:
            max_len = len_recur
            max_d = d

    return max_d

---

What needs to be mentioned is that despite of its fast nature dict would take more space than list, but only at the time of one nominal loop iteration as it's reset and last quotient filled at the end will be garbage-collected on function exit.

Let's get to tests.
I've increased limit to LIMIT = 5000 to "turn up the heat" and have put the "old" implementation into separate function calc_recur_cycle_old for comparison.
As for resulting max_d value - both functions return the same result:

print(calc_recur_cycle_old())      # 4967
print(calc_longest_recur_cycle())  # 4967

And the most interesting time performance comparison:

from timeit import timeit

print(timeit('calc_recur_cycle_old()', 'from __main__ import calc_recur_cycle_old', number=1))
19.648109548998036

print(timeit('calc_longest_recur_cycle()', 'from __main__ import calc_longest_recur_cycle', number=1))
0.26926991600339534

The end ... )