[seqfan] Re: The Annoyance Sequence

[Arthur O'Dwyer]

I suppose 5 is bumped infinitely often simply because its position cycles:
- It is annoyed from position 0 to position 5 (and pop makes 4)
- Something larger than 5 is annoyed (and pop makes 2)
- Something larger than 5 is annoyed (and pop makes 0)
- Repeat.

So there could be another number that is "infinitely annoyed," if (but
*perhaps* not "only if"?)
- it is odd, like 5; and
- it manages to get bumped into a position where everything preceding it in
the sequence is larger than it.
Just looking at the behavior of the list far from the origin, I think
you're right that this never happens. Empirically it doesn't happen in the
first 100'000 elements, and I bet someone not-me can prove that it never
ever happens.

I computed a different sequence from what Ali Sada just posted, though. My
Python program's output starts like this:

Before step 1, the list is: [2, 3, 4, 5, 6, 7, 8]

Before step 2, the list is: [4, 2, 5, 6, 7, 8]

Before step 3, the list is: [5, 6, 7, 4, 8]

Before step 4, the list is: [7, 4, 8, 9, 5, 10, 11, 12, 13, 14]

Before step 5, the list is: [8, 9, 5, 10, 11, 12, 7, 13, 14]

Before step 6, the list is: [5, 10, 11, 12, 7, 13, 14]

Before step 7, the list is: [11, 12, 7, 13, 5, 14, 8]

Before step 8, the list is: [7, 13, 5, 14, 8, 15, 16, 17, 18, 19, 11, 20]

Before step 9, the list is: [5, 14, 8, 15, 16, 17, 7, 18, 19, 11, 20]

Before step 10, the list is: [8, 15, 16, 17, 5, 7, 18, 19, 11, 20]

Before step 11, the list is: [16, 17, 5, 7, 18, 19, 11, 8, 20]

Before step 12, the list is: [5, 7, 18, 19, 11, 8, 20, 21, 22, 23, 24, 25,
16]

Before step 13, the list is: [18, 19, 11, 8, 5, 20, 21, 22, 23, 24, 25, 16]

Before step 14, the list is: [11, 8, 5, 20, 21, 22, 23, 24, 25, 16, 26, 27,
18]

Before step 15, the list is: [5, 20, 21, 22, 23, 24, 25, 16, 26, 27, 11, 18]

Before step 16, the list is: [21, 22, 23, 24, 5, 25, 16, 26, 27, 11, 18]

Before step 17, the list is: [23, 24, 5, 25, 16, 26, 27, 11, 18, 28, 29,
30, 21]

Before step 18, the list is: [5, 25, 16, 26, 27, 11, 18, 28, 29, 30, 21,
31, 32, 23]

Before step 19, the list is: [16, 26, 27, 11, 5, 18, 28, 29, 30, 21, 31,
32, 23]

That is, the sequence we get is the second entries of these lists: 3, 2, 6,
4, 9, 10, 12, 13, 14, 15, 17, 7, 19, 8, 20, 22, 24, 25, *26*,
where Ali Sada had "27" instead of "26" (and the sequence diverges from
there).
Ali, did you compute by hand and make a mistake? or does my program have a
bug? or something even subtler?

Thanks,
Arthur

import sys

N = int(sys.argv[1])

theList = [2,3,4,5,6,7,8]

poppedNumbers = []

for i in range(0, N):

  # print('Before step %d, the list is: %r' % (i+1, theList))

  annoyedNumber = theList[0]

  if (annoyedNumber >= len(theList)):

    theList += list(range(len(poppedNumbers) + len(theList) + 2,
annoyedNumber + 5))

    allNumbers = theList + poppedNumbers

    allNumbers.sort()

    assert allNumbers == list(range(2, len(allNumbers) + 2)), allNumbers

  poppedNumbers += [theList[1]]

  if (annoyedNumber != 5) and (annoyedNumber % 2 == 1) and all(i >
annoyedNumber for i in theList[2:annoyedNumber+1]):

    assert False, annoyedNumber

  theList = theList[2:annoyedNumber+1] + [annoyedNumber] +
theList[annoyedNumber+1:]

print('%r' % poppedNumbers)



On Thu, Jul 20, 2023 at 9:38 AM Allan Wechsler <acwacw at gmail.com> wrote:

> Could it be that 5 is the only number that never appears?
>
>
> On Thu, Jul 20, 2023, 9:21 AM Ali Sada <pemd70 at yahoo.com> wrote:
>
>> Hi Allan,
>>
>> These are the terms I got for this version
>>
>> 3, 2, 6, 4, 9, 10, 12, 13, 14, 15, 17, 7, 19, 8, 20, 22, 24, 25, 27, 11,
>> 16, 30, 32, 18, 34, 36, 37, 21, 40, 41, 42, 44, 45, 26, 48, 49, 50, 52, 29,
>> 54, 31, 56, 58, 23, 33, 61, 35, 63, 65, 67, 38, 69, 28, 70, 72, 74, 75, 43,
>> 78, 79, 81, 82, 83, 84, 86, 87, 89, 51, 91, 93, 53, 95, 97, 98, 99, 39, 57,
>> 102, 104, 105, 106, 60, 109, 110, 111, 113, 114, 115, 46, 117, 118, 119,
>> 120, 68, 123, 124, 126, 71, 128, 130, 131, 132, 134, 76, 136, 77, 138, 139,
>> 141, 80, 143, 145, 147, 148, 59, 151, 85, 153, 155, 47, 88, 62, 158, 90,
>> 161, 162, 163, 164, 165, 94, 167, 168, 170, 171, 172, 174, 176, 177, 178,
>> 179, 101, 181, 183, 103, 73, 186, 187, 189, 107, 191, 108, 194, 195, 197,
>> 199, 112, 201, 203, 204, 206, 207, 208, 210, 212, 64, 214, 216, 121, 218,
>> 66, 219, 221, 222, 223, 224, 226, 127, 228, 230, 129, 232, 234, 235, 92,
>> 133, 238, 240, 241, 242, 244, 245, 96, 247, 249, 250, 251, 253, 142
>>
>> Best,
>>
>> Ali
>>
>> On Wednesday, July 19, 2023 at 10:10:21 PM GMT+1, Allan Wechsler <
>> acwacw at gmail.com> wrote:
>>
>>
>> I always try to make novel definitions simpler, and I came up with this
>> variant of Ali Sada's idea.
>>
>> Start with 2,3,4,5,...
>>
>> At each step, "annoy" the first element, then record the new first
>> element and throw it away. This gives:
>>
>> 3,4,2,5,6,... (pop 3)
>> 2,5,6,7,4,8,9,... (pop 2)
>> 6,7,4,8,9,5,10,11,... (pop 6)
>>
>> The popped numbers in order are 3,2,6,4,9,10,12,...
>>
>> I think this is not a permutation, because there is a collection of
>> numbers that never manage to get emitted, of which I think the smallest is
>> 5. This was all worked out by hand and I would appreciate confirmation.
>>
>> On Tue, Jul 18, 2023 at 1:30 AM Ali Sada via SeqFan <
>> seqfan at list.seqfan.eu> wrote:
>>
>>  Thank you, Allan and Arthur, for answering my question, and for
>> verifying the terms of the sequence. I really appreciate it. Under such
>> temperature (40+ C) all the words came to my mind were negative (annoy,
>> disturb, displace, etc.)
>> And thank you, Mike, for the fascinating analysis. I wish you could have
>> done it my version too! I would love to see the "cool" and the "late" ones!
>>
>> This is the definition I came up with:  Starting with a list of positive
>> integers and setting a(1) = 1, we follow a process: remove each of the a(n)
>> terms to the right of a(n), m, from the list, and then insert it m steps to
>> the right. The number remaining to the right of a(n) becomes a(n+1).
>>  I am sure it needs a lot of corrections and I would really appreciate
>> the help!
>> Best,
>> Ali
>>
>>     On Sunday, July 16, 2023 at 07:10:06 PM GMT+1, Arthur O'Dwyer <
>> arthur.j.odwyer at gmail.com> wrote:
>>
>>  Ali's description makes sense to me. (Although FWIW I don't like the
>> "Annoying Sequence" name; it doesn't seem to convey anything useful about
>> the structure, and it's just... annoying?)
>> Here's a Python program that implements the idea (up to the 50th term):
>>
>>
>>
>> def smartlyTruncatedList(x):
>>
>>
>>   i = len(x)
>>
>>   while (x[i-1] == i):
>>
>>     i -= 1
>>
>>   return x[:i]
>>
>>
>>
>>
>> theList = list(range(1,10000))
>>
>> for i in range(0, 50):
>>
>>   print('Before step %d, the list is: %r' % (i+1,
>> smartlyTruncatedList(theList)))
>>
>>   annoyingNumber = theList[i]
>>
>>   for d in range(0, annoyingNumber):
>>
>>     annoyedNumber = theList[i+1]
>>
>>
>>
>>     assert (i+2+annoyedNumber < len(theList))
>>
>>     theList = theList[:i+1] + theList[i+2:i+2+annoyedNumber] +
>> [annoyedNumber] + theList[i+2+annoyedNumber:]
>>
>>
>>
>>     print('  After %d annoys %d, the list is: %r' % (annoyingNumber,
>> annoyedNumber, smartlyTruncatedList(theList)))
>>
>>
>>
>> And here's the program's output, which agrees with Ali's:
>>
>>
>>
>> Before step 1, the list is: []
>>
>>   After 1 annoys 2, the list is: [1, 3, 4, 2]
>>
>> Before step 2, the list is: [1, 3, 4, 2]
>>
>>   After 3 annoys 4, the list is: [1, 3, 2, 5, 6, 7, 4]
>>
>>   After 3 annoys 2, the list is: [1, 3, 5, 6, 2, 7, 4]
>>
>>   After 3 annoys 5, the list is: [1, 3, 6, 2, 7, 4, 8, 5]
>>
>> Before step 3, the list is: [1, 3, 6, 2, 7, 4, 8, 5]
>>
>>   After 6 annoys 2, the list is: [1, 3, 6, 7, 4, 2, 8, 5]
>>
>>   After 6 annoys 7, the list is: [1, 3, 6, 4, 2, 8, 5, 9, 10, 11, 7]
>>
>>   After 6 annoys 4, the list is: [1, 3, 6, 2, 8, 5, 9, 4, 10, 11, 7]
>>
>>   After 6 annoys 2, the list is: [1, 3, 6, 8, 5, 2, 9, 4, 10, 11, 7]
>>
>>   After 6 annoys 8, the list is: [1, 3, 6, 5, 2, 9, 4, 10, 11, 7, 12, 8]
>>
>>   After 6 annoys 5, the list is: [1, 3, 6, 2, 9, 4, 10, 11, 5, 7, 12, 8]
>>
>> Before step 4, the list is: [1, 3, 6, 2, 9, 4, 10, 11, 5, 7, 12, 8]
>>
>>   After 2 annoys 9, the list is: [1, 3, 6, 2, 4, 10, 11, 5, 7, 12, 8, 13,
>> 14, 9]
>>
>>   After 2 annoys 4, the list is: [1, 3, 6, 2, 10, 11, 5, 7, 4, 12, 8, 13,
>> 14, 9]
>>
>> Before step 5, the list is: [1, 3, 6, 2, 10, 11, 5, 7, 4, 12, 8, 13, 14,
>> 9]
>>
>> [...]
>>
>>
>>
>>   After 116 annoys 52, the list is: [1, 3, 6, 2, 10, 9, 5, 8, 22, 4, 13,
>> 15, 20, 29, 7, 12, 18, 32, 59, 50, 19, 31, 14, 81, 16, 90, 17, 25, 78, 83,
>> 21, 46, 65, 23, 41, 71, 64, 36, 53, 47, 58, 44, 35, 76, 62, 43, 88, 49,
>> 123, 116, [...]
>>
>>
>>
>>
>>
>>
>> On Sun, Jul 16, 2023 at 1:38 PM Ali Sada via SeqFan <
>> seqfan at list.seqfan.eu> wrote:
>>
>>  Hi Alex and Yifan Xe,
>> Thank you very much for your responses.
>> Alex wrote  "I wonder if it's a permutation of the integers"
>> I have seen similar comments on the OEIS regarding permutations of
>> positive integers. TBH, I don't know why we need a proof in these cases.
>> For example, in this sequence we started we the list of positive integers
>> and the algorithm doesn't add or delete any numbers, so, the sequence
>> should be a permutation of positive integers.
>>
>> The question is whether any specific integer is unlucky enough to keep
>> getting bumped out of its position over and over and over forever.For
>> example, we see that the number "77" doesn't appear anywhere in the first
>> 50 terms of the sequence quoted above. Suppose "77" doesn't appear in the
>> first 200 terms (as indeed it doesn't). Suppose it doesn't appear in the
>> first billion terms. Suppose it never appears. If that's the case — if it's
>> the case that "77" never appears in the OEIS sequence — then the OEIS
>> sequence certainly can't be a permutation of the integers.
>> HTH,Arthur
>>
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>