Van Eck's sequence | https://oeis.org/A181391

van-ecks-seq.cpp

#include <iostream>
#include <vector>

class Tracker {
public:
  void record(int val, int index);
  int get_last_index(int val);
  std::pair<int, int> get_stats() const;

private:
  void grow_if_necessary(int val);
  std::vector<int> table;
};

void Tracker::grow_if_necessary(int val) {
  if (__builtin_expect(val >= table.size(), 0)) {
    table.resize(val + 1, -1);
  }
}

void Tracker::record(int val, int index) {
  grow_if_necessary(val);
  table[val] = index;
}

int Tracker::get_last_index(int val) {
  grow_if_necessary(val);
  return table[val];
}

std::pair<int, int> Tracker::get_stats() const {
  int max = -1;
  int first_missing = -1;
  for (int val = 0, end = table.size(); val < end; ++val) {
    if (table[val] != -1)
      max = std::max(max, val);
    else {
      if (first_missing == -1)
        first_missing = val;
    }
  }
  return std::make_pair(max, first_missing);
}

int main() {
  int counter = 0;
  std::cin >> counter;

  int curr_val = 0;
  Tracker tracker;
  for (int i = 0; i < counter - 1; ++i) {
    if (__builtin_expect(i < 100 || (counter - i) < 100, 0))
      std::cout << curr_val << "\t";
    else if (__builtin_expect(i == 100, 0))
      std::cout << "...\n...\t";
    int last_index = tracker.get_last_index(curr_val);
    int next_val = (last_index == -1) ? 0 : (i - last_index);
    tracker.record(curr_val, i);
    curr_val = next_val;
  }
  if (counter > 0) {
    tracker.record(curr_val, 0);
    std::cout << curr_val << "\n";
  }
  auto stats = tracker.get_stats();
  std::cout << "Max: " << stats.first << "\n";
  std::cout << "First Missing: " << stats.second << "\n";
}