A006995 Binary palindromes: numbers whose binary expansion is palindromic.
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
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
- T. D. Noe, Table of n, a(n) for n = 1..10000
- James Haoyu Bai, Joseph Meleshko, Samin Riasat, and Jeffrey Shallit, Quotients of Palindromic and Antipalindromic Numbers, arXiv:2202.13694 [math.NT], 2022.
- William D. Banks and Igor E. Shparlinski, Average Value of the Euler Function on Binary Palindromes, Bulletin Polish Acad. Sci. Math., Vol. 54 (2006), pp. 95-101, alternative link.
- Manfred Madritsch and Stephan Wagner, A central limit theorem for integer partitions, Monatshefte für Mathematik, Vol. 161, No. 1 (2010), pp. 85-114, alternative link. doi:10.1007/s00605-009-0126-y.
- Kritkhajohn Onphaeng, Tammatada Khemaratchatakumthorn, Phakhinkon Napp Phunphayap, and Prapanpong Pongsriiam, Exact Formulas for the Number of Palindromes in Certain Arithmetic Progressions, Journal of Integer Sequences, Vol. 27 (2024), Article 24.4.8. See p. 2.
- 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.
- Aayush Rajasekaran, Jeffrey Shallit and Tim Smith, Additive Number Theory via Automata Theory, Theory of Computing Systems, Vol. 64 (2020), pp. 542-567.
- L. J. Upton, Letter to N. J. A. Sloane with attachments, Oct. 1993.
- Index entries for sequences that are an additive basis, order 4.
- Index entries for sequences related to binary expansion of n
- Index entries for sequences related to palindromes
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<
-
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<
-
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
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
Comments