cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A006995 Binary palindromes: numbers whose binary expansion is palindromic.

Original entry on oeis.org

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
Offset: 1

Views

Author

N. J. A. Sloane, Robert G. Wilson v, Mira Bernstein, L. J. Upton

Keywords

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

Examples

			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.

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

See A057148 for the binary representations.
Cf. A178225, A005408, A164126, A154809 (complement).
Cf. A002113, A048700, A048701, A206913, A206914, A244162.
Even numbers that are not the sum of two terms: A241491, A261678, A262556.
Cf. A145799.
Primes: A016041 and A117697.
Cf. A000051 (a subsequence).

Programs

  • Haskell
    a006995 n = a006995_list !! (n-1)
a006995_list = 0 : filter ((== 1) . a178225) a005408_list
-- Reinhard Zumkeller, Oct 21 2011
  • Magma
    [n: n in [0..850] | Intseq(n,2) eq Reverse(Intseq(n,2))];  // Bruno Berselli, Aug 29 2011
  • 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 *)
  • 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))+(n>2)} \\ Based on Fischer's smalltalk program. - M. F. Hasler, Feb 23 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)
print(list(islice(bin_pals(), 58))) # Michael S. Branicky, Jan 09 2023
  • Python
    def A006995(n):
    if n == 1: return 0
    a = 1<<(l:=n.bit_length()-2)
    m = a|(n&a-1)
    return (m<Chai Wah Wu, Jun 10 2024
  • 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
        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
  • 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

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
Sum_{n>=2} 1/a(n) = A244162. - Amiram Eldar, Oct 17 2020

Extensions

Edited and extended by Hieronymus Fischer, Feb 21 2012
Edited by M. F. Hasler, Feb 23 2018

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

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