A044051 -id:A044051 - cp's OEIS frontend

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

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

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

			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.

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

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

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

a006995 n = a006995_list !! (n-1)
a006995_list = 0 : filter ((== 1) . a178225) a005408_list
-- Reinhard Zumkeller, Oct 21 2011

[n: n in [0..850] | Intseq(n,2) eq Reverse(Intseq(n,2))];  // Bruno Berselli, Aug 29 2011

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

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 *)

for(n=0,999,n-subst(Polrev(binary(n)),x,2)||print1(n,",")) \\ Thomas Buchholz, Aug 16 2014

for(n=0,10^3, my(d=digits(n,2)); if(d==Vecrev(d), print1(n,", "))); \\ Joerg Arndt, Aug 17 2014

is_A006995(n)=Vecrev(n=binary(n))==n \\ M. F. Hasler, Feb 23 2018

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

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

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

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

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

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

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

Edited and extended by Hieronymus Fischer, Feb 21 2012

Edited by M. F. Hasler, Feb 23 2018

A048702 Binary palindromes of even length divided by 3.

Original entry on oeis.org

0, 1, 3, 5, 11, 15, 17, 21, 43, 51, 55, 63, 65, 73, 77, 85, 171, 187, 195, 211, 215, 231, 239, 255, 257, 273, 281, 297, 301, 317, 325, 341, 683, 715, 731, 763, 771, 803, 819, 851, 855, 887, 903, 935, 943, 975, 991

Offset: 0

Antti Karttunen, Mar 07 1999

Let the length of A048701(n) in binary be 2k. Since it is a palindrome of even length, its digits come in pairs which are equal: one in the left half and the other in the right half. Thus, A048701(n) is a sum of numbers of the form d * 2^m * (2^(2k-2m-1) + 1). The number 2^(2k-2m-1) = 2 * 4^(k-m-1) is congruent to 2 (mod 3), so 2^(2k-2m-1) + 1 is divisible by 3. This means A048701(n) is divisible by 3, and therefore a(n) is an integer. - Michael B. Porter, Jun 18 2019

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A048701, A048704 (base 4 palindromes of even length divided by 5), A044051 (binary palindromes plus one divided by 2: (A006995(n)+1)/2), A000975.

# Two unproved formulas which are not based upon first generating a palindrome and then dividing by 3, recursive and more direct:
# Here d is 2^(the distance between the most and least significant 1-bit of n):
bper3_rec := proc(n) option remember; local d; if(0 = n) then RETURN(0); fi; d := 2^([ log2(n) ]-A007814[ n ]);
if(1 = d) then RETURN((2*bper3_rec(n-1))+d); else RETURN(bper3_rec(n-1)+d); fi; end;
# or more directly (after K. Atanassov's formula for partial sums of A007814):
bper3_direct := proc(n) local l,j; l := [ log2(n) ]; RETURN((2/3*((2^(2*l))-1))+1+ sum('(2^(l-j)*floor((n-(2^l)+2^j)/(2^(j+1))))','j'=0..l)); end;
# Can anybody find an even simpler closed form? See A005187 for inspiration.

Join[{0}, Reap[For[k = 1, k < 3000, k += 2, bb = IntegerDigits[k, 2]; If[bb == Reverse[bb], If[EvenQ[Length[bb]], Sow[k/3]]]]][[2, 1]]] (* Jean-François Alcover, Mar 04 2016 *)

a(n) = A048701(n)/3.
Conjecture: a(n) = 2^floor(log_2(n)) * Sum_{i=1..n} 1/(2^v_2(i)), for n >= 1, where v_2(i) = A007814(i) is the exponent of the highest power of 2 dividing i.
Conjecture: a(n) = n*2^floor(log_2(n)) - Sum_{i=1..floor(log_2(n))} 2^(floor(log_2(n)) - i)*floor(n/(2^i)).

A141707 Least k>0 such that (2n-1)k is palindromic in base 2.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 5, 1, 1, 27, 1, 89, 13, 1, 49, 1, 1, 13, 69, 5, 25, 3, 1, 103, 29, 1, 63, 3, 9, 103, 7, 1, 1, 19, 37, 147, 1, 13, 3, 19, 11, 45, 1, 37, 23, 3, 1, 27, 61, 1, 233, 47, 13, 1, 21, 23, 59, 525, 5, 1, 93, 23, 41, 1, 1, 49, 27, 13, 187, 87, 269, 15, 111, 13, 29, 7, 1, 13, 3

Offset: 1

M. F. Hasler, Jul 17 2008

Even numbers cannot be palindromic in base 2 (unless leading zeros are considered), that's why we search only for odd numbers 2n-1 the k-values such that k(2n-1) is palindromic in base 2. Obviously they are necessarily also odd.

a(A044051(n)) = 1. - Reinhard Zumkeller, Apr 20 2015

			a(1..5)=1 since 1,3,5,7,9 are already palindromic in base 2.
a(6)=3 since 2*6-1=11 and 2*11=22 are not palindromic in base 2, but 3*11=33 is.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A050782, A141708, A178225, A044051.

a141707 n = head [k | k <- [1, 3 ..], a178225 (k * (2 * n - 1)) == 1]
-- Reinhard Zumkeller, Apr 20 2015

lkp[n_]:=Module[{k=1,n2=2n-1},While[IntegerDigits[k*n2,2]!= Reverse[ IntegerDigits[ k*n2,2]],k++];k]; Array[lkp,80] (* Harvey P. Dale, Mar 19 2016 *)

A141707(n,L=10^9)={ n=2*n-1; forstep(k=1,L,2, binary(k*n)-vecextract(binary(k*n),"-1..1") || return(k))}

def binpal(n): b = bin(n)[2:]; return b == b[::-1]
def a(n):
    m = 2*n - 1
    km = m
    while not binpal(km): km += m
    return km//m
print([a(n) for n in range(1, 80)]) # Michael S. Branicky, Mar 20 2022

A145342 a(n) = (A145341(n) + 1)/2.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 6, 8, 9, 13, 11, 15, 10, 14, 12, 16, 17, 25, 21, 29, 19, 27, 23, 31, 18, 26, 22, 30, 20, 28, 24, 32, 33, 49, 41, 57, 37, 53, 45, 61, 35, 51, 43, 59, 39, 55, 47, 63, 34, 50, 42, 58, 38, 54, 46, 62, 36, 52, 44, 60, 40, 56, 48, 64, 65, 97, 81, 113, 73, 105, 89

Offset: 1

Leroy Quet, Oct 08 2008

This sequence is a permutation of the positive integers. It is its own inverse permutation.
Fixed points of the permutation are the terms of A044051. - Ivan Neretin, Oct 31 2015
From Yosu Yurramendi, Feb 04 2019: (Start)
If the terms (n > 0) are written as an array (left-aligned fashion) with rows of length 2^m, m = 0,1,2,3,...
   1;
   2,  3;
   4,  5,  7,  6;
   8,  9, 13, 11, 15, 10, 14, 12;
  16, 17, 25, 21, 29, 19, 27, 23, 31, 18, 26, 22, 30, 20, 28, 24;
  32, 33, 49, 41, 57, 37, 53, 45, 61, 35, 51, 43, 59, 39, 55, 47, 63, 34, ...
then the following relationship can be observed:
a(1) = 1, a(2) = 2, a(3) = 3,
for m > 0, a(2^(m+1)) = 2*a(2^m), a(2^m + 1) = a(2^m) + 1, a(2^(m+1)+ 2^m) = 2*a(2^(m+1)) - 1, for 0 < k < 2^m, a(2^(m+1)+ k) = 2*a(2^m + k) - 1, a(2^(m+1)+ 2^m + k) = a(2^(m+1) + k) + 1
(End)

Cf. A044051, A145341.

Table[(FromDigits[Reverse[IntegerDigits[2n-1, 2]], 2] +1)/2, {n, 71}] (* Ivan Neretin, Oct 31 2015 *)

a(n) = (1+fromdigits(Vecrev(binary(2*n-1)), 2))/2; \\ Michel Marcus, Feb 04 2019

nmax <- 10^3 # by choice
b <- vector()
for (o in seq(1,nmax,2)){
  w <- which(as.numeric(intToBits(o))==1)
  b <- c(b, sum(2^(max(w)-w)))
}
a <- (b+1)/2
a[1:71]
# Yosu Yurramendi, Feb 04 2019

More terms from R. J. Mathar and Ray Chandler, Oct 10 2008

cp's OEIS Frontend

A006995 Binary palindromes: numbers whose binary expansion is palindromic.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Sage

Sage

Smalltalk

Formula

Extensions

A048702 Binary palindromes of even length divided by 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A141707 Least k>0 such that (2n-1)k is palindromic in base 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

A145342 a(n) = (A145341(n) + 1)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

R

Extensions

A341257 Positions of palindromes in the ordering of all 01-words defined at A341256.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica