Недавно Vaclav Kotesovec написал мне письмо, в котором предложил продолжить его новую последовательность A137432 — число способов расставить максимальное количество (n²) не бьющих друг друга королей на цилиндрической доске 2n×2n.

Меня часто спрашивают о том, как можно вывести огромную формулу в несколько тысяч слагаемых, которая является решением той или иной трудной задачи. Как вообще действовать, чтобы вывести формулы длиной свыше 10000 слагаемых, о которых рассказывается, например, здесь? На самом деле, во-первых, все эти формулы не выводятся, а «угадываются», а во-вторых, в ряде случаев это делается тривиальным образом. Хотя бывают и чрезвычайно сложные ситуации. Здесь я расскажу о самых простых примерах, так сказать, для начала. Речь пойдёт пока только о линейных рекуррентных соотношениях с постоянными коэффициентами.

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