login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006995 Numbers whose binary expansion is palindromic.
(Formerly M2403)
114
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

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

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.

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:

A;  # Robert Israel, Aug 17 2014

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

(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

(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: A121820 A238257 A180204 * A163410 A235264 A064896

Adjacent sequences:  A006992 A006993 A006994 * A006996 A006997 A006998

KEYWORD

nonn,base,easy,nice,hear

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified November 26 01:37 EST 2014. Contains 250017 sequences.