login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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
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 (list; graph; refs; listen; history; text; internal format)
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 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

Cf. A181391. First-occurrence sequence: A275668.

Sequence in context: A029314 A071635 A156643 * A128664 A003823 A059451

Adjacent sequences:  A268752 A268753 A268754 * A268756 A268757 A268758

KEYWORD

nonn,easy

AUTHOR

Nathaniel Shar, Feb 12 2016

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified February 20 17:47 EST 2017. Contains 282392 sequences.