# Project Euler #104 – Java

You can see the problem here: Problem #104.

I brute-forced the question… I didn’t know there was a formula for calculating the nth term for the Fibonacci sequence without calculating all the terms before it! Well, truth to be told, I had read something like that before in a book, but I forgot about it. Sigh. Anyway, this is (kind of) hard because you need to keep track of the first nine digits of the Fibonacci sequence, and I have no idea how to do that without calculating the whole sequence. I resorted to brute-forcing it.

I tested BigInteger and its toString() with a simple loop and found it’s just too slow. Even for the first 20000 Fibonacci numbers, it was already taking 1 second. I resorted to writing an array that would keep track of each part (9 digits long) of the Fibonacci number. Other than that, the logic is pretty simple – keep calculating the Fibonacci numbers until I solved the question.

int[] partsA = new int[50000], partsB = new int[50000], cache10 = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000}; int count = 1, temp; //initialize fibonacci sequence partsA[0] = 1; partsB[0] = 1; //carry flag boolean carry = false; //since the minimum possible answer is 2750, get the sequence until 2750 for (int i = 3; i < 2750; i++) { carry = false; for (int j = 0; j < count; j++) { temp = partsA[j]; partsA[j] = partsB[j]; partsB[j] = partsB[j] + temp; //if there is carry from last calculation, add 1 to current digit if (carry == true) { partsB[j]++; } //if current number is bigger than the limit, then set carry flag to true //else there is no carry if (partsB[j] > 1000000000) { //increase the number of array use to hold the numbers if (partsB[j + 1] == 0) { count++; } partsB[j] -= 1000000000; carry = true; } else { carry = false; } } } for (int i = 2750; ; i++) { carry = false; for (int j = 0; j < count; j++) { temp = partsA[j]; partsA[j] = partsB[j]; partsB[j] = partsB[j] + temp; //if there is carry from last calculation, add 1 to current digit if (carry == true) { partsB[j]++; } //if current number is bigger than the limit, then set carry flag to true //else there is no carry if (partsB[j] > 1000000000) { //increase the number of array use to hold the numbers if (partsB[j + 1] == 0) { count++; } partsB[j] -= 1000000000; carry = true; } else { carry = false; } } if (isPandigital9(partsB[0])) { //get the first nine digits int number = partsB[count - 1], digitsNum = DLNumber.numOfDigitsOf(<span class="hiddenGrammarError" pre="">number); number</span> = number * cache10[9 - digitsNum]; number += partsB[count - 2] / cache10[digitsNum]; if (isPandigital9(number)) { System.out.println("***" + number + ": " + i); break; } } }

isPandigital9() is very easy to implements (all the .digitOf() and .numOfDigitsOf() are methods I wrote before. I think they are very fast…).

private static boolean isPandigital9(int number) { int[] digits = DLNumber.digitsOf(number); boolean[] check = new boolean[10]; check[0] = true; for (int i = 0, len = digits.length; i < len; i++) { if (check[digits[i]]) { return false; } else { check[digits[i]] = true; } } return true; }

Runs in 20 seconds on my computer. Sigh. Anyway, if I only had known that there was a way to calculate the nth Fibonacci number without calculating the previous numbers. It would’ve hundreds of time faster.

Oh, well. I really didn’t want to brute force it, but I still finish it within a reasonable time (not really), so all’s good. CU

## Leave a Reply