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

[Frank Ruskey]

Please note the following equation from an updated version of
the Deugau-Ruskey paper listed in A120511 that appeared in
JIS: http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.pdf
See page 25.

p(n) = s*ceil(log_k n) + (kn-d-1)/(k-1)

Here, d is the sum of the digits of the k-ary expression of n-1.
In your case s = 1 and k = 2.  Nice to see that somebody is
actually looking at these sequences!
Best Regards,
Frank




Max Alekseyev wrote:
> 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
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 


-- 
----------------------
Frank Ruskey             e-mail: (last_name)(AT)cs(DOT)uvic(DOT)ca
Dept. of Computer Science      office:    250-472-5794
University of Victoria         fax:       250-472-5708
Victoria, B.C. V8W 3P6 CANADA  WWW: http://www.cs.uvic.ca/~(last_name)

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.