В полоске, состоящей из пяти черных квадратов, будем заменять несколько идущих подряд клеток на прямоугольники разных цветов. При этом прямоугольники 2 × 1 будут красного цвета, 3 × 1 - зеленого, 4 × 1 - синего, а прямоугольник длиной 5 клеток окрасим в желтый цвет.

Используя красные прямоугольники, это можно сделать ровно семью способами:

Для зеленых прямоугольников есть три варианта:

Синие прямоугольники можно поставить только двумя способами:

А для желтых прямоугольников возможен один единственный вариант:

Итак, используя цветные прямоугольники какого-либо одного из имеющихся цветов, можно заменить часть черных квадратов в полоске длиной 5 единиц 7 + 3 + 2 + 1 = 13 способами.

Сколькими способами можно заменить цветными прямоугольниками часть черных квадратов в полоске длиной 50 единиц, если можно использовать цветные полоски только одного из имеющихся четырех цветов, и использован хотя бы один цветной прямоугольник? ("Смешивать" цвета нельзя, т.е. как и в примере, каждая полоска может содержать лишь один цвет, не считая черного).

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

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

Используя девять цифр от 0 до 8, объединяя их в группы и переставляя, можно образовать различные числовые множества. В частности, множество {2,61,487,503} состоит исключительно из простых чисел.

Сколько различных множеств можно сформировать, используя ровно один раз каждую цифру от 0 до 8, так, чтобы все элементы множества были простыми?
Замечание: натуральные числа не могут начинаться с нуля.

Число 512 имеет интересное свойство: оно равно сумме своих цифр в некоторой степени: (5+1+2)³=512. Другое число с аналогичным свойством – 614656=28⁴.

Найдите сумму натуральных чисел, равных сумме своих цифр в некоторой целой степени и не превышающих 10¹⁴.

Первое, что приходит в голову, когда нужно возвести число в 15-ю степень, это просто выполнить четырнадцать умножений:

n n ... n = n¹⁵

Если использовать "бинарный" метод, того же результата можно достичь, выполнив всего шесть умножений:

n n = n²
n² n² = n⁴
n⁴ n⁴ = n⁸
n⁸ n⁴ = n¹²
n¹² n² = n¹⁴
n¹⁴ n = n¹⁵

Но оказывается, что количество умножений можно сократить до пяти:

n n = n²
n² n = n³
n³ n³ = n⁶
n⁶ n⁶ = n¹²
n¹² n³ = n¹⁵

Определим m(k) как минимальное количество умножений, необходимое для вычисления n^k; например, m(15) = 5.

Найдите наименьшее значение k, для которого m(k)=12.

Обозначим через p_n n-ое простое число, а через r_n- остаток от деления (p_n-1)ⁿ + (p_n+1)ⁿ на p_n².
Например, при n = 3, p₃ = 5, и 4³ + 6³ = 280 5 mod 25.
Наименьшее значение n, при котором остаток r_n превышает 10⁹ равно 7037.
Найдите наименьшее значение n, для которого r_n >10¹¹.

Радикалом числа 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.

Палиндромами называют числа, десятичные знаки которых расположены симметрично. Палиндром 595 интересен тем, что его можно представить в виде суммы семи последовательных квадратов натуральных чисел: 6² + 7² + 8² + 9² + 10² + 11² + 12².

Существует ровно 5 палиндромов, не превышающих 1000, которые можно представить в виде суммы 5 и более последовательных квадратов. Их сумма равна 2609.

Найдите сумму всех палиндромов, не превышающих 10⁸, которые можно представить в виде суммы 5 и более последовательных квадратов.