воскресенье, 27 января 2013 г.

Как получить факториал

Наталия Макарова рассказала мне о новом конкурсе для математиков и программистов, который проводит Al Zimmermann.

Задача здесь - построить последовательность, которая начинается единицей, а заканчивается факториалом некоторого числа. Причём каждый член последовательности, начиная со второго, должен выражаться как сумма, произведение или разность некоторых двух предшествующих ему членов (не обязательно различных).

Вот, например, как раз 7 шагов получить факториал пяти:
1, 2, 3, 6, -5, -30, 150, 120

Здесь между членами последовательности следующие соотношения:

2 = 1 + 1
3 = 1 + 2
6 = 3 + 3
-5 = 1 - 6
-30 = 6 × (-5)
150 = -5 × (-30)
120 = -30 + 150

Особый интерес представляет вопрос, можно ли получить n! менее, чем за n шагов.  Найти 25 минимальных последовательностей, оканчивающихся факториалами чисел от 13 до 37, и должны участники конкурса.

Задача обсуждается на русском научном форуме

Официальный сайт конкурса

Напомню, что я недавно задавал задачку про последовательность, и в комментариях с тех пор дал пару подсказок.

Комментариев нет:

Отправить комментарий

Популярные сообщения