#include <bitset> #include <iostream> #include <stdlib.h> #include <string.h> #include <vector> using namespace std; #define MAX (1LL<<25) bitset<MAX> *seen = 0; vector<long long> cc; long long avoid(long long p) { if (!seen->test(1)) { return 1; } long long w=1; for (long long b=2;; b<<=1) { if ((p & b)==0) { if (cc.size()==w) { cc.resize(2*w); } for (long long k=0; k<w; k++) { long long c = cc[w+k] = b + cc[k]; if (c >= MAX) { exit(1); } if (!seen->test(c)) { return c; } } w*=2; } } } #define WANTED 10001 long long a[WANTED]; int main() { seen = new bitset<MAX>; cc.resize(1); cc[0] = 1; // we will only search for odd terms memset(a, 0, sizeof(a)); for (int n=0; n<WANTED; n++) { if (n==0) { a[n] = 0; } else if (n%2) { a[n] = avoid(a[n-1] | a[n+1]); seen->set(a[n]); } if (n) { for (int m=2*n; m<WANTED; m++) { a[m] = 2*a[m/2]; } } cout << n << ' ' << a[n] << endl; } delete seen; return 0; }