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>Here's a fairly straight-forward implementation of the recursive algorithm given at <a href="https://oeis.org/A006995" rel="nofollow">A006995</a>.</p>

<p>To make it more efficient I use bit shifting to perform binary exponentiation: when <code>x</code> is a non-negative integer, <code>1 &lt;&lt; x</code> is equivalent to <code>2 ** x</code> but substantially faster (at least, it is in both Python 2 and Python 3 on standard CPython).</p>

<p>Also, to make the recursion more efficient, the function stores previously calculated values in a dictionary. This also lets us easily handle when <code>n &lt;= 2</code>, which the recursive formula itself does not handle.</p>

<pre><code>#!/usr/bin/env python

''' Binary palindromes

    Find (non-negative) integers which are palindromes when written in binary

    See http://stackoverflow.com/q/39675412/4014959
    and https://oeis.org/A006995

    Written by PM 2Ring 2016.09.24

    Recursion for n&gt;2: a(n)=2^(2k-q)+1+2^p*a(m), where k:=floor(log_2(n-1)), and p, q and m are determined as follows:

    Case 1: If n=2^(k+1), then p=0, q=0, m=1;

    Case 2: If 2^k&lt;n&lt;2^k+2^(k-1), then set i:=n-2^k, p=k-floor(log_2(i))-1, q=2, m=2^floor(log_2(i))+i;

    Case 3: If n=2^k+2^(k-1), then p=0, q=1, m=1;

    Case 4: If 2^k+2^(k-1)&lt;n&lt;2^(k+1), then set j:=n-2^k-2^(k-1), p=k-floor(log_2(j))-1, q=1, m=2*2^floor(log_2(j))+j; 
'''

#Fast Python 3 version of floor(log2(n))
def flog2(n):
    return n.bit_length() - 1

def binpal(n, cache={1:0, 2:1, 3:3}):
    if n in cache:
        return cache[n]

    k = flog2(n - 1)
    b = 1 &lt;&lt; k
    a, c = b &gt;&gt; 1, b &lt;&lt; 1

    if n == c:
        p, q, m = 0, 0, 1
    elif b &lt; n &lt; a + b:
        i = n - b
        logi = flog2(i)
        p, q, m = k - logi - 1, 2, (1 &lt;&lt; logi) + i
    elif n == a + b:
        p, q, m = 0, 1, 1
    else:
        #a + b &lt; n &lt; c
        i = n - a - b
        logi = flog2(i)
        p, q, m = k - logi - 1, 1, (2 &lt;&lt; logi) + i

    result = (1 &lt;&lt; (2*k - q)) + 1 + (1 &lt;&lt; p) * binpal(m)
    cache[n] = result
    return result

def palgenbase2(): 
    ''' generator of binary palindromes '''
    yield 0
    x, n, n2 = 1, 1, 2
    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

gen = palgenbase2()

for i in range(1, 30):
    b = next(gen)
    c = binpal(i)
    print('{0:&gt;2}: {1} {1:b} {2}'.format(i, b, c))
</code></pre>

<p><strong>output</strong></p>

<pre><code> 1: 0 0 0
 2: 1 1 1
 3: 3 11 3
 4: 5 101 5
 5: 7 111 7
 6: 9 1001 9
 7: 15 1111 15
 8: 17 10001 17
 9: 21 10101 21
10: 27 11011 27
11: 31 11111 31
12: 33 100001 33
13: 45 101101 45
14: 51 110011 51
15: 63 111111 63
16: 65 1000001 65
17: 73 1001001 73
18: 85 1010101 85
19: 93 1011101 93
20: 99 1100011 99
21: 107 1101011 107
22: 119 1110111 119
23: 127 1111111 127
24: 129 10000001 129
25: 153 10011001 153
26: 165 10100101 165
27: 189 10111101 189
28: 195 11000011 195
29: 219 11011011 219
</code></pre>

<p>If you need to run this on Python 2 you won't be able to use that <code>flog2</code> function, since Python 2 integers do not have the <code>bit_length</code> method. Here's an alternative version:</p>

<pre><code>from math import floor, log

def flog2(n):
    return int(floor(log(n) / log(2)))
</code></pre>

python algorithm binary palindrome