%I #109 Apr 25 2024 10:41:29

%S 1,2,2,3,4,7,14,42,213,2837,175450,139759600,6837625106787,

%T 266437144916648607844,508009471379488821444261986503540,

%U 37745517525533091954736701257541238885239740313139682,5347426383812697233786139576220450142250373277499130252554080838158299886992660750432

%N Levine's sequence. First construct a triangle as follows. Row 1 is {1,1}; if row n is {r_1, ..., r_k} then row n+1 consists of {r_k 1's, r_{k-1} 2's, r_{k-2} 3's, etc.}; sequence consists of the final elements in each row.

%D Richard K. Guy, Unsolved Problems in Number Theory, Section E25.

%D R. K. Guy, What's left?, in The Edge of the Universe: Celebrating Ten Years of Math Horizons, Deanna Haunsperger, Stephen Kennedy (editors), 2006, p. 81.

%H Johan Claes, <a href="/A011784/b011784.txt">Table of n, a(n) for n = 1..19</a>

%H Johnson Ihyeh Agbinya, <a href="http://web.archive.org/web/20050712073151/http://services.eng.uts.edu.au/~agbinya/computer%20games/African_Board_Games.pdf">Computer Board Games of Africa</a>, (2004), see pages 113-114.

%H R. K. Guy, <a href="https://www.jstor.org/stable/25678158">What's left?</a>, Math Horizons, Vol. 5, No. 4 (April 1998), pp. 5-7.

%H Roland Miyamoto, <a href="https://arxiv.org/abs/2402.06618">Polynomial parametrisation of the canonical iterates to the solution of -gamma*g' = g^(-1)</a>, arXiv:2402.06618 [math.CO], 2024. See pp. 16-17.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).

%H N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=KNjPPFyEeLo">The Levine Sequence</a>, Numberphile video (2021)

%H N. J. A. Sloane, Colin Mallows, and Bjorn Poonen, <a href="/A011784/a011784.pdf">Discussion of A011784.</a> [Scans of pages 150-155 and 164 of my notebook "Lattices 77", from June-July 1997.]

%F Additional remarks: The sequence is generated by this array, the final term in each row forming the sequence:

%F 1 1

%F 1 2

%F 1 1 2

%F 1 1 2 3

%F 1 1 1 2 2 3 4

%F 1 1 1 1 2 2 2 3 3 4 4 5 6 7

%F 1 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 7 7 7 8 8 9 9 10 10 11 12 13 14

%F ...

%F where we start with the first row {1 1} and produce the rest of the array recursively as follows:

%F Suppose line n is {a_1, ..., a_k}; then line n+1 contains a_k 1's, a_{k-1} 2's, etc.

%F So the fifth line contains three 1's, two 2's, one 3 and one 4.

%F The sequence is 1,2,2,3,4,7,14,42,213,2837,175450,...,

%F where the n-th term a(n) is the sum of the elements in row n-2

%F = the number of elements in row n-1

%F = the last element in row n

%F = the number of 1's in row n+1

%F = ...

%F If the n-th row is r_{n,i} then

%F Sum_{i=1..f(n+1)} (a(n+1) - i + 1)*r_{n,i} ) = a(n+3)

%F Let {a( )} be the sequence; s(i,j) = j-th partial sum of the i-th row,

%F L(i) is the length of that row and S(i) = its sum. Then

%F L(i+1) = a(i+2) = S(i) = s(i,a(i+1));

%F L(i+2) = SUM(s(i,j));

%F L(i+3) = SUM(s(i,j)*(1+s(i,j))/2) (_Allan Wilks_).

%F Eric Rains and Bjorn Poonen have shown (June 1997) that the log of the n-th term is asymptotic to constant times phi^n, where phi = golden number.

%F This follows from the inequalities S(n) <= a(n)L(n) and S(n+1) >= ([L(n+1)/a(n)]+1) choose 2)*a(n). See N. J. A. Sloane et al., Scans of Notebook pages.

%F The n-th term is approximately exp(a*phi^n)/I, where phi = golden number, a = .05427 (last digit perhaps 6 or 8), I = .277 (last digit perhaps 6 or 8) (Colin Mallows).

%F a(n+2) = n-th row sum of A012257; e.g., 5th row of A012257 is {1, 1, 1, 2, 2, 3, 4} and the sum of elements is 1+1+1+2+2+3+4=14=a(7) - _Benoit Cloitre_, Aug 06 2003

%F a(n) = A012257(n,a(n+1)). - _Reinhard Zumkeller_, Aug 11 2014

%e {1,1}, {1,2}, {1,1,2}, {1,1,2,3}, {1,1,1,2,2,3,4}, {1,1,1,1,2,2,2,3,3,4,4,5,6,7}.

%t (* This script is not suitable for computing more than 11 terms *) nmax = 11; ro = {{2, 1}}; a[1]=1; For[n=2, n <= nmax, n++, ro = Transpose[{Table[#[[2]], {#[[1]]}]& /@ Reverse[ro] // Flatten, Range[Total[ro[[All, 1]]]]}]; Print["a(", n, ") = ", a[n] = ro // Last // Last]]; Array[a, nmax] (* _Jean-François Alcover_, Feb 25 2016 *)

%t NestList[Flatten@ MapIndexed[ConstantArray[First@ #2, #1] &, Reverse@ #] &, {1, 1}, 10][[All, -1]] (* _Michael De Vlieger_, Jul 12 2017, same limitations as above *)

%o (Haskell)

%o a011784 = last . a012257_row -- _Reinhard Zumkeller_, Aug 11 2014

%o (R)

%o # This works, as with the others, up to 11.

%o lev2 <- function(x = 10, levprev= NULL){

%o x <- floor(x[1])

%o # levlen is the RLE values

%o levterm <-rep(1,x)

%o levlen[[1]] <- 2

%o for ( jl in 2:x) {

%o rk <- length(levlen[[jl-1]])

%o for (jrk in 1: rk) {

%o levlen[[jl]] <- c(levlen[[jl]], rep(jrk, times = levlen[[jl-1]][rk+1-jrk])) }

%o levterm[jl] <- length(levlen[[jl]]) }

%o return(invisible(list(levlen=levlen, levterm = levterm) ) ) }

%o # _Carl Witthoft_, Apr 01 2021

%Y Cf. A012257, A014621, A014622.

%K nonn,nice

%O 1,2

%A Lionel Levine (levine(AT)ultranet.com)

%E a(12) from _Colin Mallows_, a(13) from _N. J. A. Sloane_, a(14) and a(15) from _Allan Wilks_

%E a(16) from _Johan Claes_, Jun 09 2004

%E a(17) (an 85-digit number) from _Johan Claes_, Jun 18 2004

%E Edited by _N. J. A. Sloane_, Mar 08 2006

%E a(18) (a 137-digit number) from _Johan Claes_, Aug 19 2008