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

essay writers canada [url="https://lawessayhelpinlondon.com"]service essay writing[/url] online essay writing service review

GinniesrPa October 9, 2022 12:28:47 PM

cheap essay writing service online [url="https://lawessayhelpinlondon.com"]cheap custom essay writing services[/url] persuasive essay helper

GinniesrPa October 9, 2022 12:47:19 PM

the help essay questions [url="https://ukessayservice.net"]top essay writing services[/url] best college essay editing service

VivienesrPa October 11, 2022 6:48:29 PM

cheap custom essays [url="https://writemyessaycheap24h.com"]top rated essay writing websites[/url] scholarship essay help

EastersrPa October 13, 2022 9:50:17 AM

write my admissions essay [url="https://writemyessaycheap24h.com"]professional essay writers[/url] best custom essay website

EastersrPa October 13, 2022 10:08:35 AM

https://prednisoneall.top/

HpfGPDP October 30, 2022 11:54:35 AM

Our website [url=https://www.bestcrazygames.com]play best crazy games[/url] has begun to discharge stylish games and driving games, and reborn opportunities to from them here are added. We come quotidian driving games nearby trucks, bikes, racing, cars, and other channel types. Another recommended class is games seeking girls with fashion dress-up and make-up. If you be sure what is playing these days is the most qualified predominant .io games, numerous developers released chic io games on the browser in pattern years, such as hole.io, venge.io, voxiom.io, and much more .io super games. Also, we are striving to count up some uncordial new kid erudition games to amend the leader and reflective abilities. Also, some other types of car games online inclination improve your reflex and timing abilities.

Baorier November 5, 2022 10:44:06 AM

Our website [url=https://www.crazygamesonline.com/]crazy games online[/url] and we classify our multiplayer games free online into the 11 most preferred classifications: driving, capturing, clicker, and.io. We started as a driving game internet site and have collected around 1000 of the best driving games. These multiplayer games best include car games, bike games, monster trucks games, and any other two-player games you can consider. Later our shooting games have taken off.

Caorier November 5, 2022 3:52:29 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 November 9, 2022 1:44:46 PM

english essay helper [url="https://bestcampusessays.com"]write my essay paper[/url] buy essay paper

DorolisasrPa November 19, 2022 7:16:50 AM

help with essay papers [url="https://besteasyessays.org"]help with argumentative essay[/url] i need help with writing an essay

MartysrPa November 20, 2022 1:42:02 PM

online essay writing services [url="https://besteasyessays.org"]help writing college application essay[/url] history essay writing service

MartysrPa November 20, 2022 2:07:25 PM

top rated essay writing services [url="https://bestessayreviews.net"]write my essay for cheap[/url] cheap essays writing service

MerolasrPa November 21, 2022 9:30:13 PM

best essays writing service [url="https://bestessaysden.com"]college admission essay help[/url] essays writing services

AshlensrPa November 23, 2022 6:49:48 AM

buy college essays online [url="https://bestsessays.org"]custom essay[/url] reviews for essay writing services

CharitasrPa November 24, 2022 2:05:56 PM

buy essay online cheap [url="https://buyacademicessay.com"]buy custom essay online[/url] writing essays custom

NanicesrPa November 25, 2022 11:27:40 PM

custom essay UK [url="https://buyacademicessay.com"]write my essay wikipedia[/url] essay online help

NanicesrPa November 25, 2022 11:51:29 PM

Leave a Comment