The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3


%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 22:24 EST 2020. Contains 338858 sequences. (Running on oeis4.)