This is another problem taken from Project Euler. Link.
The problem:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
So basically we have to find the sum of all even numbers in the Fibonacci sequence within a limit of four million (4000000).
The logic behind this program is simple, we will keep doing addition until our limit reaches 4,000,000. There is just one optimization to the process. If you observe carefully, every third number in the Fibonacci sequence is an even number. So we blindly add every third number in the sequence. This reduces a lot of processing time.
We will be using the datatype BigInteger in our program as we will be dealing with massive numbers.
BigInteger class can be found in java.math.*; package.
Some pointers about BigInteger datatype:
We cannot use the arithmetic or logical operators with the BigInteger datatype. Instead, we use the various methods provided in the package which are as follows. We will be focusing only on the methods used in this program.
add() : To add two BigIntegers.
Syntax:
|
1 |
result = num1.add(num2); |
The above line adds num1 and num2 and stores its value in result.
compareTo(): Used to compare to BigIntegers.
Syntax:
|
1 |
result = num1.compareTo(num2); |
The above line compares num1 and num2. If num1 > num2, result is assigned a positive number. If num1 == num2, result is assigned 0. If num1 < num2, result is assigned a negative number.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
//Project Euler problem 2. import java.math.BigInteger; public class P2 { static BigInteger max = new BigInteger("4000000"); //This is our limit provided in the question. public static void main(String[] args) { BigInteger sum = new BigInteger("0"); //Initializing sum to 0 BigInteger a= new BigInteger("0"); //Initializing a to 0 BigInteger b = new BigInteger("1"); //Initializing b to 0 BigInteger c=new BigInteger("0"); long count= 3;//The Loop to print the rest of the numbers long count3=2; for(count =1;;count++,count3++) { c=a.add(b); //Adding a and b a=b; b=c; if(c.compareTo(max)>=0) //If c exceeds our limit of 4000000, we stop the execution of the loop. { break; } if(count3%3==0 && count3!=0)//We only add every third number in the sequence { System.out.println("Adding "+c+" to "+sum); sum=sum.add(c); //Adding even numbers in the sequence to the current sum } }//End for System.out.println("Sum is:"+sum); //Prints the required answer System.out.println("Total iterations: "+count); //Prints total number of iterations System.out.println("Total addition operations performed: "+(count3/3)); //Prints the number of addition operations performed }//End PSVM }//End class |
Output:
Tested in Eclipse
Vlad
Latest posts by Vlad (see all)
- Code jam “Tic-Tac-Toe-Tomek” solution in java - April 19, 2013
- Code jam “Minimum Scalar product” solution in java - March 18, 2013
- Code jam Store Credit solution in java - March 10, 2013
