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, note that four appears 3 times.
Given a positive integer n. The task is to find the first n terms of Golomb sequence.
Examples:
Input : n = 4 Output : 1 2 2 3 Input : n = 6 Output : 1 2 2 3 3 4
The recurrence relation to find the nth term of Golomb sequence:
a(1) = 1
a(n + 1) = 1 + a(n + 1 – a(a(n)))
Below is the implementation using Recursion:
C++
// C++ Program to find first // n terms of Golomb sequence. #include <bits/stdc++.h> using namespace std; // Return the nth element // of Golomb sequence int findGolomb( int n) { // base case if (n == 1) return 1; // Recursive Step return 1 + findGolomb(n - findGolomb(findGolomb(n - 1))); } // Print the first n // term of Golomb Sequence void printGolomb( int n) { // Finding first n // terms of Golomb Sequence. for ( int i = 1; i <= n; i++) cout << findGolomb(i) << " " ; } // Driver Code int main() { int n = 9; printGolomb(n); return 0; } |
Java
// Java Program to find first // n terms of Golomb sequence. import java.util.*; class GFG { public static int findGolomb( int n) { // base case if (n == 1 ) return 1 ; // Recursive Step return 1 + findGolomb(n - findGolomb(findGolomb(n - 1 ))); } // Print the first n term of // Golomb Sequence public static void printGolomb( int n) { // Finding first n terms of // Golomb Sequence. for ( int i = 1 ; i <= n; i++) System.out.print(findGolomb(i) + " " ); } // Driver Code public static void main (String[] args) { int n = 9 ; printGolomb(n); } } // This code is contributed by Akash Singh |
Python3
# Python 3 Program to find first # n terms of Golomb sequence. # Return the nth element of # Golomb sequence def findGolomb(n): # base case if (n = = 1 ): return 1 # Recursive Step return 1 + findGolomb(n - findGolomb(findGolomb(n - 1 ))) # Print the first n term # of Golomb Sequence def printGolomb(n): # Finding first n terms of # Golomb Sequence. for i in range ( 1 , n + 1 ): print (findGolomb(i), end = " " ) # Driver Code n = 9 printGolomb(n) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# Program to find first n // terms of Golomb sequence. using System; class GFG { // Return the nth element // of Golomb sequence static int findGolomb( int n) { // base case if (n == 1) return 1; // Recursive Step return 1 + findGolomb(n - findGolomb(findGolomb(n - 1))); } // Print the first n term // of Golomb Sequence static void printGolomb( int n) { // Finding first n terms of // Golomb Sequence. for ( int i = 1; i <= n; i++) Console .Write(findGolomb(i) + " " ); } // Driver Code public static void Main () { int n = 9; printGolomb(n); } } // This code is contributed by vt_m |
PHP
<?php // PHP Program to find first // n terms of Golomb sequence. // Return the nth element // of Golomb sequence function findGolomb( $n ) { // base case if ( $n == 1) return 1; // Recursive Step return 1 + findGolomb( $n - findGolomb(findGolomb( $n - 1))); } // Print the first n // term of Golomb Sequence function printGolomb( $n ) { // Finding first n terms // of Golomb Sequence. for ( $i = 1; $i <= $n ; $i ++) echo findGolomb( $i ) , " " ; } // Driver Code $n = 9; printGolomb( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // javascript Program to find first // n terms of Golomb sequence. function findGolomb(n) { // base case if (n == 1) return 1; // Recursive Step return 1 + findGolomb(n - findGolomb(findGolomb(n - 1))); } // Print the first n term of // Golomb Sequence function printGolomb(n) { // Finding first n terms of // Golomb Sequence. for (let i = 1; i <= n; i++) document.write(findGolomb(i) + " " ); } // Driver Code var n = 9; printGolomb(n); // This code is contributed by Amit Katiyar </script> |
Output :
1 2 2 3 3 4 4 4 5
Below is the implementation using Dynamic Programming:
C++
// C++ Program to find first // n terms of Golomb sequence. #include <bits/stdc++.h> using namespace std; // Print the first n term // of Golomb Sequence void printGolomb( int n) { int dp[n + 1]; // base cases dp[1] = 1; cout << dp[1] << " " ; // Finding and printing first // n terms of Golomb Sequence. for ( int i = 2; i <= n; i++) { dp[i] = 1 + dp[i - dp[dp[i - 1]]]; cout << dp[i] << " " ; } } // Driver Code int main() { int n = 9; printGolomb(n); return 0; } |
Java
// Java Program to find first // n terms of Golomb sequence. import java.util.*; class GFG { public static void printGolomb( int n) { int dp[] = new int [n + 1 ]; // base cases dp[ 1 ] = 1 ; System.out.print(dp[ 1 ] + " " ); // Finding and printing first n // terms of Golomb Sequence. for ( int i = 2 ; i <= n; i++) { dp[i] = 1 + dp[i - dp[dp[i - 1 ]]]; System.out.print(dp[i] + " " ); } } // Driver code public static void main (String[] args) { int n = 9 ; printGolomb(n); } } // This code is contributed by Akash Singh |
Python3
# Python3 Program to find first # n terms of Golomb sequence. # Print the first n term # of Golomb Sequence def Golomb( n): dp = [ 0 ] * (n + 1 ) # base cases dp[ 1 ] = 1 print (dp[ 1 ], end = " " ) # Finding and print first # n terms of Golomb Sequence. for i in range ( 2 , n + 1 ): dp[i] = 1 + dp[i - dp[dp[i - 1 ]]] print (dp[i], end = " " ) # Driver Code n = 9 Golomb(n) # This code is contributed by ash264 |
C#
// C# Program to find first n // terms of Golomb sequence. using System; class GFG { // Print the first n term of // Golomb Sequence static void printGolomb( int n) { int []dp = new int [n + 1]; // base cases dp[1] = 1; Console.Write(dp[1] + " " ); // Finding and printing first n // terms of Golomb Sequence. for ( int i = 2; i <= n; i++) { dp[i] = 1 + dp[i - dp[dp[i - 1]]]; Console.Write( dp[i] + " " ); } } // Driver Code public static void Main () { int n = 9; printGolomb(n); } } // This code is contributed by vt_m |
PHP
<?php // PHP Program to find first // n terms of Golomb sequence. // Print the first n term // of Golomb Sequence function printGolomb( $n ) { // base cases $dp [1] = 1; echo $dp [1], " " ; // Finding and printing first // n terms of Golomb Sequence. for ( $i = 2; $i <= $n ; $i ++) { $dp [ $i ] = 1 + $dp [ $i - $dp [ $dp [ $i - 1]]]; echo $dp [ $i ], " " ; } } // Driver Code $n = 9; printGolomb( $n ); // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript Program to find first // n terms of Golomb sequence. // Print the first n term // of Golomb Sequence function printGolomb( n) { let dp = Array(n + 1).fill(0); // base cases dp[1] = 1; document.write(dp[1] + " " ); // Finding and printing first n // terms of Golomb Sequence. for ( i = 2; i <= n; i++) { dp[i] = 1 + dp[i - dp[dp[i - 1]]]; document.write(dp[i] + " " ); } } // Driver code let n = 9; printGolomb(n); // This code is contributed by shikhasingrajput </script> |
Output :
1 2 2 3 3 4 4 4 5
Time Complexity: O(n)
Auxiliary Space: O(n)