Число 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¹¹.

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

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

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

Для некоторых простых чисел p можно найти такое натуральное n, для которого выражение n³+ n²p является точным кубом.
Например, если p=19, то 8³+ 8²×19=12³.
Оказывается, для каждого простого p можно найти не более одного подходящего значения n, и есть только четыре подходящих простых числа, не превышающих сотни.
Найдите сумму всех простых чисел, обладающих указанным свойством и не превышающих одного миллиона.

Числа, состоящие только из единиц называют репьюнитами. Обозначим через R(k) репьюнит длиной k, например, R(6) = 111111.

Рассмотрим теперь репьюниты вида R(10ⁿ). Хотя R(10), R(100) и R(1000) не делятся на 17, R(10000) делится на 17 без остатка. Но оказывается, что нет таких n, для которых R(10ⁿ) делилось бы на 19. Из всех простых чисел, меньших ста только четыре, а именно 11, 17, 41 и 73, могут быть делителями R(10ⁿ) для некоторого n.

Найдите сумму всех простых чисел, меньших 200000, которые являются делителями R(10ⁿ) для какого-либо n.

Для натуральных чисел x, y, z их суммы и разности x + y, x - y, x + z, x - z, y + z и y - z являются квадратами натуральных чисел. Найдите минимальное значение x + y.

Найти сумму таких натуральных чисел n, для которых n²+1, n²+3, n²+7, n²+9, n²+13 и n²+21 являются последовательными простыми числами, и n < 150 000 000.

Посмотрите на таблицу. Легко проверить, что максимальная сумма чисел, стоящих подряд вдоль одного из диагональных направлений, равна 16 (= 8 + 7 + 1).

Давайте теперь рассмотрим ту же задачу для таблицы большего размера. Для этого будем использовать генератор случайных чисел Фибоначчи с запаздываниями:
Для 1≤k≤55, s_k = [100003 - 200003·k + 300007·k³)] (mod 1000000) - 500000.
Для 56≤k≤4000000, s_k = [s_k-24 +s_k-55 + 1000000] (mod 1000000) - 500000.
(Здесь x(mod y) означает остаток от деления x на y).
Например, s₁₀ = -393027 и s₁₀₀ = 86613.

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

Попробуем записать число 1/3 в виде суммы обратных квадратов различных натуральных чисел. Например, используя числа {2, 5, 6, 10, 15, 30}:

Используя числа до 45 включительно, это можно сделать четырьмя способами. Вот соответствующие наборы чисел:
{2, 5, 6, 10, 15, 30}
{2, 5, 7, 10, 14, 15, 21, 30}
{2, 4, 12, 14, 15, 20, 28, 42}
{2, 6, 7, 9, 10, 12, 20, 28, 35, 36, 45}
Сколькими способами можно записать 1/3 в виде суммы обратных квадратов различных натуральных чисел, не превышающих 80?