Sylvester Sequence in Java

In this section, we will learn what is Sylvester Sequence and also create Java programs to that calculates the Sylvester Sequence. The Sylvester Sequence program is frequently asked in Java coding interviews and academics.

Sylvester Sequence

A Sylvester Sequence is a number sequence where each term is the product of the previous terms, plus 1. The first two terms of the sequence are 2 and 3. Using the first two terms, we will compute the other terms of the Sylvester sequence.

S₁ = 2, and S₂ = 3

Thus,

S₃ = (S₁ x S₂) + 1 = (2 x 3) + 1 = 7

S₄ = (S₁ x S₂ x S₃) + 1 = (2 x 3 x 7) + 1 = 43

S₅ = (S₁ x S₂ x S₃ x S₄) + 1 = (2 x 3 x 7 x 43) + 1 = 1807

S₆ = (S₁ x S₂ x S₃ x S₄ x S₅) + 1 = (2 x 3 x 7 x 43 x 1807) + 1 = 3263443

Let's see the different approaches for computing the Sylvester Sequence.

Approach: Using Nested Loop

Observe the following program for finding the Sylvester sequence.

FileName: SylvesterSeq.java

Output:

The first 6 terms of the Sylvester's Sequence are: 2 3 7 43 1807 3263443 

Complexity Analysis: Since the program is using the nested loop, the time complexity of the program is O(n2). Also, the program uses an array list, making the space complexity of the program O(n).

Let's see the optimized way of computing the Sylvester Sequence, where we will be reducing the time as well as the space complexity.

FileName: SylvesterSeq1.java

Output:

The first 6 terms of the Sylvester's Sequence are: 2 3 7 43 1807 3263443 

Complexity Analysis: The time complexity of the program is O(n), and the space complexity of the program is O(1).