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

Сколько есть способов заполнения полоски из 50 клеток?

Радикалом числа n, rad(n), называют произведение различных простых делителей числа n. Например 1008 = 2⁴×3²×7, следовательно rad(1008) = 2×3×7 = 42.

Если мы вычислим все rad(n) для 1 ≤ n ≤10, отсортируем их по значению rad(n), а затем по значению n (при равных rad(n)), то получим:

До сортировки			После сортировки
n	rad(n)		n	rad(n)	k
1	1		1	1	1
2	2		2	2	2
3	3		4	2	3
4	2		8	2	4
5	5		3	3	5
6	6		9	3	6
7	7		5	5	7
8	2		6	6	8
9	3		7	7	9
10	10		10	10	10

Обозначим через E(k) k-ый элемент в отсортированной колонке n, например, E(4) = 8 и E(6) = 9.

Если rad(n) отсортирован для 1 ≤ n ≤ 100000, найдите сумму всех E(k) для 1 ≤ k ≤ 50000.

Числа, состоящие только из единиц называют репьюнитами. Обозначим через R(k) репьюнит длиной k, например, R(6) = 111111.
Пусть n-натуральное число, взаимно простое с 10. Можно доказать, что всегда существует число k, для которого R(k) кратно n. Обозначим через A(n) минимальное такое число, например, A(7) = 6 и A(41) = 5.
Для любого простого p > 5 число p−1 кратно A(p). Например, при p = 41 A(41) = 5 и 41-1 делится на 5.
Однако изредка попадаются и составные числа, обладающие этим свойством. Первые пять из них: 91, 259, 451, 481 и 703.
Найдите n - пятидесятое взаимно простое с 10 составное число, для которого n−1 делится на A(n).

Числа, состоящие только из единиц называют репьюнитами. Обозначим через R(k) репьюнит длиной k.
Например, R(10) = 1111111111 = 11×41×271×9091, а сумма этих простых сомножителей равна 9414.
Найдите сумму первых двухсот простых сомножителей числа R(12!).

Рассмотрим последовательные простые числа p₁ = 37 и p₂ = 41. Можно убедиться, что число S = 3441, является наименьшим числом, обладающим следующими свойствами:

1) S кратно p₁, и

2) последние цифры S образуют число p₂.

Для любых последовательных простых чисел p₂ >p₁> 5, можно найти наименьшее натуральное S, обладающее свойствами 1 и 2.

Найдите ∑S для всех пар последовательных простых чисел при 7 ≤ p₁ ≤ 1000000.

Обозначим через reverse(n) число, состоящее из тех же цифр, что и натуральное число n, но записанных в обратном порядке.

Для некоторых n в десятичной записи суммы n + reverse(n) используются только нечетные цифры. Такие n назовем обратимыми. Например, числа 36, 63, 409 и 904 обратимы, поскольку 36 + 63 = 99 и 409 + 904 = 1313.

Помня, что десятичная запись чисел не может начинаться с нуля, можно подсчитать, что ровно 120 обратимых чисел не превышают тысячи.

А сколько обратимых чисел не превышает 10²¹?

Легко видеть, что числа в первых пяти строках треугольника Паскаля не делятся на 5:

Однако, рассмотрев первые сто строк, мы найдем, что 2800 чисел из 5050 кратны пяти.
Сколько чисел в первом миллиарде строк будут кратны пяти?

В числовом треугольнике, составленном из целых чисел, мы хотим найти такой числовой треугольник меньшего размера, чтобы сумма составляющих его чисел была максимальна.
В примере на рисунке красным цветом выделен такой максимальный треугольник. Сумма составляющих его чисел равна 42.

 
Теперь мы хотим решить эту задачу для треугольника побольше. Наш треугольник будет состоять из 1000 строк. Чтобы его заполнить, сгенерируем 500500 псевдослучайных чисел s_k в диапазоне от -2¹⁹ до 2¹⁹, используя следующий линейно-конгруэнтный генератор псевдослучайных чисел:
t := 0
для k от 1 до 500500:
    t := (615949*t + 797807) (mod 2²⁰)
    s_k := t-2¹⁹
Тогда получим: s₁ = 273519, s₂ = -153582, s₃ = 450905,  а исходный треугольник будет выглядеть следующим образом

 s₁
s₂  s₃
s₄  s₅  s₆
s₇  s₈  s₉  s_10
...

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

Всем известно, что уравнение x²=-1 не имеет решений для вещественных x.
Однако, перейдя в область комплексных чисел, мы найдем два корня: x=i и x=-i.
Уравнение (x-3)²=-4 имеет два решения: x=3+2i и x=3-2i. Их называют комплексно-сопряженными.
Гауссовыми целыми называют комплексные числа a+bi, у которых a и b целые. Обычные целые числа тоже, конечно, являются гауссовыми целыми с b=0. Чтобы отличить их от гауссовых целых с b≠0, мы будем называть их "рациональными целыми". Гауссово целое будем называть делителем рационального целого n, если частное также является гауссовым целым.
Например, если мы делим 5 на 1+2i, получим

Поскольку 1-2i – гауссово целое, число 1+2i является делителем 5.

С другой стороны, 1+i не является делителем 5, поскольку .

Заметим, что если гауссово целое (a+bi) является делителем рационального целого n, то и комплексно-сопряженное (a-bi) также будет делителем n.
Таким образом, число 5 имеет ровно 6 делителей с положительной вещественной частью: {1, 1 + 2i, 1-2i, 2 + i, 2-i, 5}.
В таблице приведены все делители с положительной вещественной частью первых пяти положительных рациональных целых.

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

Давайте теперь подсчитаем количество путей, ведущих из вершины к каждому из шаров.

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

Таким образом, количество путей, ведущих к данному шарику, равно сумме количеств путей, ведущих к шарикам, расположенным непосредственно над ним (в зависимости от положения их может быть до трех).

То, что мы получили, называют пирамидой Паскаля, а числа на каждом уровне являются коэффициентами в триномиальном разложении выражения (x + y + z)ⁿ.

Найдите, сколько коэффициентов в разложении (x + y + z)¹²³⁴⁵⁶, кратных 4·10¹³.