|
G.f.: P(z) = z / (1-z) * (1 + sum(z^(2^m) * (1 + 1 / (1 - z^(2^m))), m=0..infinity))
It appears that a(n) = a(ceil(n/2)) + n. - Georgi Guninski (guninski(AT)guninski.com), Sep 08 2009
Comments from Max Alekseyev, Sep 08 2009: (Start) This can be proved as follows.
Let b=A006949. It is known that b(n) = b(n-1-b(n-1)) + b(n-2-b(n-2)) and b(n-1) <= b(n) <= b(n-1)+1.
The following claims are trivial:
Claim 1. For any n, b(a(n))=n.
Claim 2. If m=a(n) for some n, then a(b(m))=m.
Claim 3. Let m=a(n). Then b(m)=n and b(m-1)=n-1, implying that b(m+1) = b(m-b(m)) + b(m-1-b(m-1)) = 2*b(m-n) is an even number.
Claim 4. Each even number in A006949 is repeated at least two times while each odd number in A006949 appears only once.
Proof. If n is even, then for m=a(n), we have b(m)=n and b(m+1)=n (from Claim 3), i.e., n is repeated at least twice.
If n is odd, then for m=a(n), we cannot have b(m+1)=n since by Claim 3 b(m+1) must be even. QED
Consider two cases:
1) If n is odd, then b(m+1) = n+1 = 2*b(m-n), i.e., b(m-n) = (n+1)/2.
Claim 4 also implies b(m-2)=n-1. Therefore
n = b(m) = b(m-1-b(m-1)) + b(m-2-b(m-2)) = b(m-n) + b(m-n-1)
Since n is odd, we have b(m-n-1)<b(m-n) and thus a(b(m-n))=m-n.
2) If n is even, then b(m+1) = n = 2*b(m-n), i.e., b(m-n) = n/2.
Claim 4 also implies b(m-3)=b(m-2)=n-2. Therefore
n-1 = b(m-1) = b(m-2-b(m-2)) + b(m-3-b(m-3)) = b(m-n) + b(m-n-1)
Since n-1 is odd, we have b(m-n-1)<b(m-n) and thus a(b(m-n))=m-n.
Combining these two cases, we have b(m-n) = ceil(n/2) and furthermore
m-n = a(b(m-n)) = a(ceil(n/2)) or a(n) = a(ceil(n/2)) + n.
QED
This implies explicit formulas for both sequences.
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.
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
which gives an interval of just logarithmic length to search for the value of A006949(m).
(End)
Comment from Frank Ruskey, Sep 11 2009: From p. 25 of the revised version of the Deugau-Ruskey we have p(n) = s*ceil(log_k n) + (kn-d-1)/(k-1) where d is the sum of the digits of the k-ary expression of n-1. In the present case s = 1 and k = 2.
| 