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.
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]);

            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)

            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

It is worth ensuring that such websites have more and more content. Keep it up!

ReubenGrina September 25, 2021 1:31:44 AM

I go to see daily some websites and sites to read articles, but this weblog provides feature based posts. situs agen slot

Cole February 24, 2022 3:22:10 PM

Way cool! Some extremely valid points! I appreciate you penning this write-up and also the rest of the website is also really good. donate for ukraine

Luz June 15, 2022 7:20:06 AM

Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates. I've been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this. Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your new updates. donate for ukraine

Hye June 26, 2022 4:33:55 PM

Хелло:) Кто знает кто крутил барабаны на вебсайте казино восток игровые автоматы казино casino Просто нашел в поисковике казино рв вулкан и стало интересно.

Kraig July 3, 2022 1:43:16 PM

Leave a Comment