A240808 -id:A240808 - cp's OEIS frontend

A241218 Smallest number m such that A240808(m) = n.

2, 1, 0, 5, 10, 9, 14, 19, 15, 20, 28, 24, 23, 34, 27, 41, 37, 33, 44, 40, 36, 47, 61, 45, 53, 67, 48, 56, 70, 54, 62, 73, 57, 68, 94, 78, 71, 97, 81, 74, 100, 87, 77, 106, 90, 80, 109, 93, 86, 115, 96, 89, 121, 99, 146, 124, 105, 152, 127, 108, 155, 130

Offset: 0

Reinhard Zumkeller, Apr 17 2014

nonn

A240808(a(n)) = n and A240808(m) <> n for m < a(n).

Reinhard Zumkeller, Table of n, a(n) for n = 0..20000

Cf. A120511.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a241218 = fromJust . (`elemIndex` a240808_list)

A244480 Zeroth trisection of A240808.

Original entry on oeis.org

2, 2, 2, 5, 5, 8, 8, 8, 11, 14, 14, 17, 20, 20, 20, 23, 26, 26, 29, 32, 32, 32, 32, 32, 32, 32, 35, 38, 38, 41, 44, 47, 50, 53, 53, 56, 59, 59, 62, 62, 65, 68, 71, 74, 77, 77, 80, 83, 83, 83, 83, 83, 83, 83, 86, 89, 89, 92, 95, 98, 101, 104, 104, 107, 110, 110, 113, 113, 116, 119, 122, 125, 128, 128

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.

Index entries for Hofstadter-type sequences

Cf. A240808, A244781, A244782.

A244481 First trisection of A240808.

Original entry on oeis.org

1, 1, 1, 4, 4, 4, 7, 7, 7, 10, 10, 13, 16, 19, 19, 19, 19, 19, 19, 19, 22, 22, 25, 28, 31, 31, 31, 31, 31, 31, 31, 34, 37, 40, 40, 43, 46, 46, 49, 49, 52, 55, 58, 61, 64, 64, 67, 70, 73, 73, 76, 79, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 85, 88, 91

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.

Index entries for Hofstadter-type sequences

Cf. A240808, A244780, A244782.

A244482 Second trisection of A240808.

Original entry on oeis.org

0, 3, 3, 3, 6, 6, 9, 12, 12, 12, 12, 12, 12, 15, 18, 21, 21, 24, 27, 27, 30, 30, 33, 36, 39, 42, 45, 45, 48, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 54, 54, 57, 60, 63, 66, 69, 69, 72, 75, 78, 81, 84, 84, 87, 90, 90, 93, 93, 96, 99, 102, 105, 108, 108, 111, 114, 114

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.

Index entries for Hofstadter-type sequences

Cf. A240808, A244780, A244781.

A006949 A well-behaved cousin of the Hofstadter sequence: a(n) = a(n - 1 - a(n-1)) + a(n - 2 - a(n-2)) for n > 2 with a(0) = a(1) = a(2) = 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 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, 32, 32, 33, 34, 34, 35, 36, 36

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

nonn

Number of different partial sums of 1+[1,2]+[1,4]+[1,8]+[1,16]+... E.g., a(6)=3 because we have 6 = 1+1+1+1+1+1 = 1+1+4 = 1+2+1+1+1. - Jon Perry, Jan 01 2004
Ignoring first term, this is the Meta-Fibonacci sequence for s=1. - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
Comment from N. J. A. Sloane, Jul 03 2014: (Start)
The recurrence a(n) = a(n-1-a(n-1)) + a(n-2-a(n-2)) for n>2 with a(0)=X, a(1)=Y, a(2)=Z gives rise to the following sequences (cf. Higham-Tanny 1993):
  X Y Z
  3 1 0 A244483
  2 1 0 A240808
  2 1 1 A240807
  2 0 2 A244478
  1 0 2 A240808 again
  1 1 1 A006949 (this sequence).
Most other initial values do not produce a nontrivial sequence. (End)
Higham and Tanny (1993) define a family {t_k(n)} (k=0,12,...) of sequences by t_k(n) = floor(n/2) for 0 <= n < k; thereafter t_k(n) = t_k(n-1-t_k(n-1)) + t_k(n-2-t_k(n-2)). The sequence t_4(n) begins 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, ..., which is essentially this sequence. - N. J. A. Sloane, Jul 03 2014
The values X=0 Y=1 Z=1 and X=1 Y=1 Z=2 (see above comments) also produce a sequence which is essentially this sequence. - Pablo Hueso Merino, Dec 31 2020

Jeff Higham and Stephen Tanny, 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.
Jeff Higham and Stephen Tanny, 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 and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..20000
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See Eq. (1.4). - _N. J. A. Sloane_, Apr 16 2014
A. Das, A combinatorial approach to the Tanny sequence, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 97-108.
Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.
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
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Nathan Fox, Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences, arXiv:2203.09340 [math.CO], 2022.
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.
Warren Page (editor), Media Highlights: A well-behaved cousin of the Hofstadter sequence, The College Math. Jnl., 24 (1993), p. 105.
F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3.
S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discr. Math. 105 (1992), 227-239. [See Higham-Tanny 1993 for updates and corrections.]
Index entries for Hofstadter-type sequences

See also A120511. A244478, A244479, A240807, A240808, A244483 have the same recurrence but different initial conditions.

Cf. A241235 (run lengths).

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

A006949 := proc(n) option remember: if n<3 then 1 else A006949(n-1-A006949(n-1))+A006949(n-2-A006949(n-2)) fi end;

a[0] = a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1 - a[n - 1]] + a[n - 2 - a[n - 2]]; Table[a@ n, {n, 0, 75}] (* Michael De Vlieger, Mar 24 2017 *)

{ n=20; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]+2^(i-1))); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } \\ Jon Perry, Jan 01 2004

a(n) = a(n-1) + 0 or 1 for n > 0 and lim_{n -> infinity} a(n)/n = 1/2. - Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003
G.f.: z + z * Sum_{n >= 1} Product_{k=1..n} (z + z^(2^k)). - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
For an efficient way to compute this sequence for large n, see A120511.

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003

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.

cp's OEIS Frontend

A241218 Smallest number m such that A240808(m) = n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A244480 Zeroth trisection of A240808.

Views

Author

Keywords

References

Links

Crossrefs

A244481 First trisection of A240808.

Views

Author

Keywords

References

Links

Crossrefs

A244482 Second trisection of A240808.

Views

Author

Keywords

References

Links

Crossrefs

A006949 A well-behaved cousin of the Hofstadter sequence: a(n) = a(n - 1 - a(n-1)) + a(n - 2 - a(n-2)) for n > 2 with a(0) = a(1) = a(2) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

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