Будем называть натуральное число A александрийским, если есть такие целые p, q, r, что
A = p·q·r и 1/A=1/p+1/q+1/r.
Примером александрийского числа является 630 (p = 5, q = -7, r = -18). Вот семь первых александрийских чисел:
6, 42, 120, 156, 420, 630, 930.
930 – наибольшее александрийское число, не превышающее 1000.
Найдите наибольшее александрийское число, не превышающее 1,5?10¹⁵.

Возьмем вещественное число x.
Наилучшим его приближением со знаменателем, не превышающим d, назовем квадратный корень из несократимой дроби r/s (s≤d), такой, что у любого рационального числа, лежащего ближе к x, чем r/s, знаменатель будет больше, чем d:
|p²/q²-x| < |r²/s²-x| => q>d.
Найдите сумму знаменателей наилучших приближений ³√n со знаменателем, не большим, чем 10¹⁰, для всех простых чисел n, не превышающих 100000.

В игру "Погоня" играет четное количество игроков за круглым столом двумя игральными костями.
В начале игры два игрока, сидящие друг напротив друга, получают каждый по кости. Каждую секунду игроки, получившие кость, делают ход. Для этого они одновременно бросают кубик, и если выпадает 1, они передают кость соседу слева, а если выпадет 6 – соседу справа. В остальных случаях кубик остается у игрока до следующего хода. Игра заканчивается, когда оба кубика после очередного хода окажутся у одного игрока. Этот игрок считается проигравшим.
Однажды за стол сели играть 100 игроков. Их перенумеровали подряд по часовой стрелке. Спустя некоторое время кубики оказались у игроков № 33 и № 77.
Каково ожидаемое время до конца игры?
Ответ дайте в миллисекундах, округлив его до целого.

Рассмотрим число
G(n) = (n²)!/(n!)ⁿ,
где n – натуральное. Несложно показать, что G(n) – тоже натуральное число.
Например, G(3)=1680. Разложим 1680 на простые множители, а затем их сложим:

1680=2⁴×3×5×7=2×2×2×2×3×5×7,
и
2 + 2 + 2 + 2 + 3 + 5 +7 = 23.
Таким образом, сумма простых множителей числа G(3) равна 23.

Найдите сумму простых множителей числа G(4444).

Лёва и Петя поспорили, у кого лучше память, и решили проверить. Для этого они обзавелись генератором случайных чисел, настроили его на получение случайных чисел от 1 до 10 и стали соревноваться, кто больше чисел запомнит. По условию игры участник получает очко, если очередное число все еще хранится в его памяти. Побеждает тот, кто набрал больше очков.

По ходу дела выяснилось, что и Лёва, и Петя могут удержать в голове не более пяти разных чисел. Если игрок уже помнит пять чисел, то чтобы запомнить следующее, не содержащееся к этому моменту в его памяти, он вынужден забыть одно из имеющихся. Однако оказалось, что забывание происходит несколько по-разному:

• Лёва забывает то число, которое не выдавалось генератором наиболее продолжительное время
• Петя забывает то число, которое первым попало в память.

В начале соревнования память игроков свободна.

Вот пример начала игры:

Обозначим количество очков, которые Лёва и Петя набрали после 50 туров через L и P, соответственно. Найдите математическое ожидание величины (L-P)², результат умножьте на 10⁸ и округлите до ближайшего целого.

Английский математик Джон Хортон Конвей изобрел множество математических развлечений, доставляющих не только удовольствие, но и пищу для серьезных размышлений. Одно из его изобретений – язык программирования FRACTRAN, о котором пойдет речь в данной задаче.

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

Вот, например, FRACTRAN-программа, предложенная Конвеем для получения последовательности простых чисел:

17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1.

Записав в память исходное значение 2, получим в памяти ряд чисел в следующей последовательности:

15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

Оказывается, степени двойки в полученной последовательности встречаются только с простыми показателями: 2², 2³, 2⁵, ..., и можно проверить, что данная последовательность будет содержать в порядке возрастания все степени двух с простыми показателями.

Заметим, что для получения 2² из исходного числа 2 потребовалось 19 шагов программы, и при этом три раза происходило умножение на дробь 13/11.

А сколько раз придется выполнить умножение на 13/11 при переходе от исходного числа 2 к 2¹¹¹¹¹⁹?

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

Когда в прибор передают очередное число, оно отображается индикатором, затем отображаются все промежуточные значения, и, наконец, - результат.

Например, если взять число 137, индикатор покажет последовательность "137"→"11"→"2", а затем погаснет до прихода нового числа.

Каждая цифра на индикаторе состоит из нескольких отрезков, как показано на рисунке.

Например, цифра "8" использует семь отрезков – четыре вертикальных и три горизонтальных, цифра "1" состоит из двух вертикальных, а именно, правого верхнего и правого нижнего, а цифра "4" – из четырех отрезков: левого верхнего, правого верхнего и правого нижнего вертикальных и горизонтального, лежащего посередине.

Индикатор потребляет электроэнергию, только когда отрезки включаются или выключаются. Так, включение или выключение числа 2 требует пяти единиц энергии, а числа 7 – четырех единиц энергии.

Сэм и Макс предложили разные конструкции прибора.

Работа прибора Сэма показана на картинке слева. Когда  этот прибор получает число 137, оно отображается на индикаторе, затем полностью гаснет, затем прибор показывает число 11, которое также гаснет, и, наконец, загорается число 2, которое тоже гаснет

В таблице приведен расчет энергопотребления прибора Сэма для числа 137.

"137":(2 + 5 + 4) ?× 2 = 22 переключений ("137" включается и выключается).

"11":(2 + 2) × 2 = 8 переключений ("11" включается и выключается).

"2":(5) × 2 = 10 переключений ("2" включается и выключается).

Всего получается 40 переключений и, соответственно, тратится 40 единиц энергии.

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

Вот, как он будет работать с числом 137:

"137":2 + 5 + 4 = 11 переключений (включение трех цифр числа "137"), 7 переключений (выключение отрезков, не нужных для числа "11"). 0 переключений (число "11" уже и так горит)

"11":3 переключения (выключение первой единички и нижней части второй единички; верхняя часть остается гореть, поскольку она нужна для цифры "2").

"2":4 переключения (включение оставшихся отрезков цифры "2"), 5 переключений (выключение цифры "2").

Итого: 30 переключений.

Понятно, что прибор Макса тратит меньше энергии. Так, при подсчете однозначной суммы цифр для числа 137 экономия составляет 10 единиц энергии.

Найдите общую экономию энергии при подсчете однозначной суммы цифр для всех простых чисел, не превышающих  2×10⁷.

Обозначим через N(i) наименьшее натуральное число n,  факториал которого n! делится на (i!)^1234567890 .

Сумма N(i) для всех составных натуральных i, не превышающих 1000, равна 520804933959105.

Найдите сумму N(i) для всех составных натуральных i, не превышающих 1 000 000. В качестве ответа укажите 18 младших разрядов результата.

Широко известна игра, где один из участников задумывает целое число, а другой пытается его угадать, задавая вопросы. В этой задаче исследуется вариант такой игры, когда задумывают натуральное число из промежутка [1,n], а в качестве вопросов разрешается называть натуральные числа из этого же интервала. При этом стоимость каждого вопроса равна названному числу. Допускаются ответы трех видов:

1. Ты назвал число меньше задуманного.
2. Ты угадал!
3. Ты назвал число больше задуманного.

Требуется определить  задуманное число и при этом минимизировать суммарную стоимость вопросов (в дальнейшем – цена игры). Для данного числа n назовем стратегию оптимальной, если она минимизирует цену игры для самого неудачного задуманного числа.

Например, при n=3 наилучшим первым ходом будет число "2". После этого при любом ответе можно будет точно определить задуманное число, поэтому больше вопросов не потребуется, и цена игры будет равна 2.

Если n=8, мы могли бы выбрать в качестве стратегии "бинарный поиск". Если первым ходом мы назовем число "4", а задуманное число будет больше, чем 4, нам потребуется еще два вопроса. Пусть вторым ходом мы называем число "6". Если задуманное число больше, чем 6, нам потребуется еще один ход, скажем, "7", и цена игры составит 4+6+7=17.

Мы можем существенно улучшить нашу стратегию для n=8, если первым ходом назовем число "5". Если задуманное число больше, чем 5, то вторым ходом мы можем назвать число "7", и этого будет достаточно для нахождения задуманного. Тогда цена игры составит 5+7=12. Если же задуманное число меньше, чем 5, то для его определения достаточно  вторым и третьим ходом назвать "3" и "1", а цена игры составит 5+3+1=9. Поскольку 12 > 9, в худшем случае цена игры при этой стратегии будет равна 12. Получается, что данная стратегия более выгодна, чем предыдущая, и оказывается, что она оптимальна, то есть никакая другая стратегия не может гарантировать для n=8 результат меньший, чем 12.

Пусть C(n) – максимальная цена игры, которая может получиться для оптимальной стратегии в худшем случае. 

Тогда C(1) = 0, C(2) = 1, C(3) = 2 и C(8) = 12.

Можно подсчитать, что  C(100) = 400.

Найдите С(500000).

На каждую клетку доски N×N положили по шашке, окрашенной в белый цвет с одной стороны и в черный цвет с другой.

Каждым ходом разрешается перевернуть одну шашку, а вместе с нею N-1 шашек, стоящих  на одной с ней вертикали, и N-1 шашек, стоящих  на одной с ней горизонтали. Таким образом, каждым ходом игрок должен перевернуть 2×N-1 шашку. Игра заканчивается, когда все шашки будут стоять белой стороной вверх. Ниже приведен пример игры для доски 5×5.

Несложно проверить, чтобы закончить игру из данной начальной позиции, нужно как минимум 3 хода.

Пусть строки и столбцы перенумерованы целыми числами от 0 до N-1.

Построим на доске N×N начальную конфигурацию C_N. Для этого на клетку с координатами x и y положим шашку черной стороной вверх, если (N-1)²≤x²+y²<N², и белой стороной вверх в противном случае. Конфигурацию C₅ мы видели в приведенном примере.

Пусть T(N) – минимальное количество ходов, необходимых для окончания игры из начального положения C_N (если это невозможно T(N) = 0).

Ясно , что T(1)=T(2)=1. Мы видели, что T(5)=3. Можно проверить, что T(10)=29, а T(1000)=395253.

Найдите сумму T(k!) для 1≤k≤12.