Определим модифицированную последовательность Коллатца как последовательность натуральных чисел, начинающуюся с числа 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.

На плоскости даны четыре точки с целочисленными координатами: 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?

Назовем натуральное число n мощным, если для его любого простого делителя p число n делится также на p².

Назовем натуральное число n точной степенью, если оно является степенью другого натурального числа.

Назовем натуральное число n ахиллесовым, если оно мощное, но не является точной степенью. Например, числа 864 = 2⁵•3³ и 1800 = 2³•3²•5² — ахиллесовы.

Назовем натуральное число S сильно ахиллесовым, если и S, и φ(S) — ахиллесовы.  Здесь φ(S) означает функцию Эйлера. 

Например, число 864 — сильно ахиллесово число, поскольку φ(864) = 288 = 2⁵•3², а число 1800 — ахиллесово, но не сильно ахиллесово, так как φ(1800) = 480 = 2⁵•3¹•5¹.

Существует 2 трехзначных и 5 четырехзначных сильно ахиллесовых чисел, а восьмизначных насчитывается 396.

Найдите количество 18-значных сильно ахиллесовых чисел.

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

S =1234567891011121314151617181920212223242...

Ясно, что десятичная запись каждого натурального числа n встретится в строке S бесконечно много раз. Будем отмечать, где именно встретились такие вхождения. Например, число 12 первый раз встретится, начиная с позиции 1 строки S, а второй раз — с позиции 14, и так далее.

Обозначим через f(n) номер позиции в строке S, с которого начинается n-ое вхождение числа n. Например, f(1)=1, f(5)=81, f(11)=235, а f(7780)=111111365.

Найдите ∑f(11^k), где 1≤k≤6.

Две лестницы длиной x и y опираются на противоположные стены коридора шириной w, как показано на рисунке. Пусть h – высота, на которой лестницы пересекаются. Нас интересуют случаи, когда все четыре числа – x,y,w и h – оказываются целыми.

Например, для x = 70 и y = 119 можно найти пару подходящих целых чисел h = 30 и w = 56. При 0<x<y<200 есть ровно пять пар (x,y), для которых существуют целые h и w, а именно: (70, 119), (74, 182), (87, 105), (100, 116) и (119, 175).

А сколько существует пар (x,y) при 0<x<y<1 000 000, для которых можно подобрать целые значения w и h?

Пусть ABCD – выпуклый четырехугольник с  целыми сторонами, и 1 ≤ AB < BC < CD < AD. Точка O – середина диагонали BD. Будем называть четырехугольник ABCD биклинным, если длины отрезков BO, DO, AO и CO – целые числа, и AO = CO < BO = DO.

Например, когда AB = 19, BC = 29, CD = 37, AD = 43, BD = 48 и AO = CO = 23, четырехугольник ABCD является биклинным.

Обозначим через B(N) количество различных биклинных четырехугольников ABCD с целыми сторонами, у которых |AB|²+|BC|²+|CD|²+|AD|² ≤ N..

Можно проверить, что B(10 000) = 48 и B(1 000 000) = 38108. 

Найдите B(10 000 000 000).