*45*

# Star Numbers in Java

In this section, we are going to learn about **stars numbers in Java**. The stars number resembles the board of the Chinese checkers game. A star number is a hexagram. Here, a hexagram means a six-pointed star. Observe the following diagram.

Mathematically, the number is represented by

S_{n} = 6 x n x (n – 1) + 1, where n >= 1

Thus,

S_{1} = 6 x 1 x (1 – 1) + 1 = 6 x 1 x 0 + 1 = 0 + 1 = 1

S_{2} = 6 x 2 x (2 – 1) + 1 = 6 x 2 x 1 + 1 = 12 + 1 = 13

S_{3} = 6 x 3 x (3 – 1) + 1 = 6 x 3 x 2 + 1 = 36 + 1 = 37

S_{4} = 6 x 4 x (4 – 1) + 1 = 6 x 4 x 3 + 1 = 72 + 1 = 73

S_{5} = 6 x 5 x (5 – 1) + 1 = 6 x 5 x 4 + 1 = 120 + 1 = 121

S_{6} = 6 x 6 x (6 – 1) + 1 = 6 x 6 x 5 + 1 = 180 + 1 = 181

## Implementation

There are three ways to write the code for the star numbers in Java. One way is using the formula defined above, the other is recursive, and the last one is iterative. Let’s start with the formula-based approach.

### Formula based Approach

**FileName:** StarNumbers.java

**Output:**

The first 10 star numbers are: 1 13 37 73 121 181 253 337 433 541

**Time-Complexity:** The time-complexity of the above program is O(n), where n is the total number of star numbers that have to be found.

**Space Complexity:** The above program is not using any extra space; therefore, the space complexity of the above program is O(1).

### Recursive Approach

Using recursion also, one can compute the star numbers. However, before implementing the recursion, one must know the recursive formula for computing the star numbers. The recursive formula is defined as:

S_{n} = S_{n – 1} + 12 x (n – 1), where n >= 2 and S_{1} = 1

Thus,

S_{2} = S_{2 – 1} + 12 x (2 – 1) = = S_{1} + 12 x 1 = 1 + 12 = 13

S_{3} = S_{3 – 1} + 12 x (3 – 1) = = S_{2} + 12 x 2 = 13 + 24 = 37

S_{4} = S_{4 – 1} + 12 x (4 – 1) = = S_{3} + 12 x 3 = 37 + 36 = 73

S_{5} = S_{5 – 1} + 12 x (5 – 1) = = S_{4} + 12 x 4 = 73 + 48 = 121

S_{6} = S_{6 – 1} + 12 x (6 – 1) = = S_{5} + 12 x 5 = 121 + 60 = 181

Observe the following Java code.

**FileName:** StarNumbers1.java

**Output:**

The first 10 star numbers are: 1 13 37 73 121 181 253 337 433 541

**Time-Complexity:** For finding the nth star number, one has to recursive go from n to 1. Therefore, the time complexity of the above program is O(n^{2}), where n is the total number of star numbers that have to be computed.

**Space Complexity:** If we ignore the implicit memory consumption due to recursion, the space complexity of the above program is O(1).

In order to optimize the above program, one has to use the memorization technique. The following program shows the same.

**FileName:** StarNumbers2.java

**Output:**

The first 10 star numbers are: 1 13 37 73 121 181 253 337 433 541

**Time Complexity:** Because of the memorization technique, the time complexity of the above program is O(n), where n is the total number of star numbers that have to be computed.

**Space Complexity:** The space complexity of the above program is O(n), where n is the total number of star numbers that have to be computed.

### Iterative Approach

Using a loop also, one can easily compute the value of the star numbers. The following program shows the same.

**FileName:** StarNumbers3.java

**Output:**

The first 10 star numbers are: 1 13 37 73 121 181 253 337 433 541

**Time Complexity:** Because of the for-loop used in the calculation of finding each star number, the time complexity of the above program is O(n^{2}), where n is the total number of star numbers one has to find.

**Space Complexity:** The space complexity of the above program is O(n), where n is the total number of star numbers that have to be computed.

We can optimize the above code to reduce the time complexity. See the following program.

**FileName:** StarNumbers4.java

**Output:**

The first 10 star numbers are: 1 13 37 73 121 181 253 337 433 541

**Time Complexity:** As there is only one loop for computing the star numbers; therefore, the time complexity of the above program is O(n), where n is the total number of star numbers one has to find.

**Space Complexity:** The space complexity of the above program is O(n), where n is the total number of star numbers that have to be computed.

We can still do some optimization to reduce the space complexity of the program. If we observe the recursive formula, we find that the nth star number is dependent on the (n- -1)th star number, and (n – 1)th star number is dependent on the (n – 2)th star number, and so on. That means the current star number is dependent on the previous star number. Therefore, we do not need an array for storing the star numbers. All we have to do is to store the previous star number in a variable to compute the current star number. The following program shows the same.

**FileName:** StarNumbers5.java

**Output:**

The first 10 star numbers are: 1 13 37 73 121 181 253 337 433 541

**Time Complexity:** As there is only one loop for computing the star numbers; therefore, the time complexity of the above program is O(n), where n is the total number of star numbers one has to find.

**Space Complexity:** As we are using only two variables for computing the star numbers; therefore, the space complexity of the above program is O(1).

## Relation with the Other Numbers

- There are many star numbers that are also triangular numbers. Numbers such as 1, 253, 49141, and many more are the star as well as the triangular number.
- There are many star numbers that are also square numbers. Numbers such as 1 = 1
^{2}, 121 = 11^{2}, 11881 = 109^{2}, and many more are the star as well as the square number. - A star prime number is a number that is a prime as well as a star number. For example: 13, 37, 73, and many more are the star as well as the prime numbers.