Продолжите последовательность

[dimview]

1, 11, 21, 1211, 111221, 312211, 13112221, ...

Следующий элемент должен быть...



...1113213211.

Читаем 13112221 как «одна единица, одна тройка, две единицы, три двойки, одна единица». Эта последовательность называется look-and-say sequence, A005150 в OEIS.

Это была приcказка. Сказка в том, что каждое следующее число примено на 30% длиннее. Если быть точным, то если в десятичном представлении i-го элемента последовательности L_i цифр, то L_i+1/L_i стремится к λ≈1.303577 при i, стремящемся к бесконечности.

Доказательство тривиально — достаточно перечислить 92 возможных подпоследовательности, нарисовать матрицу переходов, рассмотреть её как рекуррентное соотношение для длины элементов последовательности, использовать тот факт, что предел отношения элементов последовательности равен спектральному радиусу матрицы переходов, выписать соответствующий многочлен

x⁷¹
-x⁶⁹-2x⁶⁸-x⁶⁷+2x⁶⁶+2x⁶⁵+x⁶⁴-x⁶³-x⁶²-x⁶¹-x⁶⁰
-x⁵⁹+2x⁵⁸+5x⁵⁷+3x⁵⁶-2x⁵⁵-10x⁵⁴-3x⁵³-2x⁵²+6x⁵¹+6x⁵⁰
+x⁴⁹+9x⁴⁸-3x⁴⁷-7x⁴⁶-8x⁴⁵-8x⁴⁴+10x⁴³+6x⁴²+8x⁴¹-5x⁴⁰
-12x³⁹+7x³⁸-7x³⁷+7x³⁶+x³⁵-3x³⁴+10x³³+x³²-6x³¹-2x³⁰
-10x²⁹-3x²⁸+2x²⁷+9x²⁶-3x²⁵+14x²⁴-8x²³-7x²¹+9x²⁰
+3x¹⁹-4x¹⁸-10x¹⁷-7x¹⁶+12x¹⁵+7x¹⁴+2x¹³-12x¹²-4x¹¹-2x¹⁰
+5x⁹+x⁷-7x⁶+7x⁵-4x⁴+12x³-6x²+3x-6

и найти его единственный положительный вещественный корень λ, например, с помощью wxMaxima:

    float(realroots(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, 1e-8));

Источник: Nathaniel Johnston

Comments

[selik]

Эх, не столь силён я в математике :(
Поэтому меня лично покорила вот эта фраза: Доказательство тривиально — достаточно перечислить 92 возможных подпоследовательности... :)