Challenge: Largest Reciprocal Cycle

Posted on: June 9, 2017 2:05:16 AM
This is another project euler challenge that states:

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 problem required me to do quite a bit of research on decimals with recurring cycles. I came across a wikipedia article that led me to Fermat's Little Theorem to get the number of digits in the cycle, aka, the period. From there, the problem was easy to solve.
Program.cs
using Common.Math;
using System;

namespace ProjectEuler_26
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            Tuple result = new Tuple(0, 0);

            // start by getting primes up to 1000
            var primes = Eratosthenes.GetPrimes(1000);

            // loop backwards
            for (int i = primes.Length - 1; i >= 0; i--)
            {
                int count;

                // we know that the most a cyclical decimal will repeat is d-1
                if ((count = GetCyclicalCount(primes[i])) == primes[i] - 1)
                {
                    result = new Tuple(count, primes[i]);
                    break;
                }
            }

            Console.WriteLine($"The value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part is {result.Item2} with {result.Item1} numbers in the cycle.");
        }

        private static int GetCyclicalCount(int prime)
        {
            int period = 1;

            // using Fermat's Little Theorim you can get the count of numbers in the cycle referred to as a period
            // Fermat's Little Theorim is defined as a^p=a%p
            // where a is the number base and p is a prime of that number base
            // this means that the count of cyclical numbers is the first modular power where the period test is not 1

            while (ModularPow(10, period, prime) != 1)
            {
                period++;
            }

            return period;
        }

        private static int ModularPow(int @base, int exponent, int modulus)
        {
            if (modulus == 1) return 0;

            int result = 1;
            for (int i = 1; i <= exponent; i++)
            {
                result = (result * @base) % modulus;
            }

            return result;
        }
    }
}
The code is pretty well documented and explains what it's doing at just about every step. Enjoy!

Comments


No comments yet, be the first to leave one.

Leave a Comment