cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A004001 Hofstadter-Conway $10000 sequence: a(n) = a(a(n-1)) + a(n-a(n-1)) with a(1) = a(2) = 1.

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

On Jul 15 1988 during a colloquium talk at Bell Labs, John Conway stated that he could prove that a(n)/n -> 1/2 as n approached infinity, but that the proof was extremely difficult. He therefore offered $100 to someone who could find an n_0 such that for all n >= n_0, we have |a(n)/n - 1/2| < 0.05, and he offered $10,000 for the least such n_0. I took notes (a scan of my notebook pages appears below), plus the talk - like all Bell Labs Colloquia at that time - was recorded on video. John said afterwards that he meant to say $1000, but in fact he said $10,000. I was in the front row. The prize was claimed by Colin Mallows, who agreed not to cash the check. - N. J. A. Sloane, Oct 21 2015
a(n) - a(n-1) = 0 or 1 (see the D. Newman reference). - Emeric Deutsch, Jun 06 2005
a(A188163(n)) = n and a(m) < n for m < A188163(n). - Reinhard Zumkeller, Jun 03 2011
From Daniel Forgues, Oct 04 2019: (Start)
Conjectures:
a(n) = n/2 iff n = 2^k, k >= 1.
a(n) = 2^(k-1): k times, for n = 2^k - (k-1) to 2^k, k >= 1. (End)

Examples

			If n=4, 2^4=16, a(16-i) = 2^(4-1) = 8 for 0 <= i <= 4-1 = 3, hence a(16)=a(15)=a(14)=a(13)=8.

References

  • J. Arkin, D. C. Arney, L. S. Dewald and W. E. Ebel, Jr., Families of recursive sequences, J. Rec. Math., 22 (No. 22, 1990), 85-94.
  • 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.
  • R. K. Guy, Unsolved Problems Number Theory, Sect. E31.
  • D. R. Hofstadter, personal communication.
  • C. A. Pickover, Wonders of Numbers, "Cards, Frogs and Fractal sequences", Chapter 96, pp. 217-221, Oxford Univ. Press, NY, 2000.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • S. Vajda, Fibonacci and Lucas Numbers and the Golden Section, Wiley, 1989, see p. 129.
  • S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

Links

Crossrefs

Cf. A005229, A005185, A080677, A088359, A087686, A093879 (first differences), A265332, A266341, A055748 (a chaotic cousin), A188163 (greedy inverse).
Cf. A004074 (A249071), A005350, A005707, A093878. Different from A086841. Run lengths give A051135.
Cf. also permutations A267111-A267112 and arrays A265901, A265903.

Programs

  • Haskell
    a004001 n = a004001_list !! (n-1)
a004001_list = 1 : 1 : h 3 1  {- memoization -}
  where h n x = x' : h (n + 1) x'
          where x' = a004001 x + a004001 (n - x)
-- Reinhard Zumkeller, Jun 03 2011
  • Magma
    [n le 2 select 1 else Self(Self(n-1))+ Self(n-Self(n-1)):n in [1..75]]; // Marius A. Burtea, Aug 16 2019
  • Maple
    A004001 := proc(n) option remember; if n<=2 then 1 else procname(procname(n-1)) +procname(n-procname(n-1)); fi; end;
  • Mathematica
    a[1] = 1; a[2] = 1; a[n_] := a[n] = a[a[n - 1]] + a[n - a[n - 1]]; Table[ a[n], {n, 1, 75}] (* Robert G. Wilson v *)
  • PARI
    a=vector(100);a[1]=a[2]=1;for(n=3,#a,a[n]=a[a[n-1]]+a[n-a[n-1]]);a \\ Charles R Greathouse IV, Jun 10 2011
  • PARI
    first(n)=my(v=vector(n)); v[1]=v[2]=1; for(k=3, n, v[k]=v[v[k-1]]+v[k-v[k-1]]); v \\ Charles R Greathouse IV, Feb 26 2017
  • Python
    def a004001(n):
    A = {1: 1, 2: 1}
    c = 1 #counter
    while n not in A.keys():
        if c not in A.keys():
            A[c] = A[A[c-1]] + A[c-A[c-1]]
        c += 1
    return A[n]
# Edward Minnix III, Nov 02 2015
  • SageMath
    @CachedFunction
def a(n): # a = A004001
    if n<3: return 1
    else: return a(a(n-1)) + a(n-a(n-1))
[a(n) for n in range(1,101)] # G. C. Greubel, Apr 25 2024
  • Scheme
    ;; An implementation of memoization-macro definec can be found for example from: http://oeis.org/wiki/Memoization
(definec (A004001 n) (if (<= n 2) 1 (+ (A004001 (A004001 (- n 1))) (A004001 (- n (A004001 (- n 1)))))))
;; Antti Karttunen, Oct 22 2014

Formula

Limit_{n->infinity} a(n)/n = 1/2 and as special cases, if n > 0, a(2^n-i) = 2^(n-1) for 0 <= i < = n-1; a(2^n+1) = 2^(n-1) + 1. - Benoit Cloitre, Aug 04 2002 [Corrected by Altug Alkan, Apr 03 2017]

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.