

A120511


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


7



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, 53, 55, 56, 59, 60, 62, 63, 70, 71, 73, 74, 77, 78, 80, 81, 85, 86, 88, 89, 92, 93, 95, 96, 101, 102, 104, 105, 108, 109, 111, 112, 116, 117, 119, 120, 123, 124, 126, 127, 135
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

Antti Karttunen, Table of n, a(n) for n = 1..10000
C. Deugau and F. Ruskey, Complete kary Trees and Generalized MetaFibonacci Sequences
C. Deugau and F. Ruskey, Complete kary Trees and Generalized MetaFibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
B. Jackson and F. Ruskey, MetaFibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.
Index entries for sequences related to binary expansion of n


FORMULA

G.f.: P(z) = z / (1z) * (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, 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(n1b(n1)) + b(n2b(n2)) and b(n1) <= b(n) <= b(n1)+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(m1)=n1, implying that b(m+1) = b(mb(m)) + b(m1b(m1)) = 2*b(mn) 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(mn), i.e., b(mn) = (n+1)/2. Claim 4 also implies b(m2)=n1. Therefore n = b(m) = b(m1b(m1)) + b(m2b(m2)) = b(mn) + b(mn1). Since n is odd, we have b(mn1)<b(mn) and thus a(b(mn))=mn.
2) If n is even, then b(m+1) = n = 2*b(mn), i.e., b(mn) = n/2. Claim 4 also implies b(m3)=b(m2)=n2. Therefore n1 = b(m1) = b(m2b(m2)) + b(m3b(m3)) = b(mn) + b(mn1). Since n1 is odd, we have b(mn1)<b(mn) and thus a(b(mn))=mn.
Combining these two cases, we have b(mn) = ceil(n/2) and furthermore mn = a(b(mn)) = 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 2n1 <= 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 2n1 <= 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 DeugauRuskey, we have p(n) = s*ceil(log_k n) + (knd1)/(k1) where d is the sum of the digits of the kary expression of n1. In the present case s = 1 and k = 2.
Comments from Antti Karttunen, Dec 12 2013: (Start)
a(n) = 2n + A080791(n)  A007814(n)  A036987(n1) [This is essentially Max Alekseyev's above formula represented with Anumbers].
a(n) = A005408(n1) + A080791(n1) = A233273(n1)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)].
(End)
a(n) = 2*n1 + A023416(2*n1).  Reinhard Zumkeller, Apr 17 2014


MAPLE

p := proc(n)
if n=1 then return 1; end if;
for j from p(n1)+1 to infinity do
if A006949(j) = n then return j; fi; od;
end proc;


PROG

(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 */
(Scheme)
(define (A120511 n) (+ n n (A080791 n) ( (A007814 n)) ( (A036987 ( n 1)))))
(define (A120511 n) (+ (A005408 ( n 1)) (A080791 ( n 1))))
;; Based on above PARIprogram and its further reduction, from Antti Karttunen, Dec 12 2013
(Haskell)
import Data.List (elemIndex); import Data.Maybe (fromJust)
a120511 = (+ 1) . fromJust . (`elemIndex` (tail a006949_list))
 Reinhard Zumkeller, Apr 17 2014


CROSSREFS

Cf. A006949, A120522, A007814, A023416, A036987, A080791, A005408.
a(n) = one less than A233273(n1).
Cf. A241218.
Sequence in context: A091067 A269177 A269178 * A176864 A022550 A237883
Adjacent sequences: A120508 A120509 A120510 * A120512 A120513 A120514


KEYWORD

nonn


AUTHOR

Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca), Jun 20 2006


EXTENSIONS

Edited by Max Alekseyev, Sep 16 2009
More terms from Max Alekseyev, Sep 18 2009


STATUS

approved



