Project Euler Problem 14

Bismillah.

Hey guys. Problem 14 was solved by me. This time, it's about Collatz Problem. Read about the problem in the previous link.

Now, let's see how I tried to solve it. First, I guess simulate it's example by simply display the numbers in sequence. I thought that using methods would be the best. The pseduocode is something like this.

if value is even
    n = n/2
else
    n = 3*n+1

I almost forgot during the writing of first program, that we need to put * for multiplication. It was used recursively, because I read about dynamic programming using recursion and caching. Then, when I succeded in making a method that display sequence for 13, I started thinking at the bigger picture of the problem.

After some reading from Google search hits, I see that it might overflow our count variable or any other name for it as you see fit. So I thought about BigInteger. There are way too many methods needed. such as remainder() to replace %, equals(), divide(), multiply(), add(). I even asked dreamincode about it, and sure the overflow comes from int limitation. I even use cache and vector. Modified it into BigInteger, and I got wrong answer. Hmm...

By the way, its about having two main variables: longest and longestchain. longest store the value of number that have highest chain/sequence/steps, while longestchain is the number of chain/sequence/steps. table variable that you can see here is the caching, or memoization. See this example: if you use number 13 as starting point, sequences would be this: 13 40 20 10 5 16 8 4 2 1. But when we use larger number, maybe 1000, It will comes at some point, reach the number 13 too. So, of course it repeat the same sequence there. By caching those numbers, you can reduce significantly the number of processes.

Using primitive type int (overflow):
Using class BigInteger(wrong answer):

Say, can we use long?

Hahaha. Well, it is more of the brute force way, and took 7 secs if I use the methods. Without recursion and the cache. I think I should edit this method to used recursive, or just put that process in main program, that makes about 4 secs. Other solution on webs can reach less than 1 sec.

Slower and didn't apply dynamic programming:
I think I may or may not try to build the program that apply dynamic programming again. Any question?