title: I am trying to find the nth binary palindrome
body: <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>