#include <iostream>
#include <cmath>

/************************************
 * A function for very quickly
 * calculating
 *  |    ___ n |
 *  |_ \/ 2   _|
 *
 * for values up to 61.
 *
 * For powers beyond 61, it returns
 * the floor(sqrt(2)^61), the largest
 * power of sqrt(2) which is
 * representable.
 ************************************/

int root2pow( int n ) {
	// The result is < 1; therefore return 0.
	if ( n < 0 ) {
		return 0;
	}

	// Return the largest power of sqrt(2)
	if ( n > 61 ) {
		return 1518500249;
	}

	// Odd powers are calculated by dividing
	//     floor( sqrt(2)*2^30 )
	// by an appropriate power of 2; and
	// Even powers are calculated using bit shifting.

	if ( n & 1 ) {
		return 1518500249 >> (30 - (n >> 1));
	} else {
		return 1 << (n >> 1);
	}
}

int main() {
	for ( int i = 0; i <= 64; ++i ) {
		int v = static_cast<int>(
			std::floor( std::pow( std::sqrt(2.0), i ) )
		);
		std::cout << i << '\t'
		    << root2pow( i ) << '\t'
		    << v << '\t'
		    << v - root2pow( i )
		    << std::endl;
	}

	return 0;
}