Попробуем построить признак делимости для делителя 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.

Альберт выбирает натуральное число k и два случайных вещественных числа, a и b, равномерно распределенных на промежутке [0,1]. Затем он вычисляет квадратный корень из суммы (k·a + 1)² + (k·b + 1)² и округляет его вниз до целого. Если результат оказывается равным k, Альберт получает k очков, в противном случае он не получает ничего.
По окончании игры Альберт получает 1000 руб. за каждое очко.
Можно подсчитать, что после 10 туров с k=1, k=2,: k=10 математическое ожидание выигрыша составит примерно 12059 руб. 48 коп.
Каково будет математическое ожидание выигрыша после 10⁵ туров с k=1, k=2, k=3, ..., k=10⁵? Дайте ответ в копейках, округлив его до ближайшего целого.

Сколько существует 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.

На плоскости даны четыре точки с целочисленными координатами: A(a, 0), B(b, 0), C(0, c) и D(0, d), где 0 < a < b и 0 < c < d.

Точка P(x,y) с целочисленными координатами выбрана на отрезке AC так, что треугольники ABP, CDP и BDP оказываются подобными.

Легко показать, что при этом a=c=x+y. Поэтому, задав подходящим образом четверку чисел (x,y,b,d), мы однозначно определим размер и положение наших треугольников.

Например, четверки (x,y,b,d)=(1,1,3,4) и (x,y,b,d)=(1,1,4,3) обе удовлетворяют указанным условиям: каждая из них задает три подобных треугольника. Мы будем считать различными такие четверки, отвечающие взаимно симметричным конфигурациям.

При b+d<100 существует 110 различных четверок, задающих три подобных треугольника.

При b+d<100 000 существует 395662 различных четверок, задающих три подобных треугольника.

Сколько существует различных четверок, задающих три подобных треугольника при b+d<100 000 000?