The OEIS is supported by the many generous donors to the OEIS Foundation.
%I M2403 #240 Jun 11 2024 01:41:24
%S 0,1,3,5,7,9,15,17,21,27,31,33,45,51,63,65,73,85,93,99,107,119,127,
%T 129,153,165,189,195,219,231,255,257,273,297,313,325,341,365,381,387,
%U 403,427,443,455,471,495,511,513,561,585,633,645,693,717,765,771,819,843
%N Binary palindromes: numbers whose binary expansion is palindromic.
%C 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
%C 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
%C 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
%C From _Hieronymus Fischer_, Jan 23 2013: (Start)
%C 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.
%C Also: A070939(a(n)) = A070939(n) + A070939(floor(n/3)) - 1, for n <> 2. (End)
%C Rajasekaran, Shallit, & Smith show that this is an additive basis of order 4. - _Charles R Greathouse IV_, Nov 06 2018
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A006995/b006995.txt">Table of n, a(n) for n = 1..10000</a>
%H James Haoyu Bai, Joseph Meleshko, Samin Riasat, and Jeffrey Shallit, <a href="https://arxiv.org/abs/2202.13694">Quotients of Palindromic and Antipalindromic Numbers</a>, arXiv:2202.13694 [math.NT], 2022.
%H William D. Banks and Igor E. Shparlinski, <a href="https://doi.org/10.4064/ba54-2-1">Average Value of the Euler Function on Binary Palindromes</a>, Bulletin Polish Acad. Sci. Math., Vol. 54 (2006), pp. 95-101, <a href="http://faculty.missouri.edu/~bankswd/papers/2006_palindromes_iii.pdf">alternative link</a>.
%H Manfred Madritsch and Stephan Wagner, <a href="https://doi.org/10.1007/s00605-009-0126-y">A central limit theorem for integer partitions</a>, Monatshefte für Mathematik, Vol. 161, No. 1 (2010), pp. 85-114, <a href="https://www.researchgate.net/publication/225845584_A_central_limit_theorem_for_integer_partitions">alternative link</a>. doi:10.1007/s00605-009-0126-y.
%H Kritkhajohn Onphaeng, Tammatada Khemaratchatakumthorn, Phakhinkon Napp Phunphayap, and Prapanpong Pongsriiam, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Phunphayap/phun7.html">Exact Formulas for the Number of Palindromes in Certain Arithmetic Progressions</a>, Journal of Integer Sequences, Vol. 27 (2024), Article 24.4.8. See p. 2.
%H Aayush Rajasekaran, <a href="http://hdl.handle.net/10012/13202">Using Automata Theory to Solve Problems in Additive Number Theory</a>, MS thesis, University of Waterloo, 2018.
%H Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, <a href="https://arxiv.org/abs/1706.10206">Sums of Palindromes: an Approach via Nested-Word Automata</a>, preprint arXiv:1706.10206 [cs.FL], Jun 30 2017.
%H Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, <a href="https://doi.org/10.1007/s00224-019-09929-9">Additive Number Theory via Automata Theory</a>, Theory of Computing Systems, Vol. 64 (2020), pp. 542-567.
%H L. J. Upton, <a href="/A006993/a006993_1.pdf">Letter to N. J. A. Sloane with attachments, Oct. 1993</a>.
%H <a href="/index/Ab#basis_04">Index entries for sequences that are an additive basis</a>, order 4.
%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%H <a href="/index/Pac#palindromes">Index entries for sequences related to palindromes</a>
%F A178225(a(n)) = 1; union of A048700 and A048701. - _Reinhard Zumkeller_, Oct 21 2011
%F From _Hieronymus Fischer_, Dec 31 2008, Jan 10 2012, Feb 18 2012: (Start)
%F 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...:
%F a(1000) = 249903,
%F a(10^4) = 24183069,
%F a(10^5) = 2258634081,
%F a(10^6) = 249410097687,
%F a(10^7) = 24350854001805,
%F a(10^8) = 2229543293296319,
%F a(10^9) = 248640535848971067,
%F a(10^10)= 24502928886295666773.
%F Inequality: (2/9)*n^2 < a(n) < (1/4)*(n+1)^2, if n > 1.
%F lim sup_{n -> oo} a(n)/n^2 = 1/4, lim inf_{n -> oo} a(n)/n^2 = 2/9.
%F For n >= 2, a(2^n-1) = 2^(2n-2) - 1; a(2^n) = 2^(2n-2) + 1;
%F a(2^n+1) = 2^(2n-2) + 2^(n-1) + 1; a(2^n + 2^(n-1)) = 2^(2n-1) + 1.
%F 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:
%F Case 1: If n = 2^(k+1), then p = 0, q = 0, m = 1;
%F 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;
%F Case 3: If n = 2^k + 2^(k-1), then p = 0, q = 1, m = 1;
%F 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.
%F Non-recursive formula:
%F Let n >= 3, m = floor(log_2(n)), p = floor((3*2^(m-1)-1)/n), then
%F 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]
%F 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]
%F 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)].
%F (End)
%F 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 f_1(x) = x^(1/2), and for j > 1,
%F 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
%F A044051(n) = (a(n)+1)/2 for n > 0. - _Reinhard Zumkeller_, Apr 20 2015
%F A145799(a(n)) = a(n). - _Reinhard Zumkeller_, Sep 24 2015
%F Sum_{n>=2} 1/a(n) = A244162. - _Amiram Eldar_, Oct 17 2020
%e a(3) = 3, since 3 = 11_2 is the 3rd symmetric binary number;
%e a(6) = 9, since 9 = 1001_2 is the 6th symmetric binary number.
%p dmax:= 15; # to get all terms with at most dmax binary digits
%p revdigs:= proc(n)
%p local L, Ln, i;
%p L:= convert(n,base,2);
%p Ln:= nops(L);
%p add(L[i]*2^(Ln-i),i=1..Ln);
%p end proc;
%p A:= {0,1}:
%p for d from 2 to dmax do
%p if d::even then
%p A:= A union {seq(2^(d/2)*x + revdigs(x),x=2^(d/2-1)..2^(d/2)-1)}
%p else
%p m:= (d-1)/2;
%p B:={seq(2^(m+1)*x + revdigs(x),x=2^(m-1)..2^m-1)};
%p A:= A union B union map(`+`,B,2^m)
%p fi
%p od:
%p A; # _Robert Israel_, Aug 17 2014
%t palQ[n_Integer, base_Integer] := Module[{idn=IntegerDigits[n, base]}, idn==Reverse[idn]]; Select[Range[1000], palQ[ #, 2]&]
%t Select[ Range[0, 1000], # == IntegerReverse[#, 2] &] (* _Robert G. Wilson v_, Feb 24 2018 *)
%t Select[Range[0, 1000], PalindromeQ[IntegerDigits[#, 2]]&] (* _Jean-François Alcover_, Mar 01 2018 *)
%o (PARI) for(n=0,999,n-subst(Polrev(binary(n)),x,2)||print1(n,",")) \\ _Thomas Buchholz_, Aug 16 2014
%o (PARI) for(n=0,10^3, my(d=digits(n,2)); if(d==Vecrev(d), print1(n,", "))); \\ _Joerg Arndt_, Aug 17 2014
%o (PARI) is_A006995(n)=Vecrev(n=binary(n))==n \\ _M. F. Hasler_, Feb 23 2018
%o (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
%o (Magma) [n: n in [0..850] | Intseq(n,2) eq Reverse(Intseq(n,2))]; // _Bruno Berselli_, Aug 29 2011
%o (Haskell)
%o a006995 n = a006995_list !! (n-1)
%o a006995_list = 0 : filter ((== 1) . a178225) a005408_list
%o -- _Reinhard Zumkeller_, Oct 21 2011
%o (Smalltalk)
%o A006995
%o "Answer the n-th binary palindrome
%o (nonrecursive implementation)"
%o | m n a b c d k2 |
%o n := self.
%o n = 1 ifTrue: [^0].
%o n = 2 ifTrue: [^1].
%o m := n integerFloorLog: 2.
%o c := 2 raisedToInteger: m - 1.
%o n >= (3 * c)
%o ifTrue:
%o [a := n - (3 * c).
%o d := 2 * c * c.
%o b := d + 1.
%o k2 := 1.
%o 1 to: m - 1
%o do:
%o [:k |
%o k2 := 2 * k2.
%o b := b + (a * k2 // c \\ 2 * (k2 + (d // k2)))]]
%o ifFalse:
%o [a := n - (2 * c).
%o d := c * c.
%o b := d + 1 + (n \\ 2 * c).
%o k2 := 1.
%o 1 to: m - 2
%o do:
%o [:k |
%o k2 := 2 * k2.
%o b := b + (a * k2 // c \\ 2 * (k2 + (d // k2)))]].
%o ^b // by _Hieronymus Fischer_, Feb 15 2013
%o (Sage)
%o def palgenbase2(): # generator of palindromes in base 2
%o yield 0
%o x, n, n2 = 1, 1, 2
%o while True:
%o for y in range(n,n2):
%o s = format(y,'b')
%o yield int(s+s[-2::-1],2)
%o for y in range(n,n2):
%o s = format(y,'b')
%o yield int(s+s[::-1],2)
%o x += 1
%o n *= 2
%o n2 *= 2 # _Chai Wah Wu_, Jan 07 2015
%o (Sage)
%o [n for n in (0..843) if Word(n.digits(2)).is_palindrome()] # _Peter Luschny_, Sep 13 2018
%o (Python)
%o from itertools import count, islice, product
%o def bin_pals(): # generator of binary palindromes in base 10
%o yield from [0, 1]
%o digits, midrange = 2, [[""], ["0", "1"]]
%o for digits in count(2):
%o for p in product("01", repeat=digits//2-1):
%o left = "1"+"".join(p)
%o for middle in midrange[digits%2]:
%o yield int(left + middle + left[::-1], 2)
%o print(list(islice(bin_pals(), 58))) # _Michael S. Branicky_, Jan 09 2023
%o (Python)
%o def A006995(n):
%o if n == 1: return 0
%o a = 1<<(l:=n.bit_length()-2)
%o m = a|(n&a-1)
%o return (m<<l+1)+int(bin(m)[-1:1:-1]or'0',2) if a&n else (m<<l)+int(bin(m)[-2:1:-1]or'0',2) # _Chai Wah Wu_, Jun 10 2024
%Y See A057148 for the binary representations.
%Y Cf. A178225, A005408, A164126, A154809 (complement).
%Y Cf. A002113, A048700, A048701, A206913, A206914, A244162.
%Y Even numbers that are not the sum of two terms: A241491, A261678, A262556.
%Y Cf. A145799.
%Y Primes: A016041 and A117697.
%Y Cf. A000051 (a subsequence).
%K nonn,base,easy,nice,hear
%O 1,3
%A _N. J. A. Sloane_, _Robert G. Wilson v_, _Mira Bernstein_, L. J. Upton
%E Edited and extended by _Hieronymus Fischer_, Feb 21 2012
%E Edited by _M. F. Hasler_, Feb 23 2018