How I solved Project Euler 26 using an algorithm from the 70’s

The problem

A unit fraction contains 1 in the numerator. 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 makes for a really interesting problem to solve. There is the brute force way but always with Project Euler problems there is also a neat mathemagical way to do things as well. As ever I went off to do a little research…

Fermats Little Theorem

In essence the problem involves finding the largest repeating string in all of the unit fractions with denominators between 1-1000. It sounds easy and once I solved it it was reasonably straight forward. What struck me first it wasn’t necessary to compute all the decimals. This would be a waste of resources so I needed a way to compute repeating decimals of note through out the process.

I won’t be the last to say my Mathematics is a little bit rusty at this stage but you get the idea.

Repeating Decimals

What I needed really was a string representation of each of the decimals produced by the prime so I hacked together a quick and nasty function to generate strings to about 10,000 digit precision:

        private static string GenerateRepeatingPatternString(int prime)
        {
            string final_string = string.Empty;
            int divisor = 10;

            while (final_string.Length < 10000)
            {
                var result = divisor / prime;
             var remainder = divisor % prime;

                if (result == 0)
                {
                    divisor = divisor * 1;
                }
                else if (result > 0)
                {
                    divisor = remainder;
                    final_string = final_string + result;
                }
            }
            return final_string;
        }

Building a Suffix Tree

I figured that once that this list of individual strings up to 10,000 characters would need something particularly novel to determine which one of them had the longest repeating section. A Suffix Tree is a data-structure that allows many problems on strings (sequences of characters) to be solved quickly. The uses of algorithms like this come to the fore in bioformatics in which pattern matching plays a really important part.

Since I had a relatively large set of strings generated. I used Mark Nelsons implementation of the Suffix Tree in C# in order to complete this. By generating a suffix tree for each of the strings I managed to build a tree very quickly for each of the strings. Determining the prime that had the longest repeating string was then a straightforward count on the edges in the graph produced. The source code for the Suffix Tree implementation used in this is available from http://code.google.com/p/csharsuffixtree/

photo credit: 邪恶的正太 via photopin cc