Project Euler #26

Problem 26 at Project Euler asks

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.

This is a problem about repeated division by the same number – how many divisions can you do before you start repeating yourself? The division algorithm can be expressed as follows:

```def div_by(rem, div):
y = min([x for x in range(5) if rem*(10**x) > div])
return rem*(10**y) % div```

So then I need to use this to repeatedly divide by the test value d – len_pattern calls div_by until it detects a repeated remainder:

```def len_pattern(init, rems, d):
rem=div_by(init, d)
if rem in rems:
return len(rems) - rems.index(rem)
else:
rems.append(rem)
return len_pattern(rem, rems, d)```

I then have to use this to find out which d < 1000 has the longest cycle. However, I don't need to call it on all the numbers under 1000 – the only ones I really need to test are the primes. The upper bound on the length of the cycle is n-1 for any number n (for example the length of the cycle generated by 7 is 6), and primes are the only numbers which generate cycles of this length. So I need to use the list generated by the primes_under() function, then call len_pattern on each of these, returning the maximum length.

```def get_longest():
from EulerFunc import primes_under
divs = dict([(div, len_pattern(1.0, [], div)) \
for div in primes_under(1000) if div > 5])
longest=max(divs,  key=lambda x: divs[x])
print "Longest cycle is for %d with length %d" % \
(longest, divs[longest])

if __name__ == '__main__':
from timeit import Timer
t = Timer("get_longest()",  "from __main__ import get_longest")
print t.timeit(number=100)

>>> Longest cycle is for 983 with length 884
Longest cycle is for 983 with length 884
Longest cycle is for 983 with length 884
.
.
.
Longest cycle is for 983 with length 884
151.166881084```

So it takes on average around 1.5 seconds to run. Not bad, I see some people had Python code which ran in under a second, so I’m sure this could be optimised…

2 thoughts on “Project Euler #26”

1. Lee Crabtree says:

How the heck did you come up with that division function?

This is a problem I have with Project Euler – I really enjoy some of the problems, and my understanding of Python has definitely been expanded as a result of working through the list, but it sometimes feels like I need a goddamned PhD in math to know the best way to approach some of the problems.

I’m not a math-oriented person, and I don’t think you have to be in order to be a good programmer. It frustrates me that some of the problems focus on topics I haven’t needed in almost a decade of professional programming. Maybe I’m in the minority, though.

• geoffness says:

Lee – I completely agree with the comment that you don’t have to be math-oriented to be a good programmer.

The division algorithm is probably a bit shonky to be honest – it’s founded on the observation that at each stage after dividing by d, we have to multiply the remainder by some power of 10 in order to ensure that we get a value for % d. y is the least such value that will allow this.