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

Sequence in context: A322921 A030581 A113609 * A336112 A067086 A254531

Adjacent sequences: A206913 A206914 A206915 * A206917 A206918 A206919

Keyword

nonn,base

Author

Hieronymus Fischer, Feb 17 2012

Status

approved