### 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!

A lot of useful information as always, thank you and best regards!

GilbertsAx September 16, 2021 6:34:48 AM

It is very good that you can find more and more information on this topic on the Internet.

Andrewjes September 16, 2021 9:53:02 AM

Contact Me
Recent Blog Activity
Blog Archive