A005378 The female of a pair of recurrences.

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

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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"

Crossrefs

Cf. A005379.

Programs

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

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

Formula

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

Extensions

More terms from James Sellers, Jul 12 2000

Comment corrected by Jaroslav Krizek, Dec 25 2011