Search: id:A120511
Results 1-1 of 1 results found.

%I A120511
%S A120511 1,3,6,7,11,12,14,15,20,21,23,24,27,28,30,31,37,38,40,41,44,45,47,48,52,
%T A120511 53,55,56,59,60,62,63,70,71,73,74,77,78,80,81,85,86,88,89,92,93,95,96,
%U A120511 101,102,104,105,108,109,111,112,116,117,119,120,123,124,126,127,135
%N A120511 a(n) = min{j>0 : A006949(j) = n}.
%H A120511 B. Jackson and F. Ruskey, <a href="http://www.combinatorics.org/Volume_13/
               Abstracts/v13i1r26.html">Meta-Fibonacci Sequences, Binary Trees and 
               Extremal Compact Codes</a>, Electronic Journal of Combinatorics, 
               13 (2006), R26.
%H A120511 C. Deugau and F. Ruskey, <a href="http://www.cs.uwaterloo.ca/journals/
               JIS/VOL12/Ruskey/ruskey6.pdf">Complete k-ary Trees and Generalized 
               Meta-Fibonacci Sequences</a>, J. Integer Seq., Vol. 12. [This is 
               a later version than that in the GenMetaFib.html link]
%H A120511 C. Deugau and F. Ruskey, <a href="http://www.cs.uvic.ca/~ruskey/Publications/
               MetaFib/GenMetaFib.html">Complete k-ary Trees and Generalized Meta-Fibonacci 
               Sequences</a>
%F A120511 G.f.: P(z) = z / (1-z) * (1 + sum(z^(2^m) * (1 + 1 / (1 - z^(2^m))), 
               m=0..infinity))
%F A120511 It appears that a(n) = a(ceil(n/2)) + n. - Georgi Guninski (guninski(AT)guninski.com), 
               Sep 08 2009
%F A120511 Comments from Max Alekseyev, Sep 08 2009: (Start) This can be proved 
               as follows.
%F A120511 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.
%F A120511 The following claims are trivial:
%F A120511 Claim 1. For any n, b(a(n))=n.
%F A120511 Claim 2. If m=a(n) for some n, then a(b(m))=m.
%F A120511 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.
%F A120511 Claim 4. Each even number in A006949 is repeated at least two times while 
               each odd number in A006949 appears only once.
%F A120511 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.
%F A120511 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
%F A120511 Consider two cases:
%F A120511 1) If n is odd, then b(m+1) = n+1 = 2*b(m-n), i.e., b(m-n) = (n+1)/2.
%F A120511 Claim 4 also implies b(m-2)=n-1. Therefore
%F A120511 n = b(m) = b(m-1-b(m-1)) + b(m-2-b(m-2)) = b(m-n) + b(m-n-1)
%F A120511 Since n is odd, we have b(m-n-1)<b(m-n) and thus a(b(m-n))=m-n.
%F A120511 2) If n is even, then b(m+1) = n = 2*b(m-n), i.e., b(m-n) = n/2.
%F A120511 Claim 4 also implies b(m-3)=b(m-2)=n-2. Therefore
%F A120511 n-1 = b(m-1) = b(m-2-b(m-2)) + b(m-3-b(m-3)) = b(m-n) + b(m-n-1)
%F A120511 Since n-1 is odd, we have b(m-n-1)<b(m-n) and thus a(b(m-n))=m-n.
%F A120511 Combining these two cases, we have b(m-n) = ceil(n/2) and furthermore
%F A120511 m-n = a(b(m-n)) = a(ceil(n/2)) or a(n) = a(ceil(n/2)) + n.
%F A120511 QED
%F A120511 This implies explicit formulas for both sequences.
%F A120511 Let z(n) be the number of zero bits in the binary representation of n. 
               Then
%F A120511 A120511(n) = 2n + z(n) - k - [n==2^k],
%F A120511 where k = valuation(n,2), i.e., the maximum power of 2 dividing n.
%F A120511 Note that k <= z(n) <= log2(n)-1, implying that 2n-1 <= A120511(n) <= 
               2n + log2(n) - 1
%F A120511 Since A006949(m) equals the largest n such that A120511(n) <= m (and
%F A120511 thus A120511(n+1) > m), from 2n-1 <= A120511(n) <= m it follows that
%F A120511 A006949(m) <= (m+1)/2. Similarly, from
%F A120511 m < A120511(n+1) < 2(n+1) + log2(n+1) - 1 <= 2(n+1) + log2((m+1)/2+1) 
               - 1,
%F A120511 it follows that A006949(m) >= (m - log2(m+3)) / 2.
%F A120511 Therefore | A006949(m) - m/2 | <= log2(m+3)/2
%F A120511 which gives an interval of just logarithmic length to search for the 
               value of A006949(m).
%F A120511 (End)
%F A120511 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.
%p A120511 p := proc(n)
%p A120511 if n=1 then return 1; end if;
%p A120511 for j from p(n-1)+1 to infinity do
%p A120511 if A006949(j) = n then return j; fi; od;
%p A120511 end proc;
%o A120511 (PARI) { 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) } /* from Max Alekseyev */
%Y A120511 Cf. A006949, A120522.
%Y A120511 Sequence in context: A087643 A022544 A091067 this_sequence A022550 A153033 
               A076644
%Y A120511 Adjacent sequences: A120508 A120509 A120510 this_sequence A120512 A120513 
               A120514
%K A120511 nonn
%O A120511 1,2
%A A120511 Frank Ruskey (http://www.cs.uvic.ca/~ruskey/) and Chris Deugau (deugaucj(AT)uvic.ca), 
               Jun 20 2006
%E A120511 Edited by Max Alekseyev (maxale(AT)gmail.com), Sep 16 2009
%E A120511 More terms from Max Alekseyev (maxale(AT)gmail.com), Sep 18 2009

Search completed in 0.002 seconds