Skip to main content

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)
	{
		Sequence task = new Sequence();
		// Test
		task.golombSequence(15);
		task.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
// 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()
{
	Sequence *task = new Sequence();
	// Test
	task->golombSequence(15);
	task->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
// 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)
	{
		Sequence task = new Sequence();
		// Test
		task.golombSequence(15);
		task.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
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()
{
	$task = new Sequence();
	// Test
	$task->golombSequence(15);
	$task->golombSequence(25);
}
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()
{
	var task = new Sequence();
	// Test
	task.golombSequence(15);
	task.golombSequence(25);
}
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() :
	task = Sequence()
	#  Test
	task.golombSequence(15)
	task.golombSequence(25)

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() 
	task = Sequence.new()
	#  Test
	task.golombSequence(15)
	task.golombSequence(25)
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
		task.golombSequence(15);
		task.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
// 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()
{
	let task: Sequence = Sequence();
	// Test
	task.golombSequence(15);
	task.golombSequence(25);
}
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
{
	val task: Sequence = Sequence();
	// Test
	task.golombSequence(15);
	task.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

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.

Last updated on by Kalkicode




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.

New Comment