a new twist on Gijswijt's sequence

[Geoffrey Caveney]

Here are a couple twists on Gijswijt's sequence that I do not find in OEIS now:

1. Define a sequence in the same way as Gijswijt's sequence, with the following exception: 

If a(n-1) is even, then a(n) = a(n-1) / 2.

At first this may sound like a random and pointless mongrel sequence with no purpose or significance. However, it is striking that despite the very frequent occurrence of 2's in Gijswijt's sequence, surprisingly it appears that forcing a 1 after each 2 does not fundamentally change the essential nature of the original sequence: it appears that the same types of B blocks and suffix blocks (glue strings) still occur in this altered sequence. Instead of the B block 1,1,2,1,1,2,2,2,3 in Gijswijt's sequence, the altered sequence has the B block 1,1,2,1,1,2,1,2,1,2,1,3.

Please note that this sequence is not equivalent to simply replacing each 2 in Gijswijt's sequence with 2, 1. The latter process would create an initial string 1,1,2,1,1,1, but this sequence does not. The point is that when 2 occurs at the end of a suffix block in Gijswijt's sequence, the following 1 in this "divide evens by 2" variant seamlessly begins the following B block, as in the original sequence. In this situation there is no "extra" 1 inserted into the variant sequence. An extra 1 is only inserted between consecutive 2's within a suffix block.

Naturally this sequence grows more slowly than Gijswijt's. But it does not appear to slow the growth to an extreme extent, such as the a(n) = floor(k/2) variant A091970 does. For example, I estimate the first 4 to occur in this variant around the 312th term, compared with the 220th term in Gijswijt's sequence.

Perhaps this variant sequence may be useful in investigating and resolving issues around the "Finiteness Conjecture" that Gijswijt's procedure applied to any finite initial string of numbers must eventually result in the occurrence of a 1 in the sequence. The fact that this variant requires a 1 to occur after every 2, while preserving the essential properties of Gijswijt's sequence, might forcibly resolve some of the complications and difficulties surrounding the Finiteness Conjecture. It seems impossible to believe, for example, that any finite initial string of 3's and 5's could avoid 1's, 2's, and 4's indefinitely.

=================

2. A more extreme variant to resolve the Finiteness Conjecture by brute force would be a sequence where Gijswijt's procedure is applied for a(n) only if a(n-1) = 1, and if a(n-1) > 1, then a(n) = 1. Even this variant may surprisingly preserve the essential properties of Gijswijt's sequence, while resolving the Finiteness Conjecture entirely. For example, in this extreme variant, after the two B blocks 1,1,2,1,1,2,1,2,1,2,1,3 ; 1,1,2,1,1,2,1,2,1,2,1,3, the suffix block 1,2 still occurs (akin to the suffix block 2 that is term a(19) in Gijswijt's sequence) because after the first 1 in the first B block, term a(1), the word 1,2,1,1,2,1,2,1,2,1,3,1 is repeated in terms a(2)-a(13) and a(14)-a(25). The surprising upshot is that even this sequence with the forced insertion of a 1 after each term >1 may still preserve the essential interesting properties of Gijswijt's sequence.

Upon some contemplation, I suspect that many mathematicians may prefer the latter "extreme variant" (if a(n-1) > 1, then a(n) = 1) over the first variant (if a(n-1) is even, then a(n) = a(n-1) / 2) because it is more internally coherent and the variant procedure is less artificial. But I include both variants in this message in case this instinct is wrong, or in case the extreme variant sequence becomes problematic in some way that the first variant does not.

I find neither variant sequence in OEIS now. However, the B block sequence 1,1,2,1,1,2,1,2,1,2,1,3 occurs within a handful of existing sequences. It is most likely that these are coincidental occurrences. But just in case, I mention A253051, a compressed version of A253050, the mod 2 version of A252867, a set-based version of the Yellowstone permutation A098550.

Geoffrey Caveney