|
| |
|
|
A006995
|
|
Binary palindromes: numbers whose binary expansion is palindromic.
(Formerly M2403)
|
|
229
|
|
|
|
0, 1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 85, 93, 99, 107, 119, 127, 129, 153, 165, 189, 195, 219, 231, 255, 257, 273, 297, 313, 325, 341, 365, 381, 387, 403, 427, 443, 455, 471, 495, 511, 513, 561, 585, 633, 645, 693, 717, 765, 771, 819, 843
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
If b > 1 is a binary palindrome then both (2^(m+1) + 1)*b and 2^(m+1) + 2^m - b are also, where m = floor(log_2(b)). - Hieronymus Fischer, Feb 18 2012
Floor and ceiling: If d > 0 is any natural number, then A206913(d) is the greatest binary palindrome <= d and A206914(d) is the least binary palindrome >= d. - Hieronymus Fischer, Feb 18 2012
The number of binary digits of a(n) is A070939(a(n)) = 1 + floor(log_2(n)) + floor(log_2(n/3)), for n > 1.
Rajasekaran, Shallit, & Smith show that this is an additive basis of order 4. - Charles R Greathouse IV, Nov 06 2018
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
|
|
|
FORMULA
|
Written as a decimal, a(10^n) has 2*n digits. For n > 1, the decimal expansion of a(10^n) starts with 22..., 23... or 24...:
a(1000) = 249903,
a(10^4) = 24183069,
a(10^5) = 2258634081,
a(10^6) = 249410097687,
a(10^7) = 24350854001805,
a(10^8) = 2229543293296319,
a(10^9) = 248640535848971067,
a(10^10)= 24502928886295666773.
Inequality: (2/9)*n^2 < a(n) < (1/4)*(n+1)^2, if n > 1.
lim sup_{n -> oo} a(n)/n^2 = 1/4, lim inf_{n -> oo} a(n)/n^2 = 2/9.
For n >= 2, a(2^n-1) = 2^(2n-2) - 1; a(2^n) = 2^(2n-2) + 1;
a(2^n+1) = 2^(2n-2) + 2^(n-1) + 1; a(2^n + 2^(n-1)) = 2^(2n-1) + 1.
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 p = k-floor(log_2(i))-1 with i = n-2^k, 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 p = k-floor(log_2(j))-1 with j = n-2^k-2^(k-1), q = 1, m = 2*2^floor(log_2(j))+j.
Non-recursive formula:
Let n >= 3, m = floor(log_2(n)), p = floor((3*2^(m-1)-1)/n), then
a(n) = 2^(2*m-1-p) + 1 + p*(1-(-1)^n)*2^(m-1-p) + sum_{k=1 .. m-1-p} (floor((n-(3-p)*2^(m-1))/2^(m-1-k)) mod 2)*(2^k+2^(2*m-1-p-k)). [Typo at the last exponent of the third sum term eliminated by the author, Sep 05 2018]
a(n) = 2^(2*m-2) + 1 + 2*floor((n-2^m)/2^(m-1)) + 2^(m-1)*floor((1/2)*min(n+1-2^m,2^(m-1)+1)) + 3*2^(m-1)*floor((1/2)*max(n+1-3*2^(m-1),0)) + 3*sum_{j=2 .. m-1} floor((n+2^(j-1)-2^m)/2^j)*2^(m-j). [Seems correct for n > 3. - The Editors]
Inversion formula: The index of any binary palindrome b = a(n) > 0 is n = palindromicIndex(b) = ((5-(-1)^m)/2 + Sum_{k=1..[m/2]} ([b/2^k] mod 2)/2^k)*2^[m/2], where [.] = floor(.) and m = [log_2(b)].
(End)
G.f.: g(x) = x^2 + 3x^3 + sum_{j=1..oo}( 3*2^j*(1-x^floor((j+1)/2))/(1-x)*x^((1/2)-floor((j+1)/2)) + f_j(x) - f_j(1/x))*x^(2*2^floor(j/2)+3*2^floor((j-1)/2)-(1/2)), where the f_j(x) are defined as follows:
f_1(x) = x^(1/2), and for j > 1,
f_j(x) = x^(1/2)*sum_{i=0..2^floor((j-1)/2)-1}((3+(1/2)*sum_{k=1..floor((j-1)/2)}(1-(-1)^floor(2i/2^k))*b(j,k))*x^i), where b(j,k) = 2^(floor((j-1)/2)-k)*((3+(-1)^j)*2^(2*k+1)+4) for k > 1, and b(j,1) = (2+(-1)^j)*2^(floor((j-1)/2)+1). - Hieronymus Fischer, Apr 04 2012
|
|
|
EXAMPLE
|
a(3) = 3, since 3 = 11_2 is the 3rd symmetric binary number;
a(6) = 9, since 9 = 1001_2 is the 6th symmetric binary number.
|
|
|
MAPLE
|
dmax:= 15; # to get all terms with at most dmax binary digits
revdigs:= proc(n)
local L, Ln, i;
L:= convert(n, base, 2);
Ln:= nops(L);
add(L[i]*2^(Ln-i), i=1..Ln);
end proc;
A:= {0, 1}:
for d from 2 to dmax do
if d::even then
A:= A union {seq(2^(d/2)*x + revdigs(x), x=2^(d/2-1)..2^(d/2)-1)}
else
m:= (d-1)/2;
B:={seq(2^(m+1)*x + revdigs(x), x=2^(m-1)..2^m-1)};
A:= A union B union map(`+`, B, 2^m)
fi
od:
|
|
|
MATHEMATICA
|
palQ[n_Integer, base_Integer] := Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], palQ[ #, 2]&]
Select[ Range[0, 1000], # == IntegerReverse[#, 2] &] (* Robert G. Wilson v, Feb 24 2018 *)
|
|
|
PROG
|
(PARI) for(n=0, 999, n-subst(Polrev(binary(n)), x, 2)||print1(n, ", ")) \\ Thomas Buchholz, Aug 16 2014
(PARI) for(n=0, 10^3, my(d=digits(n, 2)); if(d==Vecrev(d), print1(n, ", "))); \\ Joerg Arndt, Aug 17 2014
(PARI) A006995(n, m=logint(n, 2), c=1<<(m-1), a, d)={if(n>=3*c, a=n-3*c; d=2*c^2, a=n-2*c; n%2*c+d=c^2)+sum(k=1, m-2^(n<3*c), if(bittest(a, m-1-k), 1<<k+d>>k))+(n>2)} \\ Based on Fischer's smalltalk program. - M. F. Hasler, Feb 23 2018
(Magma) [n: n in [0..850] | Intseq(n, 2) eq Reverse(Intseq(n, 2))]; // Bruno Berselli, Aug 29 2011
(Haskell)
a006995 n = a006995_list !! (n-1)
a006995_list = 0 : filter ((== 1) . a178225) a005408_list
(Smalltalk)
"Answer the n-th binary palindrome
(nonrecursive implementation)"
| m n a b c d k2 |
n := self.
n = 1 ifTrue: [^0].
n = 2 ifTrue: [^1].
m := n integerFloorLog: 2.
c := 2 raisedToInteger: m - 1.
n >= (3 * c)
ifTrue:
[a := n - (3 * c).
d := 2 * c * c.
b := d + 1.
k2 := 1.
1 to: m - 1
do:
[:k |
k2 := 2 * k2.
b := b + (a * k2 // c \\ 2 * (k2 + (d // k2)))]]
ifFalse:
[a := n - (2 * c).
d := c * c.
b := d + 1 + (n \\ 2 * c).
k2 := 1.
1 to: m - 2
do:
[:k |
k2 := 2 * k2.
b := b + (a * k2 // c \\ 2 * (k2 + (d // k2)))]].
(Sage)
def palgenbase2(): # generator of palindromes in base 2
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
(Sage)
[n for n in (0..843) if Word(n.digits(2)).is_palindrome()] # Peter Luschny, Sep 13 2018
(Python)
from itertools import count, islice, product
def bin_pals(): # generator of binary palindromes in base 10
yield from [0, 1]
digits, midrange = 2, [[""], ["0", "1"]]
for digits in count(2):
for p in product("01", repeat=digits//2-1):
left = "1"+"".join(p)
for middle in midrange[digits%2]:
yield int(left + middle + left[::-1], 2)
|
|
|
CROSSREFS
|
See A057148 for the binary representations.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
