Для натурального числа n найдем такие натуральные x из промежутка 1<x<n, чтобы остаток от деления x³ на n был равен 1. Их количество обозначим как C(n).
Например, при n=91 мы найдем 8 подходящих значений x, а именно: 9, 16, 22, 29, 53, 74, 79, 81. Поэтому C(91)=8.

Найдите сумму таких n≤10¹¹, для которых C(n)>100.

Рассмотрим уравнение вида a² + b² = N,  где N- некоторое нечетное натуральное число, и будем искать его натуральные решения (a, b), где a четно, и b нечетно.
При N=65 наше уравнение имеет два таких решения:
a=8, b=1 и a=4, b=7.
Обозначим через S(N) сумму значений a для всех решений уравнения a² + b² = N. Тогда S(65) = 8 + 4 = 12.

Найдите ∑S(N) для всех бесквадратных натуральных N,  имеющих простые делители только вида 4k+1, где k – натуральное число и 4k+1 < 150.

Примечание: бесквадратным (свободным от квадратов) называется натуральное число, которое не делится ни на один квадрат, кроме 1.

Попробуем построить признак делимости для делителя p > 1, взаимно простого с 10. Мы хотим найти для каждого натурального n другое число n₁, которое делится на p тогда и только тогда, когда n делится на p. Два целых числа называются равноделимыми на p, если либо они оба делятся на p, либо оба не делятся. Если b – последняя цифра числа n, и n=10a+b, мы будем искать n₁ в виде:
n₁ = a + b ? m.
Остается найти подходящее значение  m < p, которое будем  называть фактором делимости. Тогда для достаточно больших n мы сможем построить убывающую последовательность равноделимых чисел.
Например, для p=113 фактор делимости равен 34.
При n=76275 получим n₁ = 7627 + 5 * 34 = 7797, и оба числа 76275 и 7797 делятся на 113.
При n=12345 получим n₁ = 1234 + 5 * 34 = 1404, и оба числа 12345 и 1404 не делятся на 113.
Сумма факторов делимости для всех простых p вида 4k+3, не превышающих 1000, равна 19961.
Найдите сумму факторов делимости для всех простых p вида 4k+3, не превышающих 2*10⁷.

Определим уравновешенную статую как полимино, удовлетворяющее следующим требованиям:

• Статуя порядка n состоит из n единичных квадратов — блоков и еще одного квадрата — постамента (всего — n+1 квадрат).
• Центр постамента находится в начале координат (x = 0, y = 0).
• Центры всех блоков имеют положительные координаты y, так что постамент находится ниже остальных квадратов.
• Центр масс уравновешенной статуи имеет нулевую горизонтальную координату x.

Подсчитаем количество различных уравновешенных статуй порядка n. При этом статуи, симметричные друг другу относительно вертикальной оси, будем считать одинаковыми. На рисунке показаны уравновешенные статуи порядка 6. Объединив симметричные, получим 18 различных уравновешенных статуй.

Пусть Z(n) – количество уравновешенных статуй порядка n. Тогда  Z(6)=18, Z(10)=964, Z(15)= 360505.

Найдите ∑Z(n)  для 1 ≤ n ≤ 18.

Рассмотрим треугольник, длины сторон которого – целые числа a, b и с, удовлетворяющие неравенству a ≤ b ≤ c.
Будем называть такой треугольник примитивным, если наибольший общий делитель длин его сторон равен 1, т.е. gcd(a, gcd(b,c))=1.

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

Определим модифицированную последовательность Коллатца как последовательность натуральных чисел, начинающуюся с числа a₁, а далее задаваемую рекуррентно по следующим правилам:

• a_n+1 = a_n/3, когда a_n делится на 3. Обозначим такой переход от  a_n к a_n+1 символом "D".
• a_n+1 = (4a_n + 2)/3, если a_n дает остаток 1 при делении на 3. Обозначим этот случай символом "U".
• a_n+1 = (2a_n - 1)/3 , если a_n дает остаток 2 при делении на 3.

Обозначим этот случай символом "d".
Последовательность заканчивается первой встретившейся единицей.
Например, при a₁ =231 получим последовательность чисел {231,77,51,17,11,7,10,14,9,3,1} и соответствующую строку символов - "DdDddUUdDD".
Для a₁ =1004064 получим строку символов DdDddUUdDDDdUDUUUdDdUUDDDUdDD, которая начинается с DdDddUUdDD.

Найдите все a₁<10¹⁵, у которых цепочка символов, соответствующая модифицированной последовательности Коллатца, начинается с dDUddDDUUUUUdDDUdUdDUdDUddUDUd.
В качестве ответа укажите их сумму.

Рассмотрим треугольник со сторонами 6,8 и 10. Легко подсчитать, что и его периметр, и его площадь равны 24, а отношение площади к периметру равно 1.

У треугольника со сторонами 13,14 и 15 периметр равен 42, а площадь — 84 единицам. Отношение площади этого треугольника к его периметру равно 2.

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

Сколько существует 18-значных натуральных чисел n, таких, что сумма цифр n равна сумме цифр числа 137n?

Для натурального числа k обозначим через d(k) сумму его десятичных цифр. Например, d(42) = 4+2 = 6.

Обозначим через S(n) количество натуральных чисел k < 10ⁿ, таких что 

• k делится на 69;
• d(k) = 69. 

Можно подсчитать, что S(9) = 5464, и S(20) = 36035277144875036.

Найдите остаток от деления S(20¹²) на 10⁹.

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

C₀: x²+y²=25
C₁: (x+4)²+(y-4)²=1
C₂: (x-12)²+(y-4)²=65

Линзы, заключенные между окружностями C₀ и C₁ и между C₀ и C₂, закрашены красным.

Обозначим через L(N) количество различных пар чисел (r1,r2), для которых существует линза с радиусами r1 и r2, и 0<r1≤ r2≤ N.

Можно проверить, что L(10) = 30 и L(100) = 3442.

Найдите Σ L(10^k), где 1 ≤ k ≤ 5.