#include <bitset> #include <iostream> #include <vector> using namespace std; #define MAX (1LL<<25) bitset<MAX> *seen = 0; vector<long long> cc; long long other(long long p) { seen->set(p); long long w=1; for (long long b=1;; 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) { return -1; } if (!seen->test(c)) { return c; } } w*=2; } } } #define WANTED 10001 long long a[WANTED]; int main() { seen = new bitset<MAX>; seen->set(0); // only positive integers cc.resize(1); long long v=1; for (long long n=1; v>0 && n<WANTED; n++) { a[n] = v; long long nb = 0; for (long long m=1; m<=n; m++) { if ((a[m] & a[n])==0) { nb++; } } cout << n << ' ' << nb << endl; v = other(v); } delete seen; return 0; }