# 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 as an example. Starting from the bottom, multiply by 2 gives or . This gives the next fraction as . Multiply that by 5 (the inner denominator), you get . 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