Grind Report 26

Problem 26

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 ¹/₇ 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="^(">¹/_d contains the longest recurring cycle in its decimal fraction part.

*WARNING: This contains the solution!*

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*