Skip to content
March 31, 2011 / oop123

Project Euler #71 – Java

You can see the problem here: Problem #71.

(I code this, not realizing there’s a way to solve this without programming at all. All those smart people in the forum, sigh. You can skip my stupid code and my bad grammer)

For this problem, I realize you don’t actually need to calculate all the reduced fractions (and it’s impossible anyway, as there are too many of them). Instead, all you need to do is using each number 1 to 1, 000, 000 as a denominator, find the fraction closest to 3/7 without going over it; for example, for the fraction with denominator 17, 7/17 is just to the left of 3/7 while 8/17 would’ve exceeded it. Then among those 1,000,000 fractions, find the one closest to 3/7 and that will be the solution.

To get the fraction with denominator d closest to 3/7, you first get the numerator n = Math.truncate(n * 3 / 7). Then we can check how close the fraction is to 3/7 by getting the decimal representation of it and compare it to 3/7. You can optimize the problem further by realizing that the answer’s denominator is probably above 900,000.

Here is my Java code.

double f37 = 3.0 / 7,
minDifference = 1,
tempFrac = 0, tempDiff = 0;
int numerator = 0, denominator = 0;

//find the closest fraction to 3/7
for (int i = 8, j = 1; i < 1000000; ++i, ++j) {
    //we need to skip denominator that are multiples of 7 because they will reduced to 3/7
    //to do this, instead of modulus which is slow, I just use another counting variable that
    //will cause the loop to skip every time it reaches 7
    if (j == 7) {
        j = 0; //reset for next time
        continue;
    }

    tempFrac = ((double) (i * 3 / 7)) / i;
    tempDiff = f37 - tempFrac;

    if (tempDiff < minDifference) {
         minDifference = tempDiff;
        denominator = i;
    }
}

//calculate numerator from denominator
numerator = denominator * 3 / 7;
System.out.println(numerator + "/" + denominator);

Note that this doesn’t reduce the denominator and numerator. I did it with some online website

Now, for the non-code solution. You could generate all the reduced fractions in sorted sequence by using the Farey Sequence (Wikipedia it or something). I learned about the sequence before but never though I can use it here. Anyway, starting at the beginning, we can generate this sequence:

0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 1/1

Note that 2/5 is just to the left of 3/7, so we can find the fraction closest to 3/7 without going over 100000 by repeatedly adding 3 to 2 and 7 to 5. (2/5, 5/12, 8/19…) You can do this on a calculator, which kinda made my code moot and made me sad. CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: