

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

R. K. Guy, What's left?, Math Horizons, Vol. 5, No. 4 (April 1998), pp. 57.
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));
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


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)
(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) ) ) }


CROSSREFS



KEYWORD

nonn,nice


AUTHOR

Lionel Levine (levine(AT)ultranet.com)


EXTENSIONS

a(17) (an 85digit number) from Johan Claes, Jun 18 2004
a(18) (a 137digit number) from Johan Claes, Aug 19 2008


STATUS

approved



