A241218 -id:A241218 - cp's OEIS frontend

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.

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 *)

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

Original entry on oeis.org

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

cp's OEIS Frontend

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