OFFSET
1,1
COMMENTS
For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined as the number of applications required to reach a singleton.
More formally, a(n) is the maximum possible number of extensions of a seed sequence, s_n = (s(1),...,s(n)) of any n integers, where an extension, s(m+1) for m >= n, is the runs-resistance of s_m = (s(1),...,s(m)), denoted R(s_m). Every such sequence eventually becomes periodic, so its number of extensions is counted up to and including the first full instance of the cycle. For instance, the sequence 1,3,3,3,... is 1-periodic, and will be counted as 1,3; if this is shorter than its seed sequence (e.g., 1,3,3), its number of extensions is counted as zero.
The calculation of a(n) relies on being able to determine whether the extended sequence has become periodic. For n <= 32, it has been sufficient to rely on the following stopping criterion: a(m+1) = a(m); m > 1; and the sequence of run-lengths of s_m has either a single entry or ends in ...ab, where a < b.
Conjecture: No other stopping criteria are necessary to ensure that any sequence will terminate, which also implies that a cycle with period > 1 will never appear.
Some consistently performing seed patterns can be found: ab{c}5, abc{d}5, and aabcd{e}6 result in a number of extensions growing as n+4, 2n+1, and 3n-18, respectively, where {x} means that you fill in the appropriate number of x's to make the seed have n entries. The first pattern dominates for n=5, the second for n=6..19, and the third from n=20 to at least 32. As no faster-growing patterns have been found, a lower bound is a(n) >= 3*n-18.
0 only appears as an extension when n=1, and only as the first extension.
Playing the opposite game: trying find the sequence resulting in the fewest possible extensions is trivial for n > 1; simply pick n 1's.
LINKS
Frederik G. Faye, Python script
EXAMPLE
An example of calculating the runs-resistance would be R((1,0,0)) = 3, since we have to apply the run-lengths operation three times to reach a singleton: (1,0,0) -> (1,2) -> (1,1) -> (2).
For n=2, the seed sequence s_n can be any two integers. While we obviously can't check every combination of two integers, we can make the cases we need to analyze finite by realizing, that all that matters to the runs-resistance is whether the two integers are equal or not. We therefore only need to consider s_n = (a,a) and s_n = (a,b), or aa and ab in short. We now calculate the first extension in either case: R(aa)=1 and R(ab)=2. With these extensions, we now have aa1 and ab2, and we would like to see how many such extensions we can make before the extensions become periodic (e.g., keeps repeating the same number forever). However, at this point (and this point only), we have to consider if a=1 and b=2, respectively, since this affects the calculation of run-lengths. This means that the number of cases we have to analyze doubles to 111 (a=1), aa1 (a!=1), a22 (b=2), and ab2 (b!=2). Extending these until they become periodic, we get 1s, aa134s, a22334s, and ab22454s, respectively, where an "s" means that the number just before it repeats forever. Since ab22454s is the longest, with 5 extensions to the seed sequence, we have a(2)=5.
Note: In the above case, it was sufficient to look at the seed sequences (a,a) and (a,b) in order to capture all possible seed sequences of length 2. To do the same for any n, we just need to realize that the image of the run-length encoding of sequences of length n is given by the compositions of n; for instance, for n=3, the only possible run-lengths of sequences of length 3 are (1,1,1), (1,2), (2,1), and (3), corresponding exactly to the compositions of n. These, in turn, correspond to the run-lengths of all the seed sequences we need to consider for n=3, namely (a,b,c), (a,b,b), (a,a,b), and (a,a,a), respectively.
The following table lists the first few terms and example sequences. "|" separates the seed sequence of n integers from its extensions.
n a(n) Example of longest possible sequence
----------------------------------------------------
1 6 a|0,2,2,4,5,4s
2 5 a,b|2,2,4,5,4s
3 5 a,b,c|2,2,4,5,4s
4 7 a,a,b,4|4,3,3,5,6,4,6s
5 9 a,b,c,c,5|5,3,5,3,5,5,6,5,6s
6 13 a,b,c,d,d,5|5,4,4,3,5,5,4,5,6,6,5,7,6s
7 15 a,b,c,d,d,d,5|5,5,4,4,4,3,5,5,4,5,6,6,5,7,6s
8 17 a,b,c,d,d,d,d,5|5,5,5,4,4,4,4,3,5,5,4,5,6,6,5,7,6s
9 19 a,b,c,d,d,d,d,d,5|5,5,5,5,4,4,4,4,4,3,5,5,4,5,6,6,5,7,6s
10 21 a,b,c,d,d,d,d,d,d,5|5,5,5,5,5,4,4,4,4,4,4,3,5,5,4,5,6,6,5,7,6s
PROG
(Python) # See link by Faye.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Frederik G. Faye, Jan 10 2026
EXTENSIONS
a(33)-a(35) from Sean A. Irvine, Feb 03 2026
STATUS
approved