Project Euler Problem #26

February 14, 2010

Read the details of the problem here

Summary

Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

Solution

This has me a little puzzled as to the best way to do it. I did consider simply using BigDecimal to calculate the fraction to, say, 2000 decimal places and then use a regex or a contracting substring search to find the recurring sequences but it didn’t feel very “Project Euler-like” for a question that was so obviously mathematical in nature.

A little digging around found the Wolfram page on Decimal Expansion which said that the length of the sequence was found from the Multiplicative Order of it’s denominator. This boiled down to just executing a repeated modulus operation until the remainder had already been seen, at which point a cycle would occur (the remainder being used as the input to the subsequent modulus operation). This seemed like quite a nice approach as I wouldn’t have to worry about the noise on the front of the expansion before detecting the cycle start.

I wrote it using perhaps more Groovy features that it deserved but it ends up in being a fairly neat solution.

def answer = (1..<1000).collect {
    def ( found, remainder, divisor ) = [ [:], 10, 2 ]
    while (true) {
        if (remainder == 0) return [ it, 0 ]
        if (found.containsKey(remainder))
            return [ it, divisor - found[remainder] ]
        found[remainder] = divisor
        ( remainder, divisor )  = [ 10 * (remainder % it), divisor+1 ]
    }
}.max { it[1] }[0]

This runs in 1.12 seconds. I could made it a little faster perhaps by only checking primes as candidates or short-circuiting even numbers but it’s not going to save a lot of time, and it’s already well-within the 15 second limit. One thing that might make it a lot quicker would be to check to see if the multiplicative order of a number was one less than the number itself – that would be the highest possible length. If I did a descending search and broke out if this condition occurred then it would be faster. However, this way I have a way of getting a list of the multiplicative order of all the numbers which might stand me in good stead for later puzzles.

Conclusion

Groovy offered a few nice features such the list transformation collect{} function, the ability to return tuples and the parameterised max{} listop that made this code quite concise. The multiple assignment feature was convenient in keep the code short but didn’t really add anything to the solution.

Advertisements

One Response to “Project Euler Problem #26”


  1. […] Obviously, at step 3, if the decimal portion has been seen before, that sequence would just repeat from then on, so a cycle would have been found. In that respect it’s very similar to the solution for Problem #26. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: