-- Reverse-iterate (X+1)(4X+1) mod 2^BITS.

-- State is tuple(A,B,C) satisfying A*x²+B*x=c + 2^n*k

-- How many bits are there in RNG state?
BITS = 30

--Wrap to this when substracting 1, in case number is 0.
WARPSCALE = math.pow(2, BITS) - 1;

-- This returns 0 if last bit is 0, otherwise 1.
last_bit = function(state)
	return state.C % 2;
end

-- This returns new state
update_state = function(state)
	-- A*x²+B*x=c + 2^n*k
	-- 2A*x²+B*x = c/2 + 2^(n-1)*k
	if state.B % 2 == 0 then
		error("Internal error: B is even");
	end
	if state.C % 2 == 0 then
		-- Even. Last bit was 0.
		return {["A"] = 2 * state.A, ["B"] = state.B, ["C"] = state.C / 2};
	else
		-- Odd. Last bit was 1.
		return {["A"] = 2 * state.A, ["B"] = 2 * state.A + state.B, ["C"] = (state.C - state.A - state.B) / 2 };
	end
end

-- Iterate (
reverse_iterate = function(number)
	if number == 0 then
		number = WARPSCALE;
	else
		number = number - 1;
	end
	local state = {["A"] = 4, ["B"] = 5, ["C"] =  number};
	local i;
	local l = 0;
	local scale = 1;
	for i = 0, BITS - 1 do
		l = l + scale * last_bit(state);
		state = update_state(state);
		scale = scale * 2;
	end
	return l;
end

print(reverse_iterate(tonumber(arg[1])));