Jacobsthal Number in Java

In this section, we will learn about finding the jacobsthal number in Java. Mathematically, the jacobsthal numbers are defined as:

J_a= (2^a – (-1)^a) / 3 where a >= 0

Thus,

For a = 0,

J₀= (2⁰– (-1)⁰) / 3 = (1 – (1)) / 3 = 0 / 3 = 0

For a = 1,

J₁= (2¹– (-1)¹) / 3 = (2 – (-1)) / 3 = 3 / 3 = 1

For a = 2,

J₂= (2²– (-1)²) / 3 = (4 – (1)) / 3 = 3 / 3 = 1

For a = 3,

J₃= (2³– (-1)³) / 3 = (8 – (-1)) / 3 = 9 / 3 = 3

For a = 4,

J₄= (2⁴– (-1)⁴) / 3 = (16 – (1)) / 3 = 15 / 3 = 5

For a = 5,

J₄= (2⁵– (-1)⁵) / 3 = (32 – (-1)) / 3 = 33 / 3 = 11

Implementation

Let’s see how one can implement the above mathematical formula. Observe the following Java program.

FileName: JacobsthalNumberExample1.java

  public class JacobsthalNumberExample1  {  // a method that finds the value of b^e  int pow(int b, int e)  {  // anything whose power is 0 is 1  if(e == 0)  {  return 1;  }    // it will store the result  int ans = 1;  while(true)  {    if(e % 2 == 1)  {  e = e – 1;  ans = ans * b;  if(e == 0)  {  return ans;  }  }    b = b * b;  e = e / 2;  }    }  public int findJacobsthal(int a)  {  // finding (2)^a  int x = pow(2, a);    // finding (-1)^a  int y = pow(-1, a);    // finding the jacobsthal number  int no = (x – y) / 3;    return no;  }    // main method  public static void main(String argvs[])  {  // creating an object of the class JacobsthalNumberExample1  JacobsthalNumberExample1 obj = new JacobsthalNumberExample1();    System.out.println(“The first 20 Jacobsthal numbers are: “);    for(int i = 0; i < 20; i++)  {  // invoking the method findJacobsthal()  int num = obj.findJacobsthal(i);        System.out.print(num + ” “);  }  }  }  

Output:

The first 20 Jacobsthal numbers are:   0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

Using Recursion

The jacbosthal numbers can also be found using recursion. However, to find jacbosthal numbers using recursion, we must know the recursive formula of it.

J₀ = 0 and J₁ = 1

J_a = J_{a – 1} + 2 * J_{a – 2}, for a >= 2

Thus,

For a = 2

J₂= J_{2 – 1}+ 2 * J_{2 – 2}= J₁+ 2 * J₀= 1 + 2 * 0 = 1 + 0 = 1

For a = 3,

J₃= J_{3 – 1}+ 2 * J_{3 – 2}= J₂+ 2 * J₁= 1 + 2 * 1 = 1 + 2 = 3

For a = 4,

J₄= J_{4 – 1}+ 2 * J_{4 – 2}= J₃+ 2 * J₂= 3 + 2 * 1 = 3 + 2 = 5

For a = 5,

J₅= J_{5 – 1}+ 2 * J_{5 – 2}= J₄+ 2 * J₃= 5 + 2 * 3 = 5 + 6 = 11

Implementation

Let’s see the implementation of the above recursive formula.

FileName: JacobsthalNumberExample2.java

  // A Java program that shows how one can use  // recursion with memoization to find the Jacobsthal numbers  public class JacobsthalNumberExample2  {  // a[] is used for the memoization in the recursive calls  // it is done to avoid repeatitive recursive calls   // For example, J3 = J2 + 2 * J1  // Also, J2 = J1 * 2 * J0  // We see that in J3 and in J2 we have to find the value of J1  // if we will not use array a[], then we have to compute the   // value of J1 twice (one for J3 and another for J2), which in turn will consume more   // time.    // initializing the array of size 20 with the value -1  public static int a[] =                    {                       -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,                      -1, -1, -1, -1, -1, -1, -1, -1, -1, -1                       };  // method that finds the ith Jacobsthal number  public int findJacobsthal(int i)  {  // if the value of a[i] is not equal to -1, then   // it means the Jacobsthal number for the ith position  // has already been computed. So, all we have to do   // is to reuse it  if(a[i] != -1)  {  return a[i];  }  if(i == 0)  {  a[i] = 0;  // handling base case  return 0;  }  else if(i == 1)  {  a[i] = 1;  // handling base case  return 1;  }  // recursively finding the ith jacobsthal number  // Also, storing the value of the jacobsthal number   // sitting at the ith position. So that it is reused later.  a[i] = findJacobsthal(i – 1) + 2 * findJacobsthal(i – 2);  return a[i];  }  // main method  public static void main(String argvs[])  {  // creating an object of the class JacobsthalNumberExample2  JacobsthalNumberExample2 obj = new JacobsthalNumberExample2();  System.out.println(“The first 20 Jacobsthal numbers are: “);  for(int i = 0; i < 20; i++)  {  // invoking the method findJacobsthal()  int num = obj.findJacobsthal(i);   System.out.print(num + ” “);  }  }  }  

Output:

The first 20 Jacobsthal numbers are:   0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

Iterative Implementation

Instead of recursion, one can also use loops to find the jacobsthal numbers. The following program depicts the same.

Implementation

Let’s see the implementation of the above recursive formula in an iterative way.

FileName: JacobsthalNumberExample3.java

  public class JacobsthalNumberExample3  {    // main method  public static void main(String argvs[])  {  // creating an object of the class JacobsthalNumberExample3  JacobsthalNumberExample3 obj = new JacobsthalNumberExample3();    // for storing the first 20 Jacobsthal numbers  int a[] = new int[20];    // base cases  a[0] = 0;  a[1] = 1;    // computing the remaining Jacobsthal number  for(int i = 2; i < 20; i++)  {  a[i] = a[i – 1] + 2 * a[i – 2];  }    System.out.println(“The first 20 Jacobsthal numbers are: “);    // displaying the jacobsthal numbers  for(int i = 0; i < 20; i++)  {  System.out.print(a[i] + ” “);  }  }  }  

Output:

The first 20 Jacobsthal numbers are:   0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

The above program uses an array to compute the jacobsthal numbers, whose size is dependent on the total number of jacobsthal numbers we want to find. Therefore, for computing up to 10 jacobsthal numbers, we will use an array of size 10, and for computing up to 20 jacobsthal numbers, we will use an array of size 20. If we observe carefully, we will find that the current jacobsthal number is dependent on the last two jacobsthal number. In the following recursive formula,

J_a= J_{a – 1}+ 2 * J_{a – 2}

J_{a – 1}is the last jacobsthal number, and J_{a – 2}is the second last jacobsthal number.

Therefore, instead of using an array, we can use only two variables to find the jacobsthal numbers. The following program illustrates the same.

FileName: JacobsthalNumberExample4.java

  public class JacobsthalNumberExample4  {  // main method  public static void main(String argvs[])  {  // creating an object of the class JacobsthalNumberExample4  JacobsthalNumberExample4 obj = new JacobsthalNumberExample4();  // the first two jacobsthal numbers are 0 & 1  int a = 0;  int b = 1;  System.out.println(“The first 20 Jacobsthal numbers are: “);  // computing the remaining Jacobsthal number   //  and along side printing them   for(int i = 0; i < 20; i++)  {  // base case  if(i == 0)  {  System.out.print(a + ” “);  }  else if(i == 1)  {  // base case  System.out.print(b + ” “);      }  else  {  // computing the current jacobsthal number  // using the recurrence formula  int c = b + 2 * a;  System.out.print(c + ” “);  // updating the last and the second last   // Jacobsthal number  a = b;  b = c;  }  }  }  }  

Output:

The first 20 Jacobsthal numbers are:   0 1 1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923 21845 43691 87381 174763

Note: The above approach is the best approach for finding the Jacobsthal numbers as the space complexity of the program is O(1) also, it takes the least time as compared to the other approaches.

Next TopicJava BLOB

Jacobsthal Number in Java

Jacobsthal Number in Java

Implementation

Using Recursion

Implementation

Iterative Implementation

Implementation

Note: The above approach is the best approach for finding the Jacobsthal numbers as the space complexity of the program is O(1) also, it takes the least time as compared to the other approaches.

How to Take Multiple String Input in Java Using Scanner

Java constructor returns a value, but what

You may also like