Skip to content

Instantly share code, notes, and snippets.

@ramntry
Created January 23, 2022 07:31
Embed
What would you like to do?
Van Eck's sequence | https://oeis.org/A181391
#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";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment