Project Euler Solution 26

Problem Statement#

Find the value of d < 1000 for which 1/d contains the longest recurring cycle.

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.

Solution#

Let us see how to find recurrent cycle for say d=14. For this keep track of the remainders.

N → Numerator

D → Denominator

R → Remainder

N = 1, D = 14, R = 1

N < D

N = N * 10 = 10

R = 0

N > D

R = N % D = 100 % 14 = 2

N = R * 10 = 20

N > D,

R = 20 % 14 = 6

N = R * 10 = 60

N > D

R= 60 % 14 = 4

N = 4 * 10 = 40

N > D

R = 40 % 14 = 12

N = 12 * 10 = 120

N > D

R = 120 % 14 = 8

N = 8 * 10 = 80

N > D

R = 80 % 14 = 10

N = 10 * 10 = 100

N > D

R = 100 % 14 = 2

R = 2 is occurring for the second time which means the same numbers are gonna be repeated. So the recurrent cycle length is 6.

Implementation#

#include <stdio.h>
int MAX_D_VALUE = 1000;
int main(){    int denominator, numerator, remainder, longest_d;    int rec_cycle_length = 0, longest_rec_cycle_length = 1;    int r_array[1000], r_index;    for (denominator = 2; denominator <= MAX_D_VALUE; denominator++)    {        r_index = 0;        rec_cycle_length = 0;        remainder = 1;        numerator = 10;        r_array[r_index] = 1;        r_index++;        while (remainder != 0)        {            while (numerator < denominator)            {                numerator *= 10;                r_array[r_index] = 0;                r_index++;            }            remainder = numerator % denominator;            if (remainder == 0)            {                rec_cycle_length = 0;                break;            }            r_array[r_index] = remainder;            r_index++;
            /******Finding recurrent cycle*******/
            int i = 0;            if (r_index > 1)            {                while (r_array[r_index - 1] != r_array[i])                {                    i++;                }                if (i == (r_index - 1))                {                    numerator = remainder * 10;                    continue;                }                if (r_array[r_index - 1] == r_array[i])                {                    rec_cycle_length = r_index - 1 - i;                    break;                }            }            numerator = remainder * 10;        }        if (rec_cycle_length > longest_rec_cycle_length)        {            longest_d = denominator;            longest_rec_cycle_length = rec_cycle_length;        }    }    printf("d < 1000 with Longest Recurrent cycle is %d", longest_d);}

Sample Output#

Sample Output