login
The OEIS is supported by the many generous donors 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

%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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 05:02 EDT 2024. Contains 371235 sequences. (Running on oeis4.)