A006949 -id:A006949 - cp's OEIS frontend

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

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

Offset: 1

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

nonn

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

Cf. A006949, A120522, A007814, A023416, A036987, A080791, A005408.
a(n) = one less than A233273(n-1).
Cf. A241218.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a120511 = (+ 1) . fromJust . (`elemIndex` (tail a006949_list))
-- Reinhard Zumkeller, Apr 17 2014

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;

a[n_] := 2 n - 1 + DigitCount[2 n - 1, 2, 0]; Array[a, 100] (* Jean-François Alcover, Feb 01 2018, after Reinhard Zumkeller *)

{ 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 */

(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

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

Edited by Max Alekseyev, Sep 16 2009

More terms from Max Alekseyev, Sep 18 2009

A241235 a(n) = number of times n appears in A006949.

Original entry on oeis.org

3, 3, 1, 4, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2

Offset: 1

Reinhard Zumkeller, Apr 17 2014

nonn

Is this (with an exception at n=1) the same as A135560? - R. J. Mathar, Apr 26 2014

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A051135.

a241235 n = a241235_list !! (n-1)
a241235_list = map length $ group a006949_list

A120522 First differences of successive meta-Fibonacci numbers A006949.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0

Offset: 1

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

nonn

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]
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), #R26, 13 pages.

Cf. A006949, A120511.

d := n -> if n=1 then 1 else A006949(n)-A006949(n-1) fi;

d(n) = 0 if node n is an inner node, or 1 if node n is a leaf.

G.f.: z (1 + z^2 ( (1 - z^[1]) / (1 - z^[1]) + z^3 * (1 - z^(2 * [i]))/(1 - z^[1]) ( (1 - z^[2]) / (1 - z^[2]) + z^5 * (1 - z^(2 * [2]))/(1 - z^[2]) (..., where [i] = (2^i - 1).

A284214 Remainder when sum of first n terms of A006949 is divided by n.

Original entry on oeis.org

0, 0, 0, 1, 2, 3, 5, 0, 2, 4, 6, 9, 0, 3, 7, 12, 0, 4, 8, 12, 17, 1, 6, 12, 19, 0, 6, 13, 21, 29, 7, 16, 25, 0, 8, 16, 24, 33, 4, 13, 23, 34, 2, 12, 23, 35, 0, 12, 25, 38, 0, 12, 25, 39, 53, 12, 27, 42, 57, 13, 29, 45, 62, 16, 33, 50, 0, 16, 32, 48, 65, 11, 28, 46, 65, 8, 26, 45, 65, 5

Offset: 1

Altug Alkan, Mar 23 2017

nonn

Sequence represents e(n, 1) where e(n, i) = (Sum_{k=0..n-1} A006949(k)) mod (n*i).

See also alternative scatterplot and graph of this sequence in Links section.

			a(6) = 3 because Sum_{k=0..5} A006949(k) = 1 + 1 + 1 + 2 + 2 + 2 = 9 and remainder when 9 is divided by 6 is 3.

Altug Alkan, Table of n, a(n) for n = 1..20000
Altug Alkan, Alternative graph of A284214
Altug Alkan, Alternative scatterplot of A284214
Altug Alkan, Illustration of residue classes modulo 4

Cf. A006949, A282891, A283025.

a[0] = a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1 - a[n - 1]] + a[n - 2 - a[n - 2]]; MapIndexed[Mod[#1, First@ #2] &, Accumulate@ Table[a@ n, {n, 0, 79}]] (* Michael De Vlieger, Mar 24 2017 *)

a(n) = (Sum_{k=0..n-1} A006949(k)) mod n.

A240808 a(0)=2, a(1)=1, a(2)=0; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Original entry on oeis.org

2, 1, 0, 2, 1, 3, 2, 1, 3, 5, 4, 3, 5, 4, 6, 8, 4, 6, 8, 7, 9, 8, 7, 12, 11, 7, 12, 14, 10, 12, 14, 10, 12, 17, 13, 12, 20, 16, 12, 20, 19, 15, 20, 19, 18, 23, 19, 21, 26, 19, 21, 26, 19, 24, 29, 19, 27, 32, 19, 27, 32, 22, 30, 32, 22, 30, 32, 25, 33, 32, 28, 36, 32, 31, 39, 32, 31, 42, 35, 31, 45, 38, 31, 45, 38, 31, 48, 41, 31, 51, 44, 31, 51, 47, 34

Offset: 0

N. J. A. Sloane, Apr 15 2014

a(A241218(n)) = n and a(m) <> n for m < A241218(n). - Reinhard Zumkeller, Apr 17 2014

Higham, Jeff and Tanny, Stephen, A tamely chaotic meta-Fibonacci sequence. Twenty-third Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1993). Congr. Numer. 99 (1994), 67-94. [Contains a detailed analysis of this sequence]

Reinhard Zumkeller, Table of n, a(n) for n = 0..20000
Rémy Sigrist, Colored scatterplot of a(n) for n = 0..20000 (where the color is function of n mod 3)
Index entries for Hofstadter-type sequences

A006949 and A240807 have the same recurrence but different initial conditions.

Trisections: A244780..A244782.

a240808 n = a240808_list !! n
a240808_list = 2 : 1 : 0 : zipWith (+) xs (tail xs)
   where xs = map a240808 $ zipWith (-) [1..] $ tail a240808_list
-- Reinhard Zumkeller, Apr 17 2014

a:=proc(n) option remember; global k;
if n = 0 then 2
elif n = 1 then 1
elif n = 2 then 0
else
if (a(n-1) <= n-1) and (a(n-2) <= n-2) then
a(n-1-a(n-1))+a(n-2-a(n-2));
else lprint("died with n =",n); return (-1);
fi;
fi; end;
[seq(a(n),n=0..100)];

a[n_] := a[n] = Switch[n, 0, 2, 1, 1, 2, 0, _,
   If[a[n - 1] <= n - 1 && a[n - 2] <= n - 2,
   a[n - 1 - a[n - 1]] + a[n - 2 - a[n - 2]],
   Print["died with n =", n]; Return[-1]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 02 2024 *)

A240807 a(0)=a(1)=-1, a(2)=2; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Original entry on oeis.org

-1, -1, 2, 1, 1, 3, 3, 3, 2, 4, 6, 4, 4, 5, 4, 8, 9, 6, 7, 8, 8, 8, 9, 10, 10, 9, 13, 14, 10, 12, 13, 12, 14, 15, 14, 15, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 19, 23, 24, 20, 22, 22, 22, 25, 23, 22, 27, 27, 25, 28, 27, 27, 29, 29, 29, 29, 31, 31, 31, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 39, 43, 44, 40, 42, 42, 42

Offset: 0

N. J. A. Sloane, Apr 15 2014

sign

Higham, Jeff and Tanny, Stephen, A tamely chaotic meta-Fibonacci sequence. Twenty-third Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1993). Congr. Numer. 99 (1994), 67-94.

N. J. A. Sloane, Table of n, a(n) for n = 0..20000
Index entries for Hofstadter-type sequences

A006949 and A240808 have the same recurrence but different initial conditions.

a240807 n = a240807_list !! n
a240807_list = -1 : -1 : 2 : zipWith (+) xs (tail xs)
   where xs = map a240807 $ zipWith (-) [1..] $ tail a240807_list
-- Reinhard Zumkeller, Apr 17 2014

a:=proc(n) option remember;
if n = 0 then  -1
elif n = 1 then -1
elif n = 2 then 2
else
    if (a(n-1) <= n-1) and (a(n-2) <= n-2) then
    a(n-1-a(n-1))+a(n-2-a(n-2));
    else lprint("died with n =",n); return (-1);
    fi;
fi; end;
[seq(a(n),n=0..100)];

a[n_] := a[n] = Switch[n, 0, -1, 1, -1, 2, 2, _,
   If[a[n-1] <= n-1 && a[n-2] <= n-2,
   a[n-1-a[n-1]] + a[n-2-a[n-2]],
   Print["died with n =", n]; Return[-1]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 02 2024 *)

A244478 a(0)=2, a(1)=0, a(2)=2; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Original entry on oeis.org

2, 0, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 8, 8, 8, 8, 8, 8, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 16, 16, 16, 16, 16, 16, 16, 18, 18, 18, 20, 20, 20, 20, 22, 22, 22, 24, 24, 24, 24, 24, 26, 26, 26, 28, 28, 28, 28, 30, 30, 30, 32, 32, 32, 32, 32, 32, 32, 32, 34, 34, 34, 36, 36, 36, 36, 38, 38, 38

Offset: 0

N. J. A. Sloane, Jul 02 2014

nonn

Higham, J.; Tanny, S. More well-behaved meta-Fibonacci sequences. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr. Numer. 98(1993), 3-17. See Prop. 2.1.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for Hofstadter-type sequences

A006949, A240807, A240808 use the same recurrence.

A244483 a(0)=3, a(1)=1, a(2)=0; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Original entry on oeis.org

3, 1, 0, 3, 3, 4, 2, 4, 6, 3, 2, 8, 9, 6, 7, 8, 8, 10, 10, 10, 9, 11, 10, 11, 18, 11, 9, 17, 12, 10, 18, 19, 18, 16, 17, 20, 18, 18, 20, 20, 20, 19, 19, 21, 21, 21, 29, 28, 20, 22, 29, 28, 22, 29, 36, 28, 27, 27, 28, 36, 29, 30, 38, 37, 27, 27, 38, 32, 32, 38, 37, 35, 34, 38, 40, 37, 37, 40, 38, 38, 39

Offset: 0

N. J. A. Sloane, Jul 03 2014

nonn

Higham, Jeff and Tanny, Stephen, A tamely chaotic meta-Fibonacci sequence. Twenty-third Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1993). Congr. Numer. 99 (1994), 67-94.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for Hofstadter-type sequences

See A006949 for overview of sequences produced by this recurrence and various initial conditions.

a244483 n = a244483_list !! n
a244483_list = 3 : 1 : 0 : zipWith (+) xs (tail xs)
   where xs = map a244483 $ zipWith (-) [1..] $ tail a244483_list
-- Reinhard Zumkeller, Jul 07 2014

f := proc(n) option remember;
    if n=0 then 3
    elif n=1 then 1
    elif n=2 then 0
    else
    f(n-1-f(n-1))+f(n-2-f(n-2));
    fi;
end proc;
[seq(f(n),n=0..80)];

A316627 a(1)=2, a(2)=3; a(n) = a(n+1-a(n-1))+a(n-a(n-2)) for n > 2.

Original entry on oeis.org

2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36, 36, 37, 38, 38, 39, 40, 40, 40, 40, 41, 42, 42

Offset: 1

Nathan Fox, Jul 08 2018

nonn

This sequence increases slowly.
If k is not a power of 2, k occurs A001511(k) times. Otherwise, k occurs A001511(k)-1 times.
This is the meta-Fibonacci sequence for s=-1.

B. W. Conolly, "Meta-Fibonacci sequences," in S. Vajda, editor, Fibonacci and Lucas Numbers and the Golden Section. Halstead Press, NY, 1989, pp. 127-138. See Eq. (2).

Nathan Fox, Table of n, a(n) for n = 1..10000

Cf. A001511, A005185, A006949, A046699.

a:=[2,3];; for n in [3..75] do a[n]:=a[n+1-a[n-1]]+a[n-a[n-2]]; od; a; # Muniru A Asiru, Jul 09 2018

I:=[2,3]; [n le 2 select I[n] else Self(n+1-Self(n-1))+Self(n-Self(n-2)): n in [1..100]]; // Vincenzo Librandi, Jul 09 2018

A316627:=proc(n) option remember: if n <= 0 then 0: elif n = 1 then 2: elif n = 2 then 3: else A316627(n + 1-A316627(n-1)) + A316627(n-A316627(n-2)): fi: end:

a(n+1)-a(n)=1 or 0.

a(n)/n -> C=1/2.

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A241235 a(n) = number of times n appears in A006949.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A120522 First differences of successive meta-Fibonacci numbers A006949.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A284214 Remainder when sum of first n terms of A006949 is divided by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A240808 a(0)=2, a(1)=1, a(2)=0; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

A240807 a(0)=a(1)=-1, a(2)=2; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

A244478 a(0)=2, a(1)=0, a(2)=2; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

A244483 a(0)=3, a(1)=1, a(2)=0; thereafter a(n) = a(n-1-a(n-1))+a(n-2-a(n-2)) unless a(n-1) <= n-1 or a(n-2) <= n-2 in which case the sequence terminates.

Views