A070867 a(1) = a(2) = 1; a(n) = a(n-1 - a(n-1)) + a(n-1 - a(n-2)).

1, 1, 2, 2, 2, 4, 3, 4, 4, 4, 8, 5, 5, 8, 8, 6, 8, 12, 8, 11, 9, 9, 10, 13, 16, 9, 12, 20, 10, 12, 23, 12, 15, 21, 13, 17, 18, 19, 19, 22, 21, 19, 19, 26, 28, 16, 24, 33, 21, 26, 23, 36, 16, 26, 39, 16, 30, 33, 36, 19, 34, 31, 43, 23, 30, 32, 38, 23, 40, 26, 38, 43, 31, 31, 38, 44

Offset: 1

Author

N. J. A. Sloane, May 19 2002

Keywords

• nonn
• easy

References

• S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 129.

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Nick Hobson, Python program for this sequence
• Eric Weisstein's World of Mathematics, Wolfram Sequences
• Index entries for Hofstadter-type sequences

Crossrefs

Cf. A005185, A226222.

Programs

Haskell

a070867 n = a070867_list !! (n-1)
a070867_list = 1 : 1 : zipWith (+)
   (map a070867 $ zipWith (-) [2..] a070867_list)
   (map a070867 $ zipWith (-) [2..] $ tail a070867_list)
-- Reinhard Zumkeller, May 31 2013

Mathematica

a[1]=a[2]=1; a[n_]:= a[n]= a[n-1 -a[n-1]] + a[n-1 -a[n-2]]; Table[a[n], {n, 80}]

Sage

@CachedFunction
def a(n): # A070867
    if (n<3): return 1
    else: return  a(n-1 -a(n-1)) + a(n-1 -a(n-2))
[a(n) for n in (1..80)] # G. C. Greubel, Mar 28 2022

Formula

a(n) = a(n-1 - a(n-1)) + a(n-1 - a(n-2)), with a(1) = a(2) = 1.

Extensions

More terms from John W. Layman, May 21 2002

Erroneous comma in sequence corrected by Nick Hobson, Feb 17 2007