A268755 Variant of A181391: For n >= 1, if there exists an m < n such that a(m) = a(n), take the largest such m and set a(n+1) = #{a(m), a(m+1), ..., a(n)}; otherwise, a(n+1) = 0. Start with a(1) = 0.

0, 0, 1, 0, 2, 0, 2, 2, 1, 3, 0, 4, 0, 2, 5, 0, 3, 5, 3, 2, 4, 5, 4, 2, 3, 4, 3, 2, 3, 2, 2, 1, 6, 0, 7, 0, 2, 5, 8, 0, 4, 9, 0, 3, 10, 0, 3, 3, 1, 11, 0, 4, 7, 11, 4, 3, 6, 12, 0, 7, 7, 1, 8, 11, 9, 11, 2, 13, 0, 8, 6, 10, 13, 5, 14, 0, 7, 12, 13, 6, 8, 9, 12

Offset: 1

Author

Nathaniel Shar, Feb 12 2016

Keywords

• nonn
• easy

Comments

From László Kozma, Aug 04 2016: (Start)

Observe that a value k can appear in the sequence only after 0,...,k-1 have already appeared.

Observe that if the sequence were started not from 0 but from some initial sequence, then a cycle could be reached. E.g., ...,1,1,1,1,... or ...,1,2,3,3,1,3,2,3,2,2,1,3,3,...

It can be shown that if we start from 0, we never reach a cycle.

Theorem: this sequence contains every positive integer. (Alternatively: there are infinitely many zeros.)

Proof: suppose otherwise, that the sequence contains only elements up to k. Then there is a last occurrence of 0 in the sequence; let i be its index.

Suppose that after i, all elements of {1,...,k} appear in the sequence. Let x be the element of {1,...,k} with the latest "first appearance" after index i. Since the previous appearance of x is before i, between the two appearances of x we have all elements of {0,1,...,k}, therefore, after x we have "k+1,0", a contradiction.

Thus some element of {1,...,k} does not appear after index i. We argue that k cannot appear more than k times after index i. Otherwise, by the pigeonhole principle, there would be two appearances of k after the same element, say y. Thus: 0,...,y,k,...,y,k. But this is a contradiction, since between the two appearances of y there are at most k-1 distinct values (since 0 and x do not appear). Thus there is a last appearance of k after index i; let us denote its index by i' (i'>i). Thus after i' only elements of {1,...,k-1} appear in the sequence. Repeating the same argument k-2 times, we reach an index i'' after which only element 1 can appear in the sequence. Let j be the smallest index such that from j onwards the sequence contains only 1s. Then the entries at index j-2 and j-1 are "a,a" for some a != 1. But this is a contradiction, since after "a,a,1" not 1 should follow, but some larger value. QED

A275668 gives the first-occurrence-sequence (or, alternatively, the occurrences of zeros, minus 1).

I suggest the name "working set sequence" due to the similarity to concept of "working set" in data structures, e.g. binary search trees. Working set = set of distinct elements queried since last occurrence of current query key in query sequence (i.e., exactly the set whose cardinality we look for here). (End)

Conjecture: every pair of nonnegative integers (x,y) other than (1,1) appear as consecutive entries (a(i) = x, a(i+1) = y, for some i). - László Kozma, Aug 09 2016

Examples

			Example: a(10) = 3. This is because a(9) = 1; the previous occurrence of that number, 1, is at index 3; and in between a(3) and a(9) three distinct numbers occur in the sequence.
		

Links

• Nathaniel Shar, Table of n, a(n) for n = 1..100000

Crossrefs

Cf. A181391. First-occurrence sequence: A275668.