I am trying to find the nth binary palindrome
<p><a href="https://oeis.org/A006995" rel="nofollow">Binary palindromes: numbers whose binary expansion is palindromic.</a> <br>
Binary Palindrome -> is a number whose binary representation is a palindrome. <br>
<a href="http://ideone.com/CfQZuH" rel="nofollow">Here is link to the solution with naive approach</a></p>

<p>I have read from above link and it give a formula to find the nth binary palindrome. I am unable to understand and thus code the solution. </p>

<pre><code>def palgenbase2(): # generator of palindromes in base 2
    #yield 0
    x, n, n2 = 1, 1, 2
    m = 1;
    while True:
        for y in range(n, n2):
            s = format(y, 'b')
            yield int(s+s[-2::-1], 2)
        for y in range(n, n2):
            s = format(y, 'b')
            yield int(s+s[::-1], 2)
        x += 1
        n *= 2
        n2 *= 2
        if n2 &gt; 1000000000:
            break

ans = {}

for i,j in  enumerate(palgenbase2()):
    print i,j
    ans[i]=j

with open("output","a") as f:
    f.write(ans)

#use the saved output to give answer to query later
#this will work but it takes too much time.

n = int(raw_input())
for c in range(0,n):
    z = int(raw_input())
    print ans[z]
</code></pre>

<p>Here is one Python code but it is generating all such palindromes.<br>
I need help in the program to get the nth binary palindrome directly.<br>
as follows:</p>

<blockquote>
  <p>Input -> 1 &lt;= n &lt;= 1000000000<br>
  Function -> f(n)<br>
  output -> nth binary palindrome.</p>
</blockquote>

<p>Can we do this in better time using the formula mentioned <a href="https://oeis.org/A006995" rel="nofollow">here</a>?</p>

<p>I am not going to write the full code.
Let us exam the algorithm</p>

<p>These columns are : bit count , combinations, combinations count</p>

<ul>
<li>1  1        | 1  </li>
<li>2  11       | 1</li>
<li>3 101 111   | 2</li>
<li>4 1001 1001 | 2</li>
<li>5 10001 10101 11011 11111 |4</li>
<li>6 100001 101101 110011 11111 |4</li>
</ul>

<p>if you follow this series you are going to increase esponentially each two step. Let n be the bit count wich bit count has the following amount of combinations: 2&lt;&lt;((n-1)>>1) . 
Now I do not know if is possible compute it in close form but recursively is very fast since it is exponential :
 let n be the count until the n-1 bit and m the current count</p>

<pre><code>int i,n=0,m=0;
for (i=1;m&lt;nth;i++)
{
   n=m;
   m+=2&lt;&lt;((i-1)&gt;&gt;1);
}
</code></pre>

<p>Now you know how many bits are required: i</p>

<p>You build a char array with (i+1)/2 bits as 100...0
You add (nth-n)-1 (-1 because is 0 based) in binary form. And opla! you mirror your token and end.
Example: you need the 12 element
you are going to sum 1+1+2+2+4+4 . So you know your 12th element has 6 bits.
Until 5 bits you have 10 elements. So 12-10=2  2-1=1
 Yout bit looks like
 100   ( 6 bit /2)
 you add 1-> binary 1
 100+1=101
Your nth palindrom number has the follow form 101101. It works also with odd bit count. Check for the singularity 1 and 2 bit count</p>

python algorithm binary palindrome