Golomb sequence

Columbus sequence - The Columbus sequence is a non-decreasing sequence of integers where the value of the nth item is the number of times the integer n appears in the sequence.

Some terms of Columbus sequence are,

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, 9, 9, 10, 10, 10, 10, …

Here, we can see that the 5th item is 3, and 5 also appears 3 times in the sequence.

The 6th item is 4, and 6 also appears 4 times in the sequence.

Properties of Columbus sequence - The first item of the sequence is 1, the nth item is the number of items in the sequence that is less than or equal to the n - nth item.

Problem Statement

Given an integer n. Find the first n terms in the Columbus sequence.

Example 1

Input: n = 4

Output: [1, 2, 2, 3]

Example 2

Input: n = 7

Output: [1, 2, 2, 3, 3, 4, 4]

Method 1: Use recursion

Using the properties of the Columbus sequence, the first item of the sequence is 1. To find the nth term, we use the following property: nth term is the number of terms less than or equal to 1 in the sequence up to the n - nth term.

Applying this method in a recursive function, if the nth item is the smallest positive integer that appears no earlier than n - golomb(golomb(n - 1)) times in the sequence, ensure that this property is satisfied, where golomb () is a recursive function that finds the nth term of the Columbus sequence.

pseudocode

procedure golomb (n)
   if n == 1
      ans = 1
   end if
   ans = 1 + golomb(n - golomb(golomb(n - 1)))
end procedure
procedure golombSeq (n)
   seq[n] = {0}
   for i = 1 to n
      seq[i - 1] = golomb(i)
   ans = seq
end procedure

Example: C implementation

In the following program, we use recursion to find the Columbus sequence.

#include <bits/stdc++.h>
using namespace std;

// Function to find golomb number
int golomb(int n){

   // First element is 1
   if (n == 1) {
      return 1;
   }
   
   // Satisfying property of golomb sequence for the nth number
   return 1 + golomb(n - golomb(golomb(n - 1)));
}

// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   for (int i = 1; i <= n; i++){
      seq[i - 1] = golomb(i);    
      }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++)    {
      cout << seq[i] << " ";
   }
   return 0;
} 

Output

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

Time complexity - O(n^2), because each item is calculated by recursively calculating the previous item.

Space complexity - O(n)

Method 2: Recursion with memoization

To remember the recursive code, we create a map to store the values ​​previously calculated recursively in the above code. Then when calculating each number, first check whether the previous number has been calculated, if so, take the previous calculation result, otherwise perform the calculation.

pseudocode

golomb (n, t)
   if n == 1
      ans = 1
   end if
   if n is present in t
      ans = t[n]
   end if
   ans = 1 + golomb(n - golomb(golomb(n - 1, t), t), t)
   t[n] = ans
end procedure
procedure golombSeq (n)
   seq[n] = {0}
   Initialize map: t
   for i = 1 to n
       seq[i - 1] = golomb(i, t)
   ans = seq
end procedure

Example: C implementation

In the following program, the results of previous calculations are stored in a map that can be accessed when calculating items.

#include <bits/stdc++.h>
using namespace std;

// Function to find golomb number
int golomb(int n, map<int, int> &t){

   // First term is 1
   if (n == 1){
      return 1;
   }
   
   // Checking if the term is previously computed
   if (t.find(n) != t.end()){
      return t[n];
   }
   int result = 1 + golomb(n - golomb(golomb(n - 1, t), t), t);
   
   // Saving the term to map
   t[n] = result;
   return result;
}

// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   map<int, int> t;
   for (int i = 1; i <= n; i++){
      seq[i - 1] = golomb(i, t);
   }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++){
      cout << seq[i] << " ";
   }
   return 0;
}

Output

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6

Time complexity - O(nlogn)

Space complexity - O(n)

Method 3: Dynamic programming

Using dynamic programming, we create a dp table of size n 1 * 1. Then using the properties used above, where the nth number is 1 golomb(n - golomb(golomb(n - 1))), count all the numbers in the sequence and store them in a vector.

pseudocode

procedure golombSeq (n)
   seq[n] = {0}
   seq[0] = 1
      Initialize the dp table of size n+1, 1
   for i = 2 to n
      dp[i] = dp[i - dp[dp[i - 1]]] + 1
   for i = 1 to n
      seq[i-1] = dp[i]
   ans = seq
end procedure

Example: C implementation

In the following program, we use dynamic programming method to solve this problem.

#include <bits/stdc++.h>
using namespace std;
// Function to generate golomb sequence
vector<int> golombSeq(int n){
   vector<int> seq(n, 0);
   
   // First term is 1
   seq[0] = 1;
   vector<int> dp(n + 1, 1);
   for (int i = 2; i <= n; i++){
   
      // Satisfying the property that nth term is 1 + golomb(n - golomb(golomb(n - 1)))
      dp[i] = dp[i - dp[dp[i - 1]]] + 1;
   }
   for (int i = 1; i <= n; i++){
      seq[i - 1] = dp[i];
   }
   return seq;
}
int main(){
   int n = 15;
   vector<int> seq = golombSeq(n);
   cout << "Golomb sequence up to " <<n << " terms: ";
   for (int i = 0; i < n; i++){
      cout << seq[i] << " ";
   }
   return 0;
}

Output

Golomb sequence up to 15 terms: 1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 

in conclusion

In summary, to find the Columbus sequence, we use the properties of the nth number of the Columbus sequence to find all the numbers in the sequence, and use various methods with time complexity ranging from O(n^2) to O(n) .

The above is the detailed content of Golomb sequence. For more information, please follow other related articles on the PHP Chinese website!