# Golomb sequence using dynamic programming

The Golomb sequence is a non-decreasing sequence of positive integers where each element represents the number of times that a specific integer appears in the sequence. This sequence is named after Solomon W. Golomb, an American mathematician. The sequence starts with the numbers 1, 2, 2, 3, 3, 4, 4, and so on.

## Problem Statement

The task is to generate the Golomb sequence up to a given number 'n' using dynamic programming. The input is an integer 'n', and the output is the Golomb sequence up to the 'n'th term.

## Pseudocode Algorithm with Explanation

Let's break down the code and understand the steps involved in generating the Golomb sequence using dynamic programming:

``````1. golombSequence(n):
- Check if 'n' is less than or equal to 0. If true, return.
- Create an array 'dp' of size 'n + 1' to store the Golomb sequence.
- Initialize the first two elements of 'dp' as dp[0] = 0 and dp[1] = 1.
- Print the size of the sequence (value of 'n').
- Print the first element of the sequence (dp[1]).
- Use a loop starting from 2 up to 'n':
- Calculate the Golomb sequence using the formula:
dp[i] = dp[i - dp[dp[i - 1]]] + 1
- Print each element of the sequence (dp[i]).

2. main():
- Call the function golombSequence with different test inputs.```
```

The algorithm utilizes dynamic programming to calculate each element of the Golomb sequence efficiently. It stores the previously calculated elements in the 'dp' array to avoid redundant calculations.

## Code Solution

``````// C Program
// Golomb sequence using dynamic programming
#include <stdio.h>

void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int dp[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
printf("\n Size : %d", n);
// First sequence
printf("\n %d", dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
printf("  %d", dp[i]);
}
}
int main()
{
// Test
golombSequence(15);
golombSequence(25);
return 0;
}``````

#### Output

`````` Size : 15
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6
Size : 25
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8  8  8  8  9  9``````
``````// Java program for
// Golomb sequence using dynamic programming
public class Sequence
{
public void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
System.out.print("\n Size : " + n);
// First sequence
System.out.print("\n " + dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
System.out.print(" " + dp[i]);
}
}
public static void main(String[] args)
{
// Test
}
}``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````// Include header file
#include <iostream>
using namespace std;

// C++ program for
// Golomb sequence using dynamic programming
class Sequence
{
public: void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int dp[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
cout << "\n Size : " << n;
// First sequence
cout << "\n " << dp[1];
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
cout << " " << dp[i];
}
}
};
int main()
{
// Test
return 0;
}``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````// Include namespace system
using System;
// Csharp program for
// Golomb sequence using dynamic programming
public class Sequence
{
public void golombSequence(int n)
{
if (n <= 0)
{
return;
}
int[] dp = new int[n + 1];
// Set initial value
dp[0] = 0;
dp[1] = 1;
Console.Write("\n Size : " + n);
// First sequence
Console.Write("\n " + dp[1]);
// Display other sequence
for (int i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
Console.Write(" " + dp[i]);
}
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````package main
import "fmt"
// Go program for
// Golomb sequence using dynamic programming

func golombSequence(n int) {
if n <= 0 {
return
}
var dp = make([] int, n + 1)
// Set initial value
dp[0] = 0
dp[1] = 1
fmt.Print("\n Size : ", n)
// First sequence
fmt.Print("\n ", dp[1])
// Display other sequence
for i := 2 ; i <= n ; i++ {
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
// Display value
fmt.Print(" ", dp[i])
}
}
func main() {

// Test
golombSequence(15)
golombSequence(25)
}``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````<?php
// Php program for
// Golomb sequence using dynamic programming
class Sequence
{
public	function golombSequence(\$n)
{
if (\$n <= 0)
{
return;
}
\$dp = array_fill(0, \$n + 1, 0);
// Set initial value
\$dp[0] = 0;
\$dp[1] = 1;
echo("\n Size : ".\$n);
// First sequence
echo("\n ".\$dp[1]);
// Display other sequence
for (\$i = 2; \$i <= \$n; ++\$i)
{
// Calculate golomb sequence
\$dp[\$i] = \$dp[\$i - \$dp[\$dp[\$i - 1]]] + 1;
// Display value
echo(" ".\$dp[\$i]);
}
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````// Node JS program for
// Golomb sequence using dynamic programming
class Sequence
{
golombSequence(n)
{
if (n <= 0)
{
return;
}
var dp = Array(n + 1).fill(0);
// Set initial value
dp[0] = 0;
dp[1] = 1;
process.stdout.write("\n Size : " + n);
// First sequence
process.stdout.write("\n " + dp[1]);
// Display other sequence
for (var i = 2; i <= n; ++i)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
process.stdout.write(" " + dp[i]);
}
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````#  Python 3 program for
#  Golomb sequence using dynamic programming
class Sequence :
def golombSequence(self, n) :
if (n <= 0) :
return

dp = [0] * (n + 1)
#  Set initial value
dp[0] = 0
dp[1] = 1
print("\n Size : ", n, end = "")
#  First sequence
print("\n ", dp[1], end = "")
i = 2
#  Display other sequence
while (i <= n) :
#  Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
#  Display value
print(" ", dp[i], end = "")
i += 1

def main() :
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Size :  15
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6
Size :  25
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8  8  8  8  9  9``````
``````#  Ruby program for
#  Golomb sequence using dynamic programming
class Sequence
def golombSequence(n)
if (n <= 0)
return
end

dp = Array.new(n + 1) {0}
#  Set initial value
dp[0] = 0
dp[1] = 1
print("\n Size : ", n)
#  First sequence
print("\n ", dp[1])
i = 2
#  Display other sequence
while (i <= n)
#  Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1
#  Display value
print(" ", dp[i])
i += 1
end

end

end

def main()
#  Test
end

main()``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````// Scala program for
// Golomb sequence using dynamic programming
class Sequence()
{
def golombSequence(n: Int): Unit = {
if (n <= 0)
{
return;
}
var dp: Array[Int] = Array.fill[Int](n + 1)(0);
// Set initial value
dp(0) = 0;
dp(1) = 1;
print("\n Size : " + n);
// First sequence
print("\n " + dp(1));
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp(i) = dp(i - dp(dp(i - 1))) + 1;
// Display value
print(" " + dp(i));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Sequence = new Sequence();
// Test
}
}``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````
``````// Swift 4 program for
// Golomb sequence using dynamic programming
class Sequence
{
func golombSequence(_ n: Int)
{
if (n <= 0)
{
return;
}
var dp: [Int] = Array(repeating: 0, count: n + 1);
// Set initial value
dp[0] = 0;
dp[1] = 1;
print("\n Size : ", n, terminator: "");
// First sequence
print("\n ", dp[1], terminator: "");
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
print(" ", dp[i], terminator: "");
i += 1;
}
}
}
func main()
{
// Test
}
main();``````

#### Output

`````` Size :  15
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6
Size :  25
1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8  8  8  8  9  9``````
``````// Kotlin program for
// Golomb sequence using dynamic programming
class Sequence
{
fun golombSequence(n: Int): Unit
{
if (n <= 0)
{
return;
}
val dp: Array < Int > = Array(n + 1)
{
0
};
// Set initial value
dp[0] = 0;
dp[1] = 1;
print("\n Size : " + n);
// First sequence
print("\n " + dp[1]);
var i: Int = 2;
// Display other sequence
while (i <= n)
{
// Calculate golomb sequence
dp[i] = dp[i - dp[dp[i - 1]]] + 1;
// Display value
print(" " + dp[i]);
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

`````` Size : 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
Size : 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9``````

## Resultant Output Explanation

Let's analyze the output generated by the provided code for two test inputs, 15 and 25:

For n = 15:

``````
Size: 15
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6
```
```

The size of the sequence is 15, and the first element is 1. The following elements represent the Golomb sequence up to the 15th term. Each number indicates the number of times a specific integer appears in the sequence.

For n = 25:

``````
Size: 25
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9
```
```

Similarly, for n = 25, the size of the sequence is 25, and the first element is 1. The subsequent elements represent the Golomb sequence up to the 25th term.

Time Complexity:

The time complexity of the provided code is O(n) since the loop iterates from 2 to n, performing constant-time operations within each iteration.

## Finally

We explored the Golomb sequence and implemented it using dynamic programming in C. We discussed the problem statement, provided pseudocode algorithm with explanations, and analyzed the resultant output for two test inputs. The Golomb sequence is an interesting sequence that can be efficiently generated using dynamic programming techniques, enabling us to avoid redundant calculations and improve performance.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.