login
Characteristic function of A006995 (binary palindromes).
19

%I #50 Oct 16 2023 01:42:34

%S 1,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,

%T 0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,

%U 0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0

%N Characteristic function of A006995 (binary palindromes).

%C a(n)=1 if n is in A006995, a(n)=0 otherwise.

%C For n<43, identical to parity of A175096.

%C Comment by _Franklin T. Adams-Watters_: (Start)

%C Any permutation of the runs of n gives another such permutation when reversed. This pairs up all non-palindromic permutations of the runs of n. Thus the parity of A175096(n) is the parity of the number of palindromic run-permutations of n. For small n, this is 1 when n is a binary palindrome, and 0 otherwise.

%C The first exception is 43, binary 101011, which has a nontrivial palindromic run-permutation 45, binary 101101. Another kind of exception occurs first for n = 365, binary 101101101, which is a palindrome, but has another palindromic run-permutation 427, binary 110101011. (End)

%C Given an index n such that a(n)=1, then the following A164126(A206915(n))-1 terms will be 0. n'=A164126(A206915(n)) is the next term with a(n')=1. Therefore, if we subtract 1 from each term of A164126, we get the sequence of run lengths of 0's. - _Hieronymus Fischer_, Feb 19 2012.

%C Given an index n such that a(n)=0, then p=A206913(n) is the greatest index p<n such that a(p)=1, hence, a(k)=0 for all k with p<k<=n. Similarly, q=A206914(n) is the least index q>n such that a(q)=1, which implies a(k)=0 for all k with n<=k<q. - _Hieronymus Fischer_, Feb 19 2012.

%C Binary palindromes are distributed symmetrically with respect to threefold multiples of powers of 2. This becomes obvious by the generating function g(x) below. Example for the resulting factors of x^(3*2^5)=x^96: the factors are x^q and x^(-q) for q=3,11,23,31. Thus, the palindromes are 96+3, 96-3, 96+11, 96-11, 96+23, 96-23, 96+31, 96-31. The respective number of palindromes with this property is 2^(floor(m/2)), where m is the exponent of the corresponding power of 2. - _Hieronymus Fischer_, Apr 04 2012

%H Reinhard Zumkeller, <a href="/A178225/b178225.txt">Table of n, a(n) for n = 0..10000</a>

%H <a href="/index/Ch#char_fns">Index entries for characteristic functions</a>

%F a(A006995(n)) = 1; a(A154809(n)) = 0. - _Reinhard Zumkeller_, Oct 21 2011

%F a(n) = if A030101(n) = n then 1, otherwise 0. - _Reinhard Zumkeller_, Jan 17 2012

%F a(n) = 1 - (A206916(n) - A206915(n)). - _Hieronymus Fischer_, Feb 18 2012

%F G.f.: g(x) = 1 + x + x^3 + Sum{j>=1} x^(3*2^j)*(f_j(x)+f_j(1/x)), where the f_j(x) are defined as follows:

%F f_1(x)=x, and for j > 1,

%F f_j(x) = x^3*Product_{k=1..floor((j-1)/2)} (1+x^b(j,k)), 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). The first explicit terms of this g.f. are

%F g(x) = 1 + x + x^3 + (f_1(x) + f_1(1/x))*x^6 + (f_2(x) + f_2(1/x))*x^12 + (f_3(x)+f_3(1/x))*x^24 + (f_4(x) + f_4(1/x))*x^48 + (f_5(x) + f_5(1/x))*x^96 + ... = 1 + x + x^3 + (x+1/x)*x^6 + (x^3+1/x^3)*x^12 + (x^3*(1+x^4) + (1+1/x^4)/x^3)*x^24 + (x^3*(1+x^12) + (1+1/x^12)/x^3)*x^48 + (x^3*(1+x^8)(1+x^20) + (1+1/x^20)(1+1/x^8)/x^3)*x^96 + ... - _Hieronymus Fischer_, Apr 02 2012

%e a(3)=1, since 3 is binary palindromic;

%e a(4)=0, since 4 is not palindromic.

%t A178225[n_]:=Boole[PalindromeQ[IntegerDigits[n,2]]];

%t Array[A178225,100,0] (* _Paolo Xausa_, Oct 15 2023 *)

%o (Chipmunk BASIC v3.6.4(b8))

%o rem http://www.nicholson.com/rhn/basic/

%o for n=0 to 200

%o r$=""

%o s$=bin$(n)

%o for i=len(s$) to 1 step -1

%o r$=r$+mid$(s$,i,1)

%o next i

%o if r$ = s$ then c=1 : else c=0

%o print str$(c)+",";

%o next n

%o print

%o end

%o (Haskell)

%o a178225 n = fromEnum $ n == a030101 n -- _Reinhard Zumkeller_, Oct 21 2011

%o (PARI) a(n) = my(b=binary(n)); b == Vecrev(b); \\ _Michel Marcus_, Feb 13 2019

%o (Python) a187225 = lambda n: int(bin(n)[2:] == bin(n)[:1:-1]) # _David Radcliffe_, May 05 2023

%Y Cf. A006995, A175096, A178226

%Y Cf. A136522. See A206915 for the partial sums.

%K base,easy,nonn

%O 0,1

%A _Jeremy Gardiner_, May 23 2010