OFFSET
1,5
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
LINKS
Nathaniel Shar, Table of n, a(n) for n = 1..100000
EXAMPLE
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.
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Nathaniel Shar, Feb 12 2016
STATUS
approved