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;
        }
    }
}