Skip to content
April 3, 2011 / oop123

Project Euler #72 – Java

You can see the problem here: Problem #72.

Unfortunately, this problem cannot be solved using the Farey sequence. 1,000,000 is just too big so I didn’t even bother try writing code to do it. It took me about 15 minutes to think up the solution (I actually had the right idea for 10 minutes but didn’t realize it, oh well).

To solve the question, I realize a fraction is considered reduced only if its numerator is coprime to its denominator (i.e. no common prime factors, 6 and 35 are coprime because 6 has prime factors 2 and 3 while 35 has 5 and 7). For example, if you let denominator = 1000, the numerator has to be a number that’s coprime to 1000. Since 1000 can factored into 2^4 * 5^4, the numerator can be any integer below 1000 that’s not a multiple of 2 or 5 (e.g. 1, 3, 7, 9…). The count of the numbers with this property will then give you the number of reduced fractions with a denominator of 1000.

There is a math function called the totient function, or φ(n), which gives you the number of integers below n that is coprime to n. Question #70 also uses the totient function, so this is related to that question. Anyway, I rewrote the totient sieve from #70 and just figure out \sum_{i=2}^{1000000}\ \Phi(n) (sum of φ(n) from n = 2 to 1,000,000).

	int LIMIT = 1000001;

	int[] totient = new int[LIMIT];
	for (int i = 1; i < LIMIT; ++i) {
		totient[i] = i;
	}

	long sum = 0;
	int tempNum = 1;
	for (int i = 2; i < LIMIT; ++i) {
		if (totient[i] == i) {
			--totient[i];
			tempNum = i - 1;
			for (int j = i << 1; j < LIMIT; j += i) {
				totient[j] = totient[j] / i * tempNum;
			}
		}
		sum += totient[i];
	}

	System.out.println(sum);

This ran in ~200 milliseconds on my computer.

For those people who have no idea how the totient sieve work: φ(n) can be figured by finding all its distinct prime factors. Then for each factor p, multiply n by (p-1)/p. For example, 18 can be factored into 2 * 3^2. Multiply 18 by (2-1)/2 and (3-1)/3 gives you 6, which is φ(18). In words, because half of the integers below 18 are divisible by 2, multiplying 18 by (2-1)/2 will give the number of integers not divisible by 2. Then, in those 9 numbers, one third is divisible by 3, so multiplying 9 by (3-1)/3 gives 6 which is φ(18). (See Wikipedia for a much better explaination) Knowing this, using a modification of Eratosthenes sieve where instead of composite numbers being removed, it’s used to calculate the totient function.

I look at some of the harder questions and I have no idea how to do them :(. Damn, I wanted to become least level 3, sigh. 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: