self-describing-sequence.cc

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

int _golomb(vector<int>& golomb_values, int n);

int golomb(vector<int>& golomb_values, int n) {
  if (golomb_values.size() < n) {
    int next = _golomb(golomb_values, n);
    golomb_values.push_back(next);
  }
  return golomb_values.at(n - 1);
}

int _golomb(vector<int>& golomb_values, int n) {
  return 1 + golomb(golomb_values,
                    n - golomb(golomb_values,
                               golomb(golomb_values, n - 1)));
}

int main(int argc, char* argv[]) {
  if (argc <= 1) return 1;

  stringstream ss(argv[1]);
  int n;
  ss >> n;

  vector<int> golomb_values;
  golomb_values.reserve(n);
  golomb_values.push_back(1);

  for (int i = 2; i < n; i++) {
    golomb(golomb_values, i);
  }
  cout << "f(" << n << ") = " << golomb(golomb_values, n) << endl;
  return 0;
}