Open In App

Sylvester’s sequence

Last Updated : 16 Feb, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

In number system, Sylvester’s sequence is an integer sequence in which each member of the sequence is the product of the previous members, plus one. Given a positive integer N. The task is to print the first N member of the sequence. 
Since numbers can be very big, use %10^9 + 7.
Examples: 
 

Input : N = 6
Output : 2 3 7 43 1807 3263443

Input : N = 2
Output : 2 3

 

The idea is to run a loop and take two variables and initialise them as 1 and 2, one to store the product till now and other to store the current number which is nothing but the first number + 1 and for each step multiply both using arithmetic modular operation i.e (a + b)%N = (a%N + b%N)%N where N is a modular number.
Below is the implementation of this approach: 
 

C++




// CPP program to print terms of Sylvester's sequence
#include <bits/stdc++.h>
using namespace std;
#define N 1000000007
  
void printSequence(int n)
{
    int a = 1; // To store the product.
    int ans = 2; // To store the current number.
  
    // Loop till n.
    for (int i = 1; i <= n; i++) {
        cout << ans << " ";
        ans = ((a % N) * (ans % N)) % N;
        a = ans;
        ans = (ans + 1) % N;
    }
}
  
// Driven Program
int main()
{
    int n = 6;
    printSequence(n);
    return 0;
}


Java




// JAVA Code for Sylvester sequence
import java.util.*;
  
class GFG {
      
    public static void printSequence(int n)
    {
        int a = 1; // To store the product.
        int ans = 2; // To store the current number.
        int N = 1000000007;
          
        // Loop till n.
        for (int i = 1; i <= n; i++) {
           System.out.print(ans + " ");
            ans = ((a % N) * (ans % N)) % N;
            a = ans;
            ans = (ans + 1) % N;
        }
    }
  
    /* Driver program to test above function */
    public static void main(String[] args) 
    {
        int n = 6;
        printSequence(n);
          
    }
}
    
// This code is contributed by Arnav Kr. Mandal.


Python




# Python Code for Sylvester sequence
  
def printSequence(n) :
    a = 1 # To store the product.
    ans = 2 # To store the current number.
    N = 1000000007
      
    # Loop till n.
    i = 1
    while i <= n :
        print ans,
        ans = ((a % N) * (ans % N)) % N
        a = ans
        ans = (ans + 1) % N
        i = i + 1
          
  
# Driver program to test above function 
n = 6
printSequence(n)
  
# This code is contributed by Nikita Tiwari.


C#




// C# Code for Sylvester sequence
using System;
  
class GFG {
      
    public static void printSequence(int n)
    {
         // To store the product.
        int a = 1;
          
        // To store the current number.
        int ans = 2; 
          
        int N = 1000000007;
          
        // Loop till n.
        for (int i = 1; i <= n; i++)
        {
            Console.Write(ans + " ");
            ans = ((a % N) * (ans % N)) % N;
            a = ans;
            ans = (ans + 1) % N;
        }
    }
  
    // Driver program 
    public static void Main() 
    {
        int n = 6;
        printSequence(n);
          
    }
}
  
// This code is contributed by vt_m.


PHP




<?php
// PHP program to print 
// terms of Sylvester's sequence
  
$N = 1000000007;
  
function printSequence($n)
{
    global $N;
      
    // To store 
    // the product.
    $a = 1; 
      
    // To store the
    // current number.
    $ans = 2; 
  
    // Loop till n.
    for ($i = 1; $i <= $n; $i++)
    {
        echo $ans ," ";
        $ans = (($a % $N) * ($ans % $N)) % $N;
        $a = $ans;
        $ans = ($ans + 1) % $N;
    }
}
  
    // Driver Code
    $n = 6;
    printSequence($n);
      
// This code is contributed by anuj_67.
?>


Javascript




<script>
// Javascript program to print
// terms of Sylvester's sequence
  
let N = 1000000007;
  
function printSequence(n)
{
  
    // To store
    // the product.
    let a = 1;
      
    // To store the
    // current number.
    let ans = 2;
  
    // Loop till n.
    for (let i = 1; i <= n; i++)
    {
        document.write(ans + " ");
        ans = ((a % N) * (ans % N)) % N;
        a = ans;
        ans = (ans + 1) % N;
    }
}
  
    // Driver Code
    let n = 6;
    printSequence(n);
      
// This code is contributed by gfgking.
</script>


Output: 
 

2 3 7 43 1807 3263443

Time complexity : O(n) 
Auxiliary Space : O(1)

 



Previous Article
Next Article

Similar Reads

Minimum operations required to transform a sequence of numbers to a sequence where a[i]=a[i+2]
Given a sequence of integers of even length 'n', the task is to find the minimum number of operations required to convert the sequence to follow the rule a[i]=a[i+2] where 'i' is the index. The operation here is to replace any element of the sequence with any element. Examples: Input : n=4 ; Array : 3, 1, 3, 2 Output : 1 If we change the last eleme
11 min read
Convert an unbalanced bracket sequence to a balanced sequence
Given an unbalanced bracket sequence of '(' and ')', convert it into a balanced sequence by adding the minimum number of '(' at the beginning of the string and ')' at the end of the string. Examples: Input: str = ")))()" Output: "((()))()" Input: str = "())())(())())" Output: "(((())())(())())" Method 1: Approach: Initialize an empty stack.Iterate
13 min read
Find original sequence from Array containing the sequence merged many times in order
Given a number N and an array arr[] that consist of merging N length sequence of distinct integers any number of times maintaining the relative order of elements in the initial sequence. The task is to find the initial sequence of length N maintaining the right order. Examples: Input: N = 4, arr[] = {1, 13, 1, 24, 13, 24, 2, 2}Output: 1 13 24 2 Exp
10 min read
Find a valid parenthesis sequence of length K from a given valid parenthesis sequence
Given a string S of valid parentheses sequence of length N and an even integer K, the task is to find the valid parentheses sequence of length K which is also a subsequence of the given string. Note: There can be more than one valid sequence, print any of them. Examples: Input: S = "()()()", K = 4Output: ()()Explanation:The string "()()" is a subse
7 min read
Generate a sequence X from given sequence Y such that Yi = gcd(X1, X2 , ... , Xi)
Given a sequence Y of size N where: Yi = gcd(X1, X2, X3, . . ., Xi ) of some sequence X. The task is to find such a sequence X if any such X is possible. Note: If X exists there can be multiple value possible for X. Generating any one is sufficient. Examples: Input: N = 2, Y = [4, 2]Output: [4, 2]Explanation: Y0 = gcd(X0) = X0 = 4. And gcd(4, 2) =
7 min read
k-th missing element in increasing sequence which is not present in a given sequence
Given two sequences, one is increasing sequence a[] and another a normal sequence b[], find the K-th missing element in the increasing sequence which is not present in the given sequence. If no k-th missing element is there output -1 Examples: Input: a[] = {0, 2, 4, 6, 8, 10, 12, 14, 15}; b[] = {4, 10, 6, 8, 12}; k = 3 Output: 14 Explanation : The
6 min read
Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array
Given an array of 0s and 1s, find the position of 0 to be replaced with 1 to get longest continuous sequence of 1s. Expected time complexity is O(n) and auxiliary space is O(1). Example: Input: arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1} Output: Index 9 Assuming array index starts from 0, replacing 0 with 1 at index 9 causes the maximum continu
9 min read
Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array | Set-2
Given an array of 0s and 1s, find the position of 0 to be replaced with 1 to get longest continuous sequence of 1s. Expected time complexity is O(n) and auxiliary space is O(1). Examples: Input : arr[] = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1} Output : Index 9 Assuming array index starts from 0, replacing 0 with 1 at index 9 causes the maximum cont
15+ min read
Juggler Sequence | Set 2 (Using Recursion)
Juggler Sequence is a series of integer number in which the first term starts with a positive integer number a and the remaining terms are generated from the immediate previous term using the below recurrence relation : [Tex]a_{k+1}=\begin{Bmatrix} \lfloor a_{k}^{1/2} \rfloor & for \quad even \quad a_k\\ \lfloor a_{k}^{3/2} \rfloor & for \q
4 min read
Thue-Morse sequence
Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is an infinite binary sequence of 0s and 1s. The sequence is obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained so far. First few steps : Start with 0 Append complement of 0, we get 01 Append complement of 01, we get 0110 Append complement of 01
6 min read
Sum of the sequence 2, 22, 222, .........
Find the sum of the following sequence : 2, 22, 222, ......... to n terms. Examples : Input : 2 Output: 23.99868 Input : 3 Output: 245.98647 A simple solution is to compute terms one by one and add to the result.The above problem can be efficiently solved using the following formula: C/C++ Code // CPP program to find sum of series // 2, 22, 222, ..
3 min read
Golomb sequence
In mathematics, the Golomb sequence is a non-decreasing integer sequence where n-th term is equal to number of times n appears in the sequence.The first few values are 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, ...... Explanation of few terms: Third term is 2, note that three appears 2 times. Second term is 2, note that two appears 2 times. Fourth term is 3,
7 min read
Number of closing brackets needed to complete a regular bracket sequence
Given an incomplete bracket sequence S. The task is to find the number of closing brackets ')' needed to make it a regular bracket sequence and print the complete bracket sequence. You are allowed to add the brackets only at the end of the given bracket sequence. If it is not possible to complete the bracket sequence, print "IMPOSSIBLE". Let us def
7 min read
k-th number in the Odd-Even sequence
Given two numbers n and k, find the k-th number in the Odd-Even sequence made of n. The Odd-Even sequence contains first contains all odd numbers from 1 to n then all even numbers in set 1 to n. Examples : Input : n = 5, k = 3 Output : 5 In this example, the Odd-Even is {1, 3, 5, 2, 4}. The third number in sequence is 5. Naive Approach : The first
4 min read
Second most repeated word in a sequence in Python
Given a sequence of strings, the task is to find out the second most repeated (or frequent) string in the given sequence. (Considering no two words are the second most repeated, there will be always a single word). Examples: Input : {"aaa", "bbb", "ccc", "bbb", "aaa", "aaa"} Output : bbb Input : {"geeks", "for", "geeks", "for", "geeks", "aaa"} Outp
4 min read
Sum of Arithmetic Geometric Sequence
In mathematics, an arithmetico–geometric sequence is the result of the term-by-term multiplication of a geometric progression with the corresponding terms of an arithmetic progression. is an arithmetico–geometric sequence.Given the value of a(First term of AP), n(Number of terms), d(Common Difference), b(First term of GP), r(Common ratio of GP). Th
9 min read
Program to print DNA sequence
Given the value of n i.e, the number of lobes. Print the double-helix structure of Deoxyribonucleic acid(DNA). Input: n = 8 Output: AT T--A A----T T------A T------A G----C T--A GC CG C--G A----T A------T T------A A----T A--T GC AT C--G T----A C------G C------G T----A G--C AT AT T--A A----T T------A T------A G----C T--A GC Explanation : DNA primaril
9 min read
Stern-Brocot Sequence
Stern Brocot sequence is similar to Fibonacci sequence but it is different in the way fibonacci sequence is generated . Generation of Stern Brocot sequence : 1. First and second element of the sequence is 1 and 1.2. Consider the second member of the sequence . Then, sum the considered member of the sequence and it's precedent i.e (1 + 1 = 2) . Now
5 min read
Print n terms of Newman-Conway Sequence
Newman-Conway numbers is the one that generates the following integer sequence. 1 1 2 2 3 4 4 4 5 6 7 7….. and follows the below recursive formula. P(n) = P(P(n - 1)) + P(n - P(n - 1)) Given a number n then print n terms of Newman-Conway Sequence Examples: Input : 13 Output : 1 1 2 2 3 4 4 4 5 6 7 7 8Input : 20 Output : 1 1 2 2 3 4 4 4 5 6 7 7 8 8
4 min read
Find minimum length sub-array which has given sub-sequence in it
Given an array arr[] of N elements, the task is to find the length of the smallest sub-array which has the sequence {0, 1, 2, 3, 4} as a sub-sequence in it. Examples: Input: arr[] = {0, 1, 2, 3, 4, 2, 0, 3, 4} Output: 5 The required Subarray is {0, 1, 2, 3, 4} with minimum length. The entire array also includes the sequence but it is not minimum in
10 min read
Finding nth term of any Polynomial Sequence
Given a few terms of a sequence, we are often asked to find the expression for the nth term of this sequence. While there is a multitude of ways to do this, In this article, we discuss an algorithmic approach which will give the correct answer for any polynomial expression. Note that this method fails for trigonometric, exponential or other transce
4 min read
Convert String into Binary Sequence
Given a string of character the task is to convert each character of a string into the equivalent binary number. Examples : Input : GFG Output : 1000111 1000110 1000111 Input : geeks Output : 1100111 1100101 1100101 1101011 1110011 The idea is to first calculate the length of the string as n and then run a loop n times. In each iteration store ASCI
5 min read
Check if a given string can be converted to a Balanced Bracket Sequence
Given a string S of size N consisting of '(', ')', and '$', the task is to check whether the given string can be converted into a balanced bracket sequence by replacing every occurrence of $ with either ) or (. A balanced bracket sequence is a sequence where every opening bracket "(" has a corresponding closing bracket ")". Examples: Input: S = "()
12 min read
Moser-de Bruijn Sequence
Given an integer 'n', print the first 'n' terms of the Moser-de Bruijn Sequence. Moser-de Bruijn sequence is the sequence obtained by adding up the distinct powers of the number 4 (For example, 1, 4, 16, 64, etc). Examples: Input : 5 Output : 0 1 4 5 16 Input : 10 Output : 0 1 4 5 16 17 20 21 64 65 It is observed that the terms of the sequence foll
12 min read
Baum Sweet Sequence
Baum Sweet Sequence is an infinite binary sequence of 0s and 1s. The nth term of the sequence is 1 if the number n has no odd number of contiguous zeroes in its binary representation, else the nth term is 0. The first few terms of the sequence are: b1 = 1 (binary of 1 is 1) b2 = 0 (binary of 2 is 10) b3 = 1 (binary of 3 is 11) b4 = 1 (binary of 4 i
5 min read
Find nth term of the Dragon Curve Sequence
Dragon Curve Sequence is an infinite binary sequence of 0's and 1's. The first term of the sequence is 1. From the next term, we alternately insert 1 and 0 between each element of the previous term. To understand better refer the following explanations: 1 (starts with 1) "1" 1 "0" 1 and 0 are inserted alternately to the left and right of the previo
9 min read
Minimum number of operations to convert a given sequence into a Geometric Progression
Given a sequence of N elements, only three operations can be performed on any element at most one time. The operations are: Add one to the element.Subtract one from the element.Leave the element unchanged. Perform any one of the operations on all elements in the array. The task is to find the minimum number of operations(addition and subtraction) t
14 min read
Program to print Collatz Sequence
Starting with any positive integer N, Collatz sequence is defined corresponding to n as the numbers formed by the following operations : If n is even, then n = n / 2.If n is odd, then n = 3*n + 1.Repeat above steps, until it becomes 1. Examples : Input : 3 Output : 3, 10, 5, 16, 8, 4, 2, 1 Input : 6 Output : 6, 3, 10, 5, 16, 8, 4, 2, 1 Below is the
4 min read
Print Fibonacci sequence using 2 variables
Print the Fibonacci sequence. The first Fibonacci numbers are: C/C++ Code // Simple CPP Program to print Fibonacci // sequence #include <iostream> using std::cout; void fib(int n) { int a = 0, b = 1, c; if (n >= 0) cout << a << " "; if (n >= 1) cout << b << " "; for (int i = 2; i <= n; i++)
6 min read
Maximum product quadruple (sub-sequence of size 4) in array
Given an integer array, find a maximum product of a quadruple in the array. Examples: Input: [10, 3, 5, 6, 20] Output: 6000 Multiplication of 10, 5, 6 and 20 Input: [-10, -3, -5, -6, -20] Output: 6000 Input: [1, -4, 3, -6, 7, 0] Output: 504 Approach 1 (Naive, O([Tex] [/Tex]) time, O(1) Space) Steps to solve this problem: 1.check if n is smaller tha
15+ min read
three90RightbarBannerImg