A206916 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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

LINKS

Table of n, a(n) for n=0..70.

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

EXAMPLE

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;

PROG

(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<<k)-1))+(1<<k-1+(l&1^1)) # Chai Wah Wu, Jul 24 2024

CROSSREFS

Cf. A006995, A206920.