Solution to Problem 26 on Project Euler

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;
}
“`