Вот довольно простая реализация рекурсивного алгоритма, приведенная по адресу A006995.
Чтобы сделать его более эффективным, я использую битовый сдвиг для выполнения двоичного возведения в степень: когда 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, вы не сможете использовать эту функцию flog2, поскольку целые числа Python 2 не имеют метода bit_length. Вот альтернативная версия:
from math import floor, log
def flog2(n):
return int(floor(log(n) / log(2)))
person
PM 2Ring
schedule
24.09.2016
sдля результата - person dsgdfg schedule 24.09.2016numberбинарным палиндромом. Но lordzuko нужна функция, например,bin_palindrome(n), которая возвращает n-й бинарный палиндром, не выполняя перебор всех предыдущих бинарных палиндромов. - person PM 2Ring schedule 24.09.2016Recursion for n>2: a(n)=2^(2k-q)+1+2^p*a(m). Но в любом случае, надеюсь, мой ответ сделает это немного яснее. - person PM 2Ring schedule 24.09.2016binpal(1000000000), но опубликованный мной код может сделать это менее чем за 0,12 секунды на моей старой машине с частотой 2 ГГц. - person PM 2Ring schedule 24.09.2016