A005378 The female of a pair of recurrences. (Formerly M0263)

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

Offset

0,3

Comments

F(n) is not equal to M(n) if and only if n+1 is a Fibonacci number (A000045); a(n) = A005379(n) + A192687(n). - Reinhard Zumkeller, Jul 12 2011

Differs from A098294 at indices n = 0, 17, 20, 22, 25, 27, 29, 30, ... - M. F. Hasler, Jun 29 2014

References

Hofstadter, "Goedel, Escher, Bach", p. 137.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

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

D. R. Hofstadter, Eta-Lore [Cached copy, with permission]

D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]

D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991

J. Shallit, Proving properties of some greedily-defined integer recurrences via automata theory, arXiv:2308.06544 [cs.DM], August 12 2023.

Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 62-67. - from N. J. A. Sloane, May 30 2009

Eric Weisstein's World of Mathematics, Hofstadter Male-Female Sequences.

Index entries for Hofstadter-type sequences

Index entries for sequences from "Goedel, Escher, Bach"

Formula

F(0) = 1; M(0) = 0; F(n) = n-M(F(n-1)); M(n) = n-F(M(n-1)).

Mathematica

f[0] = 1; m[0] = 0; f[n_] := f[n] = n - m[f[n-1]]; m[n_] := m[n] = n - f[m[n-1]]; Table[f[n], {n, 0, 73}] (* Jean-François Alcover, Jul 27 2011 *)

Prog

(Haskell)
a005378 n = a005378_list !! n
a005378_list = 1 : zipWith (-) [1..] (map a005379 a005378_list)
a005379 n = a005379_list !! n
a005379_list = 0 : zipWith (-) [1..] (map a005378 a005379_list)
-- Without memoization the original recursion would be feasible only for small n.
-- Reinhard Zumkeller, Jul 12 2011

Crossrefs

Cf. A005379.

Sequence in context: A098294 A195119 A077467 * A247911 A103355 A347707

Adjacent sequences: A005375 A005376 A005377 * A005379 A005380 A005381

Keyword

nonn,nice,easy

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Jul 12 2000

Comment corrected by Jaroslav Krizek, Dec 25 2011

Status

approved