A320838 a(0) = 0, a(n) is the number of x such that a(x) = a(n-1) and there exists no y such that x < y < n and a(y) > a(n-1).

0, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 1, 2, 2, 3, 3, 4, 1, 1, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 1, 2, 2, 3, 3, 4, 2, 1, 1, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 1, 2, 2, 3, 3, 4, 3, 1, 1, 2, 1, 1, 2, 2, 3, 2, 1, 1, 2, 2, 3, 3, 4, 4, 5

Offset: 0

Author

Thomas Anton, Oct 21 2018

Keywords

• nonn

Comments

After the n-th occurrence (with n <= m) of m after a number larger than n comes the segment of the sequence from the first appearance of n to the first appearance of m.

The first appearance of n in this sequence is given by A002104(n).

Examples

			Start with a(0) = 0.
No larger number has occurred yet, and the number of 0's since the start of the sequence is 1, so a(1) = 1.
No larger number has occurred yet, and the number of 1's since the start of the sequence is 1, so a(2) = 1.
Still no larger number has occurred, and the number of 1's since the start of the sequence is 2, so a(3) = 2.
No larger number has occurred yet, and the number of 2's since the start of the sequence is 1, so a(4) = 1.
The number of 1's that have occurred since the last appearance of a larger number is 1, so a(5) = 1.
Etc.
		

Crossrefs

Cf. A002104.

Programs

Mathematica

a[0] = 0; a[n_] := a[n] = Count[Range[0, n-1], x_ /; a[x] == a[n - 1] && ! AnyTrue[ Range[x+1, n-1], a[#] > a[n-1] &]]; a /@ Range[0, 89] (* Giovanni Resta, Oct 22 2018 *)

PARI

lista(nn) = {va = vector(nn); va[1] = 0; for (n=2, nn, nb = 0; forstep (k=n-1, 1, -1, if (va[k] == va[n-1], nb++); if (va[k] > va[n-1], break);); va[n] = nb;); va;} \\ Michel Marcus, Oct 22 2018

Formula

Let s(n) be the first time n appears in the sequence, then s(n) = Sum_{k=0...n-1} (s(n-1)-s(k)+1).