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


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

single gay men chat line highpoint nc [url="https://chatcongays.com"]choose a gay video chat free[/url] gay phone chat manhole

GenniesrPa September 16, 2022 12:10:46 AM

gay furry chat [url="https://chatcongays.com"]gay black man chat[/url] hairy gay men chat free

GenniesrPa September 16, 2022 2:32:26 AM

serial

Coral September 19, 2022 10:52:00 AM

buy an essay online [url="https://au-bestessays.org"]english essay helper[/url] customized essay writing

MarrissrPa September 20, 2022 12:51:09 AM

custom essay cheap [url="https://au-bestessays.org"]i need help writing my essay[/url] essay help chat room

MarrissrPa September 20, 2022 1:09:29 AM

write my essay service [url="https://bestcampusessays.com"]reliable essay writing service[/url] best custom essay

DorolisasrPa September 20, 2022 8:03:21 PM

essay writers toronto [url="https://bestcampusessays.com"]personal statement essay help[/url] buy college essays online

DorolisasrPa September 20, 2022 8:22:03 PM

A lot of thanks for all your hard work on this blog and alo try to [url=https://www.kizi10.org] play kizi10 games [/url]. Ellie takes pleasure in setting aside time for investigations and it’s really simple to grasp why. My spouse and i hear all concerning the compelling method you deliver powerful items on this website and as well strongly encourage participation from website visitors on the area plus my princess is undoubtedly being taught so much.

KizdiZ September 21, 2022 12:44:13 PM

college entrance essay writing service [url="https://besteasyessays.org"]help with writing essay[/url] essay editing service online

MartysrPa September 21, 2022 6:24:45 PM

essay writing websites [url="https://besteasyessays.org"]help me write a essay[/url] english essay writing service

MartysrPa September 21, 2022 6:42:12 PM

essay writers wanted [url="https://bestessayreviews.net"]custom college essay writing service[/url] how to write my essay

MerolasrPa September 22, 2022 2:23:31 PM

essay title help [url="https://bestessayreviews.net"]good essay writing service[/url] help writing essays

MerolasrPa September 22, 2022 2:43:01 PM

custom essay paper [url="https://bestessaysden.com"]custom essays for sale[/url] helping others essays

AshlensrPa September 23, 2022 10:27:27 AM

essay writer funny [url="https://bestsessays.org"]essay writer website[/url] KeyWord

CharitasrPa September 24, 2022 11:45:15 PM

essay help chat [url="https://bestsessays.org"]essay write service[/url] college essay help online

CharitasrPa September 25, 2022 12:02:26 AM

scholarship essay writing help [url="https://buyacademicessay.com"]cheap essays for sale[/url] best essay writing company

NanicesrPa September 25, 2022 6:43:07 PM

best custom essay service [url="https://buyacademicessay.com"]best online essay writer[/url] write my essay generator

NanicesrPa September 25, 2022 7:00:20 PM

best essay cheap [url="https://buy-eessay-online.com"]personal essay writing service[/url] essay help chat

ChelsaesrPa September 26, 2022 2:23:29 PM

which essay writing service is the best [url="https://buy-eessay-online.com"]help on essays[/url] i need help writing an essay

ChelsaesrPa September 26, 2022 2:41:08 PM

online essay editing service [url="https://buytopessays.com"]homework essay help[/url] essay writing assignment help

PennysrPa September 27, 2022 9:33:06 AM

essay help pros [url="https://buytopessays.com"]where can i buy an essay[/url] Who wants to write my essay

PennysrPa September 27, 2022 9:52:14 AM

buy essay cheap [url="https://cheapessaywritingservice1.com"]write my essay for money[/url] essay help chat

TammiesrPa September 28, 2022 5:21:13 AM

fast essay writing service [url="https://customcollegeessays.net"]custom essay writing reviews[/url] college admission essay service

AntoniesrPa September 29, 2022 1:19:09 AM

personal statement essay help [url="https://customcollegeessays.net"]academic essay writing service[/url] buy an essay online

AntoniesrPa September 29, 2022 1:35:03 AM

buy an essay online cheap [url="https://customessays-writing.org"]top ten essay writing services[/url] best essay website

RhiamonsrPa September 29, 2022 8:56:54 PM

help to write an essay [url="https://customessays-writing.org"]essays on the help[/url] i cant write my essay

RhiamonsrPa September 29, 2022 9:12:41 PM

essay help 123 [url="https://customessaywwriting.com"]help essays[/url] automatic essay writer

CharosrPa September 30, 2022 4:03:41 PM

best college essay help [url="https://customs-essays-writing.org"]help writing essays for college[/url] automatic essay writer

DronasrPa October 1, 2022 10:26:45 AM

admission essay services [url="https://firstessayservice.net"]academic essay writer[/url] looking for someone to write my essay

TwylasrPa October 2, 2022 5:56:02 AM

academic essay writing help [url="https://firstessayservice.net"]custom writing essay service[/url] essay writing services toronto

TwylasrPa October 2, 2022 6:13:07 AM

help writing scholarship essays [url="https://geniusessaywriters.net"]essays help[/url] act essay help

LeilahsrPa October 3, 2022 2:41:47 AM

best online essay writing service [url="https://howtobuyanessay.com"]service to others essay[/url] custom my essay

CthrinesrPa October 4, 2022 12:51:55 AM

Leave a Comment