읽고 말하기 수열

읽고 말하기 수열은 다음과 같이 시작하는 수열이다. 대한민국에서는 소설인 개미에서 소개되면서 유명해졌기 때문에, 개미 수열이란 이름으로 잘 알려져 있다.

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... 틀:OEIS

이 수열은 앞의 수를 연속된 같은 수의 개수로 묶어서 읽는 방식으로 만들어진다..

반복 길이 부호화 알고리즘에서 이와 비슷한 원리를 이용한다.

공식

a (n + 1) = A 045918 (a (n))

^[1]^[2] 여기서 A045918는 OEIS 수열

또는

a (n) = \sum_{k = 1}^{A 005341 (n)} A 03402 (n, k) \cdot 1 0^{A 005341 (n) - k}

^[3] 여기서 A005341및 A03402는 OEIS 수열

수열은 무한히 길어진다. 초기값을 1이 아닌 다른 정수로 시작해서 똑같은 알고리즘을 적용하여 만들어도 마찬가지로 무한하게 길어진다. 단 한가지 예외는 22로 시작한 수열이다. 이 수열은 22, 22, 22, ...로 길이가 더 이상 늘어나지 않는다.
수열에서 1, 2, 3이 아닌 수는 등장하지 않는다. 이 성질은 초기값 자체에 그 외의 숫자가 들어가거나, 초기값에 연속으로 3개를 초과하는 똑같은 숫자가 들어가지 않는 이상 유효하다.
$L_{i}$ 를 수열의 $i$ 번째 수열의 길이라고 하면,

\lim_{i \to \infty} \frac{L_{i + 1}}{L_{i}} = λ

여기서

λ = 1.303577269 \dots

차수가 71인 대수적 수로 콘웨이 상수라고 부른다. 존 호턴 콘웨이가 이것을 증명했으며, 초기값이 22가 아닌 수열에 대해 같은 값으로 수렴한다.

콘웨이 상수는 다음 다항식의 유일한 양의 실수해이다.

x^{71} - x^{69} - 2 x^{68} - x^{67} + 2 x^{66} + 2 x^{65} + x^{64} - x^{63} - x^{62} - x^{61} - x^{60} - x^{59} +

2 x^{58} + 5 x^{57} + 3 x^{56} - 2 x^{55} - 10 x^{54} - 3 x^{53} - 2 x^{52} + 6 x^{51} + 6 x^{50} + x^{49} + 9 x^{48} - 3 x^{47} -

7 x^{46} - 8 x^{45} - 8 x^{44} + 10 x^{43} + 6 x^{42} + 8 x^{41} - 5 x^{40} - 12 x^{39} + 7 x^{38} - 7 x^{37} + 7 x^{36} + x^{35} -

3 x^{34} + 10 x^{33} + x^{32} - 6 x^{31} - 2 x^{30} - 10 x^{29} - 3 x^{28} + 2 x^{27} + 9 x^{26} - 3 x^{25} + 14 x^{24} - 8 x^{23} -

7 x^{21} + 9 x^{20} + 3 x^{19} - 4 x^{18} - 10 x^{17} - 7 x^{16} + 12 x^{15} + 7 x^{14} + 2 x^{13} - 12 x^{12} - 4 x^{11} -

2 x^{10} + 5 x^{9} + x^{7} - 7 x^{6} + 7 x^{5} - 4 x^{4} + 12 x^{3} - 6 x^{2} + 3 x - 6 = 0