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

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

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

Обозначим через U(n,m) количество биномиальных коэффициентов C^k_m, которые не делятся ни на 2, ни на 5, где натуральные числа m,n и k удовлетворяют неравенству m≤k<n.

Например, U( 1234567890, 10⁷-10) = 24.

Найдите U(1234567890987654321, 10¹²-10).

Рассмотрим последовательность y₀, y₁, y₂,..., где y_i - 32-битные случайные целые числа, т.е. 0≤y_i<2³², и все значения y равновероятны.

Последовательность x_i задается рекурсивно следующим образом:

• x₀ = 0 и
• x_i = x_i-1 | y_i-1, при i >0. (Символ  | обозначает побитовое ИЛИ)

Ясно, что в конце концов появится такой индекс N для которого xi окажется равным 2³²-1 при всех i≥N.

Найдите математическое ожидание величины N².

Результат умножьте на миллион и округлите вниз до целого.

В этой задаче рассматривается еще одна игра, похожая на ним, где два игрока по очереди берут камни из двух куч. Каждым ходом игрок берет камни из одной кучи в количестве, кратном количеству камней в другой куче. Как обычно, проигрывает тот, кто не может сделать очередной ход, т. е. когда  в одной из куч камней не осталось.

Опишем начальную позицию в виде упорядоченной пары чисел. Например, пара (6, 14) соответствует положению, при котором в меньшей куче 6 камней, а в большей — 14. В этом случае первый игрок может взять из большей кучи 6 или 12 камней.

Выигрышной называется позиция, которая позволяет первому игроку выиграть при верном выборе стратегии. Остальные позиции называются проигрышными. Например, позиции (1,5), (2,6) и (3,12) — выигрышные, поскольку первый игрок может первым же ходом забрать все камни из второй кучи.

Позиции (2,3) и (3,4) — проигрышные, поскольку при любом ходе первого игрока второй участник получает выигрышную позицию.

Обозначим через Z(N) сумму (y_i-x_i) для всех проигрышных позиций (x_i,y_i), 0 < x_i< y_i ≤ N. Можно проверить, что Z(10) = 27 и Z(10⁴) = 24319983959.

Найдите остаток от деления Z(10¹⁶) на 7¹⁰.

Рассмотрим пару последовательностей a_n и s n , заданных следующим образом:

a₁ = 1, s₁ = 1, a_n = s_n-1 mod n, s_n = s_n-1+ a_n×n.

(Здесь и далее "x mod y" означает остаток от деления x на y.)

Первые 10 элементов последовательности an:

1,1,0,3,0,3,5,4,1,9.

Первые 10 элементов последовательности sn:

1,3,3,15,15,33,68,100,109,199.

Обозначим через h(N,M) количество таких пар (p,q), для которых

1≤p≤q≤N  и  (s_p + s_p+1 +… + s_q-1 + s_q ) mod M = 0

Можно проверить, что h(10,10)=5, а соответствующие пары – (1,6), (4,5), (4,9), (6,9) и (8,8).

h(10⁴,10³)= 107796.

Найдите h(10¹²,10⁶).

Любое натуральное число может быть разбито на слагаемые вида 2ⁱ×3^j, где i,j ≥0, но в этой задаче мы будем рассматривать лишь те разбиения, у которых ни одно слагаемое не кратно другому. В дальнейшем будем называть такие разбиения специальными.

Например, разбиение числа 17 = 2 + 6 + 9 = (2¹×3⁰ + 2¹×3¹ + 2⁰×3²) не будет специальным, поскольку 6 кратно 2. Разбиение 17 = 16 + 1 = (2⁴×3⁰ + 2⁰×3⁰) тоже не специальное, так как 16 кратно 1. У числа 17 есть только одно специальное разбиение, а именно 8 + 9 = (2³×3⁰ + 2⁰×3²).

Некоторые числа имеют несколько специальных разбиений. Например, число 11 имеет два специальных разбиения:

11 = 2 + 9 = (2¹×3⁰ + 2⁰×3²) 

11 = 8 + 3 = (2³×3⁰ + 2⁰×3¹)

Обозначим через P(n) количество специальных разбиений числа n. Так, P(11) = 2.

Можно подсчитать, что сумма простых чисел q<100, для которых P(q)=2 равна 641.

Найдите сумму простых q < 1000000, для которых P(q)=2.

Будем вырезать из бумаги в клетку прямоугольники размером w × h клеток, где w и h – натуральные числа. Некоторые из них можно разрезать по клеточкам на две части так, что из этих частей составится новый прямоугольник другого размера.
Например, прямоугольник размером 9 × 4 клетки можно превратить в прямоугольники 18 × 2, 12 × 3 или 6 × 6, как показано на рисунке:

Аналогично, из прямоугольника 9 × 8 можно сделать прямоугольники размером 18 × 4 и 12 × 6 клеток.
Обозначим через F(w, h) количество различных прямоугольников, которые можно получить из прямоугольника размером w × h клеток. При этом прямоугольники с размерами a × b и b × a считаются одинаковыми, а прямоугольники, конгруэнтные исходному, не учитываются.
Тогда получим: F(2,1) = 0, F(2,2) = 1, F(9,4) = 3 и F(9,8) = 2.
Пусть G(N)=Σ F(w, h) для всех 0 < h ≤ w ≤ N.
Можно проверить, что G(10) = 55, G(10³) = 971745, а G(10⁵) = 9992617687.
Найдите ΣG(10^k), где 1≤k≤12. В качестве ответа укажите 8 младших цифр результата.

Пусть  a, b, c – натуральные числа, а функция F(n) определена следующим образом:
F(n) = n - c при n > b
F(n) = F(a + F(a + F(a + F(a + n)))) при n ≤ b. 
Пусть также 

Тогда, например, при a = 50, b = 2000 и c = 40, получим F(0) = 3240, F(2000) = 2040,
а Z(50, 2000, 40) = 5044935.
Найдите остаток от деления Z(21⁷, 7²¹, 12⁷) на 987654321.

Последовательность Голомба {G(n)}  определяют как единственную неубывающую последовательность натуральных чисел, содержащую ровно G(n)  вхождений каждого натурального числа n.
Вот несколько первых значений G(n):

Можно подсчитать, что G(2¹⁰) = 87, G(2²⁰) = 6320, и что ΣG(2ⁿ) = 857297 при 1 ≤ n < 30.

Найдите ΣG(2ⁿ)для 1 ≤ n < 60.