A005350 a(1) = a(2) = a(3) = 1, a(n) = a(a(n-1)) + a(n-a(n-1)) for n >= 4. (Formerly M0253)

1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 7, 7, 8, 8, 8, 8, 8, 9, 10, 11, 11, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 15, 16, 16, 17, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 22, 23, 24, 25, 25, 26, 27, 27, 28

Offset

1,4

Comments

a(n) - a(n-1) = 0 or 1 (see the 1991 Monthly reference). - Emeric Deutsch, Jun 06 2005

References

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

Links

T. D. Noe, Table of n, a(n) for n = 1..1000

R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20.

R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]

R. K. Guy and N. J. A. Sloane, Correspondence, 1988.

D. Kleitman, Solution to Problem E3274, Amer. Math. Monthly, 98 (1991), 958-959.

Maple

A005350 := proc(n) option remember; if n<=3 then 1 else procname(procname(n-1)) + procname(n-procname(n-1)); end if; end proc:
seq(A005350(n), n=1..64) ;

Mathematica

a[1] = a[2] = a[3] = 1; a[n_] := a[n] = a[a[n-1]] + a[n-a[n-1]]; Table[a[n], {n, 1, 64}] (* Jean-François Alcover, Feb 11 2014 *)

Prog

(Haskell)
a005350 n = a005350_list !! (n-1)
a005350_list = 1 : 1 : 1 : h 4 1 where
   h x y = z : h (x + 1) z where z = a005350 y + a005350 (x - y)
-- Reinhard Zumkeller, Jul 20 2012
(SageMath)
@CachedFunction
def a(n): return 1 if (n<4) else a(a(n-1)) + a(n-a(n-1))
[a(n) for n in range(1, 100)]  # G. C. Greubel, Nov 14 2022

Crossrefs

Cf. A004001, A005185, A005707.

Sequence in context: A344497 A316628 A153112 * A055037 A227386 A351833

Adjacent sequences: A005347 A005348 A005349 * A005351 A005352 A005353

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, R. K. Guy

Status

approved