cp's OEIS Frontend

A206916 Index of the least binary palindrome >=n; also the "upper inverse" of A006995.

%I A206916 #28 Jul 24 2024 17:22:32
%S A206916 1,2,3,3,4,4,5,5,6,6,7,7,7,7,7,7,8,8,9,9,9,9,10,10,10,10,10,10,11,11,
%T A206916 11,11,12,12,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,15,
%U A206916 15,15,15,15,15,15,15,15,15,15,15,16,16,17,17,17,17,17
%N A206916 Index of the least binary palindrome >=n; also the "upper inverse" of A006995.
%C A206916 The least m such that A006995(m)>=n;
%C A206916 n is palindromic iff a(n)=A206915(n);
%C A206916 a(n) is the number of the binary palindrome A206914(n);
%C A206916 if n is a binary palindrome, then A006995(a(n))=n, so a(n) is 'inverse' with respect to A006995
%F A206916 a(n)=min(m|A006995(m)>=n);
%F A206916 a(A006995(n))=n;
%F A206916 A006995(a(n))>=n, equality holds true iff n is a binary palindrome;
%F A206916 Let p=A206914(n), m=floor(log_2(p)) and p>2, then:
%F A206916 a(n)=(((5-(-1)^m)/2) + sum_{k=1..floor(m/2)} (floor(p/2^k) mod 2)/2^k))*2^floor(m/2);
%F A206916 a(n)=(1/2)*((6-(-1)^m)*2^floor(m/2)-1-sum_       {k=1..floor(m/2)} (-1)^floor(p/2^k)*2^(floor(m/2)-k)));
%F A206916 a(n)=(5-(-1)^m)*2^floor(m/2)/2-3*sum_{k=2..floor(m/2)} floor(p/2^k)*2^floor(m/2)/2^k)+(floor(p/2)*2^floor(m/2)/2-2*floor((p/2)*2^floor(m/2))*floor((m-1)/m+1/2).
%F A206916 Partial sums S(n) = sum_{k=0..n} a(k):
%F A206916 S(n) = 1+n*a(n)-A206920(a(n)-1), valid for n>0.
%F A206916 G.f.: g(x)=(x+x^2+x^3+sum_{j=1..infinity} x^(3*2^j)*(f_j(x)+f_j(1/x)))/(x(1-x)), where the f_j(x) are defined as follows:
%F A206916   f_1(x)=x, and for j>1,
%F A206916   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).
%e A206916 a(2)=3 since 3 is the index number of the least binary palindrome >= 2;
%e A206916 a(5)=4 since 4 is the index number of the least binary palindrome >= 5;
%e A206916 a(10)=7 since A006995(7)=15>=10, but A006995(6)=9<10, and so that, 7 is the index number of least binary palindrome >= 10;
%o A206916 (Python)
%o A206916 def A206916(n):
%o A206916     l = n.bit_length()
%o A206916     k = l+1>>1
%o A206916     return (n>>l-k)+(int(bin(n)[k+1:1:-1] or '0',2)<(n&(1<<k)-1))+(1<<k-1+(l&1^1)) # _Chai Wah Wu_, Jul 24 2024
%Y A206916 Cf. A006995, A206920.
%K A206916 nonn,base
%O A206916 0,2
%A A206916 _Hieronymus Fischer_, Feb 17 2012