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 < src="http://projecteuler.net/index.php?section=problems&id=26" style="display: none;" alt="^(">^{1}/_{d} contains the longest recurring cycle in its decimal fraction part.

Ready to revisit 4th grade? This problem is a little tricky because of one thing - floating point precession. The precision required is far beyond our float or double we have available in C++ and so something more is required.

This "more" is actually from 4th grade. Do you remember long hand division? If not you can refresh your memory at the Long Division Wikipedia page - don't worry I wont tell anyone ;).

This is a very basic example; however, it shows something very important. That is if the remainder is the same as a previous encountered remainder then the number has a recurring cycle. Also, something not shown here, is the fact that if the remainder is 0 then the number does not have a recurring cycle. By just using these two pieces of knowledge this problem becomes fairly simple. All that is needed is to implement long division and check for if 0 or a previous remainder is encountered (this method requires storing the previous remainders).

Here is an implementation that solves the problem very quickly.

#include <iostream>

using std::cout;

const int MAX = 1000;

int main()

{

int answer;

int highest = 0;

for (int i = 1; i < MAX; ++i)

{

int count = 0;

int remainder = 1;

bool remainders[MAX] = {false};

while (remainder != 0)

{

//keep dropping 0s to the remainder until i can divide into it at least once

while (!(int)(remainder / i))

remainder *= 10;

//get the new remainder

remainder %= i;

//found a cycle

if (remainders[remainder])

break;

//store the remainder

remainders[remainder] = true;

count++;

}

//if there was a cycle and the count is greater than the previous highest

//then set the count as the new highest

if (remainder && count > highest)

{

highest = count;

answer = i;

}

}

cout << answer << ": " << highest;

}

*saved game*

## No comments:

## Post a Comment