#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

int decimal(vector<int> _Double);
vector<int> binary(int _Number);

vector<int> get_inverted(vector<int> p) {
  const int k = p.size();

  if (k == 1) return binary(2);

  vector<int> p_copy(k / 2);
  for (int i = 0; i < p_copy.size(); i++) p_copy[i] = p[i];
  vector<int> c = get_inverted(p_copy);

  const int right_side =
      decimal(c) * pow(2, 3 * k / 2) - pow(decimal(c), 2) * decimal(p);

  vector<int> d = binary(right_side);
  if (d.size() != 2 * k) d.insert(d.begin(), 0);

  vector<int> a;
  for (int i = 0; i < k + 1; i++) a.push_back(d[i]);

  for (int i = 2; i >= 0; i--) {
    int left = (decimal(a) + pow(2, i)) * decimal(p);
    int right = pow(2, 2 * k - 1);
    if (left < right) {
      a = binary(decimal(a) + pow(2, i));
    }
  }

  return a;
}

int main() {
  // Initial number
  /*int number = 153;
  cout << "My: " << setw(4)
       << decimal(binary(decimal(get_inverted(binary(153)))));*/

  for (int i = 1; i < 5000; i++) {
    if (decimal(binary(decimal(get_inverted(binary(i))))) !=
        decimal(binary(pow(2, 2 * binary(i).size() - 1) / i)))
      cout << " Number = " << i << " My: " << setw(4)
           << decimal(binary(decimal(get_inverted(binary(i)))))
           << " Correct: " << setw(4)
           << decimal(binary(pow(2, 2 * binary(i).size() - 1) / i)) << endl;
  }
  return 0;
}

int decimal(vector<int> _Double) {
  int result = 0;

  for (int i = 0; i < _Double.size(); i++)
    result += _Double[i] * pow(2, static_cast<int>(_Double.size()) - i - 1);
  return result;
}

vector<int> binary(int _Number) {
  vector<int> result;
  for (int i = 0; _Number > 0; i++) {
    result.insert(result.begin(), _Number % 2);
    _Number /= 2;
  }
  return result;
}