# Repeating decimals

Published on 2011-07-29Problem 26 was the first Project Euler problem I've yet encountered that I had to do research to solve. The problem asks for the integer under 1,000 whose reciprocal has the longest recurring cycle in its infinitely repeating decimal representation:

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 is the first problem in Project Euler to ask about non-integral values and it is designed to be unsolvable by floating-point arithmetic, as many terminating decimal values are repeating when represented as binary numerals: ^{1}/_{10}, for example, is 0.1 in base-10 but 0.00011 in binary. After some time reading basic number theory on Wolfram and Wikipedia, I found a few rules that could be used to find the answer:

**First**, only denominators that are both prime and coprime with 10 should be evaluated. Non-prime denominators*can*resolve into a repeating decimal, but it will be preceded by a non-repeating sequence, and the length of the recurring cycle will be equal to that of its smallest prime factor coprime with 10. For example, 14 isn't prime, and^{1}/_{14}has a recurring cycle in its infinitely repeating decimal, but the length of that cycle is equal to the length of the recurring cycle in^{1}/_{7}, i.e., the reciprocal of the smallest prime factor of 14 not coprime with 10.**Second**, the length of the recurring cycle of a repeating decimal^{1}/_{x}is equal to`p`

when 10^{p}mod`x`

= 1.**Third**, solving the problem by applying the above rule would involve manipulating huge numbers, i.e., BigIntegers

The large amount of BigInteger arithmetic in my code meant that it took a couple of seconds to execute, but it did work.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem026 { class Program { static void Main(string[] args) { int ceiling = 1000; int[] repeatingPeriod = new int[ceiling]; List<int> primesUnderCeiling = sieveOfEratosthenes(ceiling); int hauptExponent = 0; foreach (int i in primesUnderCeiling) { if (1000000 % i == 0) { repeatingPeriod[i] = 0; } else { do { hauptExponent++; repeatingPeriod[i] = hauptExponent; } while (BigIntModulo(10, hauptExponent, i) != 1); hauptExponent = 0; } } Console.WriteLine("Problem 26: {0}", Array.IndexOf(repeatingPeriod, repeatingPeriod.Max())); } private static int BigIntModulo(int p, int hauptExponent, int divisor) { System.Numerics.BigInteger power = p; int modulus = 0; for (int j = 1; j < hauptExponent; j++) power *= 10; modulus = (int)(power % divisor); return modulus; } private static List<int> sieveOfEratosthenes(int ceil) { List<int> eratosthenes = new List<int>(); for (int i = 2; i < ceil; i++) eratosthenes.Add(i); for (int i = 0; i < eratosthenes.Count(); i++) eratosthenes.RemoveAll(x => (x != eratosthenes[i]) && (x % eratosthenes[i] == 0)); return eratosthenes; } } }