[seqfan] Re: A120511 a(n) = min{j : A006949(j) = n}

[Max Alekseyev]

On Fri, Sep 11, 2009 at 8:11 AM, Georgi Guninski <guninski at guninski.com> wrote:

>> I guess you meant a(n) = a(ceil(n/2)) + n.
>>
>
> thank you.
>
> assuming A120511 is efficiently computable (your proof or the potential
> doubling formulas i found) is A006949 efficiently computable by
> something like a binary search in A120511?

It is possible.

Actually, from the recurrence for A120511(n) we can derive even an
explicit formula:

Let z(n) be the number of zero bits in the binary representation of n. Then

A120511(n) = 2n + z(n) - k - [n==2^k],

where k = valuation(n,2), i.e., the maximum power of 2 dividing n.

Here is a corresponding PARI/GP code:

{ A120511(n) = local(t,k); t=binary(n); k=valuation(n,2); 2*n + #t -
sum(i=1,#t,t[i]) - k - (n==2^k) }

Note that k <= z(n) <= log2(n)-1, implying that
2n-1 <= A120511(n) <= 2n + log2(n) - 1

Since A006949(m) equals the largest n such that A120511(n) <= m (and
thus A120511(n+1) > m), from 2n-1 <= A120511(n) <= m it follows that
A006949(m) <= (m+1)/2.
Similarly, from
m < A120511(n+1) <  2(n+1) + log2(n+1) - 1 <= 2(n+1) + log2((m+1)/2+1) - 1,
it follows that
A006949(m) >= (m - log2(m+3)) / 2.

Therefore,
| A006949(m) - m/2 | <= log2(m+3)/2
that gives an interval of just logarithmic length to search the value
of A006949(m).

Regards,
Max