A206916 - OEIS

%I #28 Jul 24 2024 17:22:32

%S 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 11,11,12,12,13,13,13,13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,15,

%U 15,15,15,15,15,15,15,15,15,15,15,16,16,17,17,17,17,17

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

%C The least m such that A006995(m)>=n;

%C n is palindromic iff a(n)=A206915(n);

%C a(n) is the number of the binary palindrome A206914(n);

%C if n is a binary palindrome, then A006995(a(n))=n, so a(n) is 'inverse' with respect to A006995

%F a(n)=min(m|A006995(m)>=n);

%F a(A006995(n))=n;

%F A006995(a(n))>=n, equality holds true iff n is a binary palindrome;

%F Let p=A206914(n), m=floor(log_2(p)) and p>2, then:

%F 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 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 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 Partial sums S(n) = sum_{k=0..n} a(k):

%F S(n) = 1+n*a(n)-A206920(a(n)-1), valid for n>0.

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

%e a(2)=3 since 3 is the index number of the least binary palindrome >= 2;

%e a(5)=4 since 4 is the index number of the least binary palindrome >= 5;

%e 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 (Python)

%o def A206916(n):

%o     l = n.bit_length()

%o     k = l+1>>1

%o     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 Cf. A006995, A206920.

%K nonn,base

%O 0,2

%A _Hieronymus Fischer_, Feb 17 2012