Skip to content
April 8, 2011 / oop123

Project Euler #65 – Java

You can see the problem here: Problem #65.

A simple problem. The fraction can be iteratively worked from bottom to top with the following functions:

  • n(x) = d(x – 1)
  • d(x) = n(x – 1) + d(x – 1) * (the current addend)

The above two functions just describe how to reduce the fractions in the problem. I will use 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2}}} as an example. Starting from the bottom, multiply \cfrac{1}{2 + \cfrac{1}{2}} by 2 gives \dfrac{2}{4 + 1} or \dfrac{2}{5} . This gives the next fraction as \cfrac{1}{2 + \cfrac{2}{5}} . Multiply that by 5 (the inner denominator), you get \dfrac{5}{12} . I implemented the above steps as a function. Turns out the numerator even overflowed long, so I cheated and used the BigInteger class.

Getting the numerator and add its digits together:

int[] addends = new int[99];

//could just code it by hand, but Java already provide a utility class, so...
Arrays.fill(addends, 1);

//get the 2, 4, 6, 8... in the addends
for (int i = 1, j = 2; i < addends.length; i += 3, j += 2) {
	addends[i] = j;
}

//get the numerator
String number = continuedBigFractionNumerator(2, addends).toString();
int sum = 0;
for (int i = 0, len = number.length(); i < len; ++i) {
	//-48 convert a char digit to the actual digit (i.e. '0' -> 0), Unicode is fun
	sum += number.charAt(i) - 48;
}
System.out.println(sum);

The .continuedBigFractionNumerator() function:

private static BigInteger continuedBigFractionNumerator(int base, int[] addends) {
	int len = addends.length;
	BigInteger numer = BigInteger.ONE,
		       denom = new BigInteger(String.valueOf(addends[len - 1])),
		       tempNumer;

	for (int i = len - 2; i >= 0; --i) {
		tempNumer = numer;
		numer = denom;
		denom = denom.multiply(new BigInteger(String.valueOf(addends[i]))).add(tempNumer);
	}

	return numer.add(denom.multiply(new BigInteger(String.valueOf(base))));
}

Runs in just few milliseconds on my computer. This was really easy, 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: