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

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, 11, 11, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 17, 17, 17, 17, 17

Offset: 0

Author

Hieronymus Fischer, Feb 17 2012

Keywords

• nonn
• base

Comments

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

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

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

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

Examples

			a(2)=3 since 3 is the index number of the least binary palindrome >= 2;
a(5)=4 since 4 is the index number of the least binary palindrome >= 5;
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;
		

Crossrefs

Cf. A006995, A206920.

Programs

Python

def A206916(n):
    l = n.bit_length()
    k = l+1>>1
    return (n>>l-k)+(int(bin(n)[k+1:1:-1] or '0',2)<(n&(1<Chai Wah Wu, Jul 24 2024

Formula

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

a(A006995(n))=n;

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

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

a(n)=(((5-(-1)^m)/2) + sum_{k=1..floor(m/2)} (floor(p/2^k) mod 2)/2^k))*2^floor(m/2);

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

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

Partial sums S(n) = sum_{k=0..n} a(k):

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

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_1(x)=x, and for j>1,

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