%I #43 Jan 05 2020 07:18:15
%S 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,
%T 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,
%U 11,2,13,0,8,6,10,13,5,14,0,7,12,13,6,8,9,12
%N 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.
%C From _László Kozma_, Aug 04 2016: (Start)
%C Observe that a value k can appear in the sequence only after 0,...,k-1 have already appeared.
%C 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,...
%C It can be shown that if we start from 0, we never reach a cycle.
%C Theorem: this sequence contains every positive integer. (Alternatively: there are infinitely many zeros.)
%C 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.
%C 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.
%C 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
%C A275668 gives the first-occurrence-sequence (or, alternatively, the occurrences of zeros, minus 1).
%C 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)
%C 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
%H Nathaniel Shar, <a href="/A268755/b268755.txt">Table of n, a(n) for n = 1..100000</a>
%e 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.
%Y Cf. A181391. First-occurrence sequence: A275668.
%K nonn,easy
%O 1,5
%A _Nathaniel Shar_, Feb 12 2016
|