|
| |
|
|
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 k-ary Trees and Generalized Meta-Fibonacci Sequences
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
B. Jackson and F. Ruskey, Meta-Fibonacci 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/(1-z)) * (1 + Sum_{k=0..ceiling(n/2)} z^(2^m) * (1 + 1/(1 - z^(2^m)))).
It appears that a(n) = a(ceiling(n/2)) + n. - Georgi Guninski, Sep 08 2009
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) = ceiling(n/2) and furthermore m-n = a(b(m-n)) = a(ceiling(n/2)) or a(n) = a(ceiling(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) <= log_2(n)-1, implying that 2n-1 <= A120511(n) <= 2n + log_2(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) + 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).
(End)
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
From Antti Karttunen, Dec 12 2013: (Start)
a(n) = 2n + A080791(n) - A007814(n) - A036987(n-1) [This is essentially Max Alekseyev's above formula represented with A-numbers].
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).]
(End)
a(n) = 2*n - 1 + A023416(2*n-1). - Reinhard Zumkeller, Apr 17 2014
|
|
|
MAPLE
|
p := proc(n)
if n=1 then return 1; end if;
for j from p(n-1)+1 to infinity do
if A006949(j) = n then return j; fi; od;
end proc;
|
|
|
MATHEMATICA
|
a[n_] := 2 n - 1 + DigitCount[2 n - 1, 2, 0]; Array[a, 100] (* Jean-François Alcover, Feb 01 2018, after Reinhard Zumkeller *)
|
|
|
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 PARI-program 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(n-1).
Cf. A241218.
Sequence in context: A091067 A269177 A269178 * A176864 A347793 A306718
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
|
| |
|
|
