

A011784


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_{k1} 2's, r_{k2} 3's, etc.}; sequence consists of the final elements in each row.


23



1, 2, 2, 3, 4, 7, 14, 42, 213, 2837, 175450, 139759600, 6837625106787, 266437144916648607844, 508009471379488821444261986503540, 37745517525533091954736701257541238885239740313139682, 5347426383812697233786139576220450142250373277499130252554080838158299886992660750432
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


REFERENCES

Richard K. Guy, Unsolved Problems in Number Theory, Section E25.
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.


LINKS

Johan Claes, Table of n, a(n) for n = 1..19
Johnson Ihyeh Agbinya, Computer Board Games of Africa, (2004), see pages 113114.
R. K. Guy, What's left?, Math Horizons, Vol. 5, No. 4 (April 1998), pp. 57.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane and Brady Haran, The Levine Sequence, Numberphile video (2021)
N. J. A. Sloane, Colin Mallows, and Bjorn Poonen, Discussion of A011784. [Scans of pages 150155 and 164 of my notebook "Lattices 77", from JuneJuly 1997.]


FORMULA

Additional remarks: The sequence is generated by this array, the final term in each row forming the sequence:
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
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
...
where we start with the first row {1 1} and produce the rest of the array recursively as follows:
Suppose line n is {a_1, ..., a_k}; then line n+1 contains a_k 1's, a_{k1} 2's, etc.
So the fifth line contains three 1's, two 2's, one 3 and one 4.
The sequence is 1,2,2,3,4,7,14,42,213,2837,175450,...,
where the nth term a(n) is the sum of the elements in row n2
= the number of elements in row n1
= the last element in row n
= the number of 1's in row n+1
= ...
If the nth row is r_{n,i} then
Sum_{i=1..f(n+1)} (a(n+1)  i + 1)*r_{n,i} ) = a(n+3)
Let {a( )} be the sequence; s(i,j) = jth partial sum of the ith row,
L(i) is the length of that row and S(i) = its sum. Then
L(i+1) = a(i+2) = S(i) = s(i,a(i+1));
L(i+2) = SUM(s(i,j));
L(i+3) = SUM(s(i,j)*(1+s(i,j))/2) (Allan Wilks).
Eric Rains and Bjorn Poonen have shown (June 1997) that the log of the nth term is asymptotic to constant times phi^n, where phi = golden number.
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.
The nth 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).
a(n+2) = nth 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
a(n) = A012257(n,a(n+1)).  Reinhard Zumkeller, Aug 11 2014


EXAMPLE

{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}.


MATHEMATICA

(* 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] (* JeanFrançois Alcover, Feb 25 2016 *)
NestList[Flatten@ MapIndexed[ConstantArray[First@ #2, #1] &, Reverse@ #] &, {1, 1}, 10][[All, 1]] (* Michael De Vlieger, Jul 12 2017, same limitations as above *)


PROG

(Haskell)
a011784 = last . a012257_row  Reinhard Zumkeller, Aug 11 2014
(R)
# This works, as with the others, up to 11.
lev2 < function(x = 10, levprev= NULL){
x < floor(x[1])
# levlen is the RLE values
levterm <rep(1, x)
levlen[[1]] < 2
for ( jl in 2:x) {
rk < length(levlen[[jl1]])
for (jrk in 1: rk) {
levlen[[jl]] < c(levlen[[jl]], rep(jrk, times = levlen[[jl1]][rk+1jrk])) }
levterm[jl] < length(levlen[[jl]]) }
return(invisible(list(levlen=levlen, levterm = levterm) ) ) }
# Carl Witthoft, Apr 01 2021


CROSSREFS

Cf. A012257, A014621, A014622.
Sequence in context: A286350 A023105 A281723 * A302487 A032252 A112708
Adjacent sequences: A011781 A011782 A011783 * A011785 A011786 A011787


KEYWORD

nonn,nice


AUTHOR

Lionel Levine (levine(AT)ultranet.com)


EXTENSIONS

a(12) from Colin Mallows, a(13) from N. J. A. Sloane, a(14) and a(15) from Allan Wilks
a(16) from Johan Claes, Jun 09 2004
a(17) (an 85digit number) from Johan Claes, Jun 18 2004
Edited by N. J. A. Sloane, Mar 08 2006
a(18) (a 137digit number) from Johan Claes, Aug 19 2008


STATUS

approved



