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

[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 возможных подпоследовательности... :)

Всё относительно

[dimview]

По-моему там основная сложность в том, чтобы догадаться, что подпоследовательностей конечное (и небольшое) число. Мне, например, из условия задачи это совершенно неочевидно. Дальше я могу следить за руками, но в самом начале скрывается какая-то неотличимая от магии интуиция.

Когда человек идёт по лесу с лопатой, останавливается, начинает копать и выкапывает клад, меня не удивляет то, что он лопатой глубокую яму выкопал. Я тоже могу яму выкопать, может не так быстро, но могу. А вот как он узнал, где копать надо — это загадка.

Re: Всё относительно

[selik]

Меня восхищают и гораздо более простые задачи.
Например. В системе СИ время и длина - это основные физические величины, которые не из чего, в том числе друг из друга не выводятся.
Кому, как и зачем пришло в голову соединить это "теплое" и "мягкое", получив принципиально новую величину - скорость?
Почему именно путь делим на время, а не наоборот? Почему не умножаем, складываем, вычитаем?
Вот же кто-то когда-то додумался... Это сейчас кажется, что просто, а тогда... Гении, не иначе.

Мы это уже обсуждали

[dimview]

Но на всякий случай повторюсь. Нет принципиальной разницы между основными и производными физическими величинами. Выбор того, какие из величин считать основными не влияет на физику, так же как выбор системы счисления не влияет на математику. Все математические формулы отлично работают в десятичной, двоичной, шестидесятеричной, отрицательно троичной и полутораичной системе счисления.

При желании можно вместо метров в секунду использовать секунды на метр, так же как в Штатах потребление бензина считается в милях на галлон, а не в литрах на 100 километров. Только надо в знаменатель запихивать вместо числителя.

Между временем и длиной есть тесная связь, мы живём в четырёхмерном пространственно-временном континууме (три координаты и время). Разница между пространственными координатами и временными только в том, что у времени противоположный знак в уравнениях Максвелла. Ну и постоянный коэффициент, который скорость света в вакууме.

Re: Мы это уже обсуждали

[selik]

Эт я понял и даже нашёл естественные единицы измерения типа системы Планка. Там длина и время - производные, а не основные величины.
Я про сопоставление тёплого-мягкого :)