Sylvester Sequence in Java
A Sylvester Sequence is a series of numbers in which each term is the sum of the terms before it plus 1. The sequence's first two terms are 2 and 3. We shall calculate the other terms of the Sylvester sequence using the first two terms.
Example
S1 = 3 , and S2 = 4Apple increases the prices of its US-based subscriptions!
S3 = ( S1 x S2 ) + 1 = ( 3 x 4 ) + 1 = 13
S4 = ( S1 x S2 x S3 ) + 1 = ( 3 x 4 x 13 ) + 1 = 157
S5 = ( S1 x S2 x S3 x S4 ) + 1 = ( 3 x 4 x 13 x 157 ) + 1 = 24493
S6 = ( S1 x S2 x S3 x S4 x S5 ) + 1 = (3 x 4 x 13 x 157 x 24493) + 1 = 599882557
Explanation
In the above example first and second terms are 3 and 4. The third term will product of first and second i.e., 3 and 4 and plus 1. So the third term is ( 3 * 4 ) + 1 =13. Fourth term will be product of first 3 terms plus 1 i.e., ( 3 * 4 * 13 ) +1 = 157.Likethis the Sylvester sequence goes on.
Using Loops
The goal is to create a loop that multiplies both variables by the arithmetic modular operation (a + b) % N = ( a % N + b % N ) % N ) , where N is a modular number, in order to store the product up to this point and the current number, which is just the first number plus 1.
SylvesterSequence1. java
// import statement to import required packages
import java . util . ArrayList ;
// public class with name SylvesterSequence1 is defined
public class SylvesterSequence1
{
// main method of the program where execution of the program starts
public static void main ( String args [ ] )
{
// list for storing the Sylvester sequence
ArrayList <Integer> a1 = new ArrayList < Integer > ( ) ;
// Adding the first two terms of the sequence
a1.add(3);
a1.add(4);
// for computing the first five terms
int n = 5;
System . out . println ( " The first " + n + " terms of the Sylvester's Sequence : " ) ;
// using loops to traverse through the iterations
for ( int j = 0; j < n; j++ )
{
int r = 1 ;
// if j=0 and j=1 it should print first term or second term
if ( ( j == 0) || ( j == 1) )
{
// It prints the first two terms of the sequence
System . out . print ( a1 . get ( j ) + " " ) ;
// continue statement is used to skip the present iteration of the loop
continue;
}
// using another for loop to calculate the nth term of the sequence by multiplying with previous term in the arraylist
for(int k = 0; k < a1 . size ( ) ; k++ )
{
r = r * a1 . get (k ) ;
}
// adding 1 to the result
r = r + 1;
// adding it to the list
a1 . add ( r ) ;
// printing the sequence
System . out . print ( r + " " ) ;
} // for loop for calculating nth term
} // main
} // SylvesterSequence1
Output:
Analysis of Complexity
Because the programme uses nested loops, its temporal complexity is O (n2). The programme employs an array list as well, increasing its O-level space complexity (n).
Optimal Approach
// Using the import statment to import the required packages
import java . util . ArrayList ;
public class Main
{
public void Sequence(int x)
{
int a = 1; // for storing the product.
int r = 2 ; // for storing the n th number.
for (int i = 1; i <= x; i++)
{
System.out.print( r + " ");
r = a * r;
a = r ;
r = ( r + 1 ) ;
}
}
// main method of the program where execution of the program starts
public static void main ( String args [ ] )
{
// creating an object for the class SylvesterSeq2
Main o1 = new Main ( ) ;
Scanner sc = new Scanner ( System . in ) ;
System . out . println ( " Enter the number of terms required in the sequence ");
// for computing the first six terms
int n=sc . nextInt ( ) ;
System . out . println ( " The first " + n + " terms of the Sylvester's Sequence are: " ) ;
o1 . Sequence ( n ) ;
}
}
Output
Complexity Analysis
The program's space complexity is O ( 1 ) , whereas its time complexity is O(n).