Последовательности, которые считают варианты за нас
Теперь вместо отдельных значений появляются целые семейства. Их члены отвечают на вопрос «сколько способов?», когда ручной перебор уже превращается в гарантированный способ что-нибудь забыть. Одни считают множители, другие маршруты, скобки, группы или суммы.
9. Простые числа: атомы целой арифметики
Простое число больше 1 и имеет ровно два положительных делителя: 1 и само себя. Начало ряда выглядит так: 2, 3, 5, 7, 11, 13. Каждое целое число больше 1 раскладывается на простые множители единственным способом с точностью до их порядка. Поэтому простые числа похожи на атомы, из которых собираются составные.
Это не только школьная проверка делимости. Трудность некоторых операций с большими простыми числами лежит в основе криптографических методов. На eCalc можно проверить число на простоту, найти следующее простое, выписать все делители и посчитать функцию Эйлера. У каждого инструмента своя задача, поэтому один тест не стоит выдавать за полную факторизацию.
10. Семья факториалов: похожие знаки, разные задачи
Обычный факториал n! равен произведению чисел от 1 до n. Он считает перестановки n различных объектов: пять книг можно расставить на полке 5! = 120 способами. Калькулятор факториала особенно полезен потому, что результат растёт быстрее, чем интуиция успевает привыкнуть.
У знакомого знака есть родственники. Двойной факториал n!! перемножает числа одной чётности с шагом 2. Субфакториал !n считает перестановки, где ни один объект не остался на месте. Примориал n# перемножает простые числа до n, а суперфакториал sf(n) перемножает 1!, 2!, ..., n!. Пунктуация похожа, но математические вопросы у функций совершенно разные.
11. Числа Фибоначчи: новое из двух предыдущих
Последовательность Фибоначчи начинается с 0 и 1, а каждый следующий член равен сумме двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13. Такое правило появляется в задачах о маршрутах по лестнице, укладке плиток, двоичных строках и динамическом программировании. Если состояние можно получить двумя способами из двух предыдущих состояний, где-то рядом часто прячется Fn.
Калькулятор числа Фибоначчи находит точное Fn по индексу и показывает соседние члены. Спирали и расположение листьев действительно иногда описываются моделями, связанными с этим рядом, но не каждый цветок обязан отчитываться перед Леонардо Пизанским. Сначала нужно увидеть правило роста, и только потом произносить слово «Фибоначчи».
12. Числа Лукаса: знакомая рекурсия с другим стартом
Последовательность Лукаса использует то же сложение двух предыдущих членов, но начинается с 2 и 1: 2, 1, 3, 4, 7, 11, 18. Изменились всего две стартовые точки, а вслед за ними изменился весь ряд. Это хороший урок моделирования: рекуррентное правило описывает движение, но начальные условия выбирают конкретную траекторию.
Числа Лукаса связаны с Фибоначчи множеством тождеств, а более общие последовательности Лукаса используются в теории чисел и тестах простоты. Калькулятор числа Лукаса вычисляет Ln точно даже для индекса, при котором ответ уже содержит тысячи цифр.