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

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006995 Binary palindromes: numbers whose binary expansion is palindromic.
(Formerly M2403)
156
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 greatest binary palindrome <= the n-th non-binary-palindrome 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)

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

T. D. Noe, Table of n, a(n) for n = 1..10000

M. Madritsch, S. Wagner, A central limit theorem for integer partitions, Monatsh. Math. 161 (1) (2010) 85-114 doi:10.1007/s00605-009-0126-y.

Aayush Rajasekaran, Using Automata Theory to Solve Problems in Additive Number Theory, MS thesis, University of Waterloo, 2018.

Aayush Rajasekaran, Jeffrey Shallit, and Tim Smith, Sums of Palindromes: an Approach via Nested-Word Automata, preprint arXiv:1706.10206 [cs.FL], Jun 30 2017.

L. J. Upton, Letter to N. J. A. Sloane with attachments, Oct. 1993

Index entries for sequences related to binary expansion of n

Index entries for sequences related to palindromes

FORMULA

A178225(a(n)) = 1; union of A048700 and A048701. - Reinhard Zumkeller, Oct 21 2011

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_{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

A044051(n) = (a(n)+1)/2 for n > 0. - Reinhard Zumkeller, Apr 20 2015

A145799(a(n)) = a(n). - Reinhard Zumkeller, Sep 24 2015

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

Select[ Range[0, 1000], # == IntegerReverse[#, 2] &] (* Robert G. Wilson v, Feb 24 2018 *)

Select[Range[0, 1000], PalindromeQ[IntegerDigits[#, 2]]&] (* Jean-Fran├žois Alcover, Mar 01 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) is_A006995(n)=Vecrev(n=binary(n))==n \\ M. F. Hasler, Feb 23 2018

(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

-- Reinhard Zumkeller, Oct 21 2011

(Smalltalk)

A006995

"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)))]].

^b // by Hieronymus Fischer, Feb 15 2013

(Python)

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

........n2 *= 2 # Chai Wah Wu, Jan 07 2015

(Sage)

[n for n in (0..843) if Word(n.digits(2)).is_palindrome()] # Peter Luschny, Sep 13 2018

CROSSREFS

See A057148 for the binary representations.

Cf. A178225, A005408, A164126, A154809 (complement).

Cf. A002113, A048700, A048701, A206913, A206914.

Even numbers that are not the sum of two terms: A241491, A261678, A262556.

Cf. A145799.

Primes: A016041 and A117697.

Sequence in context: A238257 A305409 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

Edited by M. F. Hasler, Feb 23 2018

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 19 03:28 EST 2018. Contains 318245 sequences. (Running on oeis4.)