Solution to Problem 26 on Project Euler


The problem:

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.

My Solution

#include <stdio.h>

int main(){
  int i,value,max,counter,max2,z;
  max=0;
  for (i=7;i<1000;i++){
    counter=0;
    value = 10%i;
    z=1000;
    while (value != 1 && z>0){
      value = value *10;
      value = value % i;
      counter++;
      z--;
    }
    if (counter>max && z>1){
      max=counter;
      max2=i;
    }
  }
  printf("%d\n",max2);
return 0;
}

One thought on “Solution to Problem 26 on Project Euler

  1. Michael

    This is probably the easiest-to-understand solution I’ve seen for this problem.

    I refactored it to use different variable names and add some document comments:

    “`
    #include
    using namespace std;

    int main() {
    int i, bestI, length, maxLength, value, digitLimit;
    maxLength = 0;
    for (i = 7; i < 1000; i++){
    length = 0;
    value = 10 % i; // 3, 2, 1, 0, 10, 10, 10…
    digitLimit = i – 1; // the length of the repetend is at most (i-1)

    /* for i's above 10, the value above is 10.
    * Therefore, if value ever equals 1, on the
    * next loop, value *= 10 will again equal 10,
    * which % i will still equal 10, which on the
    * next loop would simply repeat the very first
    * iteration of the while loop.
    *
    * Accordingly, check to see if value == 1,
    * and break if it is.
    */
    while (value != 1 && length maxLength && length <= digitLimit) {
    maxLength = length;
    bestI = i;
    }
    }
    cout << bestI << endl;
    return 0;
    }
    “`

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *