私はn番目のバイナリパリンドロームを見つけようとしています

Question

Binary palindromes: numbers whose binary expansion is palindromic.
バイナリパインドーム - >は、バイナリ表現が回文である番号です。
Here is link to the solution with naive approach

私は上記のリンクから読んだので、n番目のバイナリパリンドロームを見つけるための式が得られます。私は解決策を理解してコード化することができません。

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 > 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] 

ここには1つのPythonコードがありますが、このようなすべての回文を生成しています。
n番目のバイナリpalindromeを直接取得するには、プログラムのヘルプが必要です。
次のように：

入力 - > 1 < = N < = 1000000000
機能 - > F（N）
出力 - > n番目のバイナリ回文。

hereという式を使用してより適切な時間にこれを行うことはできますか？

Answer 1

A006995で与えられる再帰アルゴリズムのかなり単純な実装です。それは、より効率的なIバイナリべき乗を実行するためにビットシフトを使用するために

：xは負でない整数である場合、1 << xは2 ** xと同等であるが、実質的に速く（少なくとも、それが標準でPython 2とPython 3の両方でありますCPython）。

また、再帰をより効率的にするために、関数は事前に計算された値を辞書に格納します。これにより、再帰式自体が処理しないn <= 2が簡単に処理できるようになります。

#!/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>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<n<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)<n<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 << k 
    a, c = b >> 1, b << 1 

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

    result = (1 << (2*k - q)) + 1 + (1 << 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:>2}: {1} {1:b} {2}'.format(i, b, c)) 

出力

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 

あなたは、Python 2でこれを実行する必要がある場合はPython 2つの整数がbit_lengthメソッドを持っていないので、あなたは、そのflog2機能を使用することはできません。別のバージョンがあります：

from math import floor, log 

def flog2(n): 
    return int(floor(log(n)/log(2))) 

Answer 2

私は完全なコードを書いていません。私たちは受験アルゴリズム

これらの列がある てみましょう：ビット数、組み合わせ、組み合わせが

• 1 1カウント| 1
• 2 11 | 1
• 3 101 111 | 2
• 4 1001 1001 | 2
• 5 10001 10101 11011 11111 | 4
• 6 100001 101101 110011 11111 | 4

あなたがこのシリーズに従うならば、あなたがesponentiallyそれぞれ2つの段階を上げるしようとしています。ビットカウントが次の組み合わせの量を有するビット数をnとする。2 < <（（n-1）>> 1）。 近い形で可能計算であれば今、私は知らないが、再帰的に、それは指数関数的であるため、非常に高速です： のn-1ビットまでのn数であるとすると、今現在のカウント

int i,n=0,m=0; 
for (i=1;m<nth;i++) 
{ 
    n=m; 
    m+=2<<((i-1)>>1); 
} 

m個あなたは（i + 1）/ 2ビットを100としたchar配列を構築します。0 ... （nth-n）-1（0を基にして-1）バイナリ形式で。とopla！あなたのトークンを鏡映して終了する。 例：12個の要素が必要です 1 + 1 + 2 + 2 + 4 + 4の合計になります。だから、あなたの12番目の要素は6ビットであることが分かります。 5ビットまでは10個の要素があります。したがって、12-10 = 2 2-1 = 1 Youtビットは 100（6ビット/ 2）のようになります。 1 - >バイナリ1を追加します。 100 + 1 = 101 n番目のパリンドロム番号の形式は101101です。奇数ビットカウントでも動作します。特異点1と2のビット数を確認してください