|
%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,changed
%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
|
