|
| |
|
|
A006995
|
|
Numbers whose binary expansion is palindromic.
(Formerly M2403)
|
|
98
|
|
|
|
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
|
A178225(a(n)) = 1; union of A048700 and A048701. [Reinhard Zumkeller, Oct 21 2011]
If b is a binary palindrome then both terms (2^(m+1)+1)*b and 2^(m+1)+2^m-b are palindromic, too, where m=floor(log_2(b)) and b>1. - 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 greatest binary palindrome <= the n-th non-binary-palindrom is that binary palindrome with number A154809(n)-n+1. The corresponding formula identity is: A206913(A154809(n)) = A006995(A154809(n)-n+1). - Hieronymus Fischer, Mar 18 2012
Contribution from Hieronymus Fischer, Jan 23 2013 (Start):
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.
Also: A070939(a(n)) = A070939(n) + A070939(floor(n/3)) - 1, for n<>2. (End)
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..10000
Index entries for sequences related to binary expansion of n
Index entries for sequences related to palindromes
|
|
|
FORMULA
|
Comments from Hieronymus Fischer, Dec 31 2008, Jan 10 2012, Feb 18 2012 (Start):
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 a(n)/n^2=1/4 for n-->infinity.
lim inf a(n)/n^2=2/9 for n-->infinity.
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 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;
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 +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)).
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).
Inversion formula: If b>0 is any binary palindrome, then the index n for which a(n)=b is
n=palindromicIndexOf(b)=(((5-(-1)^m)/2) + sum_{k=1...floor(m/2)} (floor(b/2^k) mod 2)/2^k))*2^floor(m/2), where m=floor(log_2(b)).
(End)
G.f.: g(x)=x^2+3x^3+sum_{j=1..infinity}(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.
|
|
|
MATHEMATICA
|
palQ[n_Integer, base_Integer] := Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], palQ[ #, 2]&]
|
|
|
PROG
|
(PARI) for(n=1, 1000, l=length(binary(n)); b=binary(n); if(sum(i=1, l, abs(component(b, i)-component(b, l+1-i)))==0, print1(n, ", ")))
(PARI) for(i=0, 999, if(vecextract(t=binary(i), "-1..1")==t, print1(i", "))) - M. F. Hasler, Dec 17 2007
(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
-- Reinhard Zumkeller, Oct 21 2011
(Smalltalk)
A006995
"Answer the n-th binary palindrome
(non recursive 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)))]].
^b // by Hieronymus Fischer, Feb 15 2013
|
|
|
CROSSREFS
|
See A057148 for the binary representations.
Cf. A178225, A005408, A164126, A154809 (complement).
Sequence in context: A145388 A121820 A180204 * A163410 A064896 A076188
Adjacent sequences: A006992 A006993 A006994 * A006996 A006997 A006998
|
|
|
KEYWORD
|
nonn,base,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane, Robert G. Wilson v, Mira Bernstein, L. J. Upton
|
|
|
EXTENSIONS
|
Edited and extended by Hieronymus Fischer, Feb 21 2012
|
|
|
STATUS
|
approved
|
| |
|
|
