cp's OEIS Frontend

A120511 a(n) = min{j>0 : A006949(j) = n}.

%I A120511 #41 Jun 14 2019 00:36:27
%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,
%T A120511 52,53,55,56,59,60,62,63,70,71,73,74,77,78,80,81,85,86,88,89,92,93,95,
%U A120511 96,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 Antti Karttunen, <a href="/A120511/b120511.txt">Table of n, a(n) for n = 1..10000</a>
%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>
%H A120511 C. Deugau and F. Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey/ruskey6.html">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 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 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>
%F A120511 G.f.: P(z) = (z/(1-z)) * (1 + Sum_{k=0..ceiling(n/2)} z^(2^m) * (1 + 1/(1 - z^(2^m)))).
%F A120511 It appears that a(n) = a(ceiling(n/2)) + n. - _Georgi Guninski_, Sep 08 2009
%F A120511 From _Max Alekseyev_, Sep 08 2009: (Start)
%F A120511 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.
%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. 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. 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.
%F A120511 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.
%F A120511 Combining these two cases, we have b(m-n) = ceiling(n/2) and furthermore m-n = a(b(m-n)) = a(ceiling(n/2)) or a(n) = a(ceiling(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], where k = valuation(n,2), i.e., the maximum power of 2 dividing n.
%F A120511 Note that k <= z(n) <= log_2(n)-1, implying that 2n-1 <= A120511(n) <= 2n + log_2(n) - 1.
%F A120511 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) + log_2(n+1) - 1 <= 2(n+1) + log_2((m+1)/2+1) - 1, it follows that A006949(m) >= (m - log_2(m+3)) / 2. Therefore | A006949(m) - m/2 | <= log_2(m+3)/2, which gives an interval of just logarithmic length to search for the value of A006949(m).
%F A120511 (End)
%F A120511 From p. 25 of the revised version of the Deugau-Ruskey paper, we have p(n) = s*ceiling(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. - _Frank Ruskey_, Sep 11 2009
%F A120511 From _Antti Karttunen_, Dec 12 2013: (Start)
%F A120511 a(n) = 2n + A080791(n) - A007814(n) - A036987(n-1) [This is essentially Max Alekseyev's above formula represented with A-numbers].
%F A120511 a(n) = A005408(n-1) + A080791(n-1) = A233273(n-1) - 1. [The above formula reduces to this, because A080791(n) - A080791(n+1) = 1 - (A007814(n+1) + A036987(n)) and A080791(2n+1) = A080791(n).]
%F A120511 (End)
%F A120511 a(n) = 2*n - 1 + A023416(2*n-1). - _Reinhard Zumkeller_, Apr 17 2014
%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;
%t A120511 a[n_] := 2 n - 1 + DigitCount[2 n - 1, 2, 0]; Array[a, 100] (* _Jean-François Alcover_, Feb 01 2018, after _Reinhard Zumkeller_ *)
%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) } /* _Max Alekseyev_, Sep 18 2009 */
%o A120511 (Scheme)
%o A120511 (define (A120511 n) (+ n n (A080791 n) (- (A007814 n)) (- (A036987 (- n 1)))))
%o A120511 (define (A120511 n) (+ (A005408 (- n 1)) (A080791 (- n 1))))
%o A120511 ;; Based on above PARI-program and its further reduction, from _Antti Karttunen_, Dec 12 2013
%o A120511 (Haskell)
%o A120511 import Data.List (elemIndex); import Data.Maybe (fromJust)
%o A120511 a120511 = (+ 1) . fromJust . (`elemIndex` (tail a006949_list))
%o A120511 -- _Reinhard Zumkeller_, Apr 17 2014
%Y A120511 Cf. A006949, A120522, A007814, A023416, A036987, A080791, A005408.
%Y A120511 a(n) = one less than A233273(n-1).
%Y A120511 Cf. A241218.
%K A120511 nonn
%O A120511 1,2
%A A120511 _Frank Ruskey_ and Chris Deugau (deugaucj(AT)uvic.ca), Jun 20 2006
%E A120511 Edited by _Max Alekseyev_, Sep 16 2009
%E A120511 More terms from _Max Alekseyev_, Sep 18 2009