login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A366631
Lexicographically earliest sequence such that each set of numbers enclosed by a pair of equal terms, excluding the endpoints, is distinct.
8
1, 1, 2, 1, 2, 3, 2, 4, 2, 3, 4, 5, 3, 6, 3, 5, 6, 7, 3, 8, 4, 5, 7, 8, 7, 8, 9, 4, 7, 9, 10, 4, 9, 10, 11, 4, 10, 12, 4, 11, 13, 4, 12, 13, 12, 13, 14, 4, 15, 4, 14, 15, 16, 4, 17, 6, 8, 10, 14, 16, 17, 16, 17, 18, 9, 15, 17, 18, 19, 11, 16, 19, 20, 18, 19
OFFSET
1,3
COMMENTS
The word 'set' means that every element is unique and order is irrelevant. {2,3}, for example, is equivalent to {3,2,2} and thus both could never appear in the sequence.
Two consecutive equal values enclose the empty set {}, and thus after [a(1), a(2)] = [1, 1] no consecutive equal values will occur again.
Note that we are considering sets between every pair of equal values, not just those that appear consecutively. For example, [2,1,2,3,2] encloses a set, which is {1,2,3}, as well as [2,3,2], which encloses {3}.
It appears that for n >= 21510, a(n + 17796) = a(n) + 2614 (found by Rémy Sigrist). If this linear recurrence is true, every number appears finitely many times.
A value k is banned after all the values in a set enclosed by a(i1) = a(i2) = k, with i1 < i2, and k itself have reoccurred in the sequence after a(i2). Suppose, for example, after the set S1 enclosed by a(i1) and a(i2) every element in S1 has appeared and also a(i3) = k, and then we had a(i4) = k. Then we would have a new set S2 enclosed by a(i2) and a(i4) that is a superset of S1 U {k}. This would contradict the sequence's definition since the set S2 enclosed by a(i2) and a(i4) is identical to the set S3 enclosed by a(i1) and a(i4) because S1 U {a(i2)} adds no new elements.
Assuming the linear recurrence above is true, the number 526 occurs a record number of 44 times in the sequence and it does not occur again after the linear recurrence begins. The same is true of three other values which occur 41, 42, and 43 times in the sequence.
For n > 2, a new value is always followed by the smallest number that has not yet been banned and is distinct from the previous number (i.e. does not form a null set).
If the definition is changed so that endpoints are included, this becomes A008619.
LINKS
Rémy Sigrist, PARI program
EXAMPLE
a(2)=1, establishing the empty set, [1,1] -> {}.
a(4)=1, creating the sets [1,2,1] -> {2} and [1,1,2,1] -> {1,2}, which are distinct from any set that has appeared thus far. Note that 1 is now permanently banned since the next 1 would have to enclose the same set with a(1) as it would with a(2).
a(8)=4: a(8) cannot be 1 since 1 has been banned. 2 would form the empty set with a(7)=2. a(8) cannot be 3 since this would form the set [3,2,3] -> {2}, which already occurred as [1,2,1] -> {2}. a(8)=4 because 4 is a first occurrence and thus forms no sets.
For another example of a banned number, see the last occurrence of 2, which is a(9)=2. a(10) cannot be 2 since this would form the empty set. At a(11), the value 2 is banned forever since any further 2 would form the same set of numbers with a(7)=2 as with a(5)=2. This is because a later term paired with a(5)=2 would only add the values a(7)=2 and a(6)=3, in comparison to a pairing with a(7)=2, which already encloses a(9)=2 and a(10)=3.
PROG
(PARI) See Links section.
(Python)
from itertools import islice
def agen(): # generator of terms
m, a = set(), []
while True:
an, allnew = 0, False
while not allnew:
allnew, an, mn = True, an+1, set()
for i in range(len(a)):
if an == a[i]:
t = tuple(sorted(set(a[i+1:])))
if t in m or t in mn: allnew = False; break
mn.add(t)
yield an; a.append(an); m |= mn
print(list(islice(agen(), 75))) # Michael S. Branicky, Jan 15 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Neal Gersh Tolunsky, Oct 14 2023
EXTENSIONS
More terms from Rémy Sigrist, Oct 15 2023
Edited by Peter Munn, Dec 05 2023
STATUS
approved