Skip to content
March 31, 2011 / oop123

Project Euler #73 – Java

You can see the problem here: Problem #73.

Having learned the Farey Sequence from question 71, this is very easy.

0/1, 1/3, 1/2, 2/3, 1/1

Using the two fraction 1/3 and 1/2, you can generate all the sorted reduce fractions between it by generating the sequence between them. There is, however a few things to note. First, a fraction in the sequence can have a denominator larger than 12,000, so we need to factor that in. Second, we don’t need the numerator at all since we just want the denominators. Finally, and this is the most important point, you don’t need to generate the fractions, you only need to count them. Using those points, I made a recursive function that will count the numbers of fractions within the Farey sequence with denominator less than 12, 000. Unfortunately, it always over-count by 1 (I assume it counted 1/2, but what do I know, I suck at recursion), but whatever, it works.

private static int Farey(int a, int b) {
	int mediant = a + b;
	if (mediant > 12, 000) return 1;
	return Farey(a, mediant) + Farey(mediant, b); //get the count from the left side and the right side
}

Just call the method with 3 and 2 and subtract 1 from the returned int.

After I read the forum and the pdf associated with the problem. I find out that what I implemented is actually the Stern-Brocot tree algorithm (I’m so proud of myself right now. Again, if you don’t know what the heck that is, wiki it). The difference is the actual algorithm gives the actual count and doesn’t over-count by 1 (which makes it vastly better than mine).

I modify my function into the Stern-Brocot tree form and now I got this.

private static int Farey(int limit, int a, int b) {
	int mediant = a + b;
	if (mediant > limit) return 0;
	else {
		int count = 1;
		count += Farey(limit, a, mediant) + Farey(limit, mediant, b);
		return count;
	}
}

Unfortunately, if the limit is too big, the computer will run out of stack space. On my computer, it only went up to about 14,000. Of course, I could unroll the recursion into an iteration and manage the stack manually, which will give me a higher limit and also be faster because it reduces method call overhead, but hey, I solve the problem in less than 5 minutes and 5 lines of code which is surprising for me, so I can’t complain too much.

That’s it, folks, 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: