У каждого из четырех прямоугольных треугольников со сторонами (9,12,15), (12,16,20), (5,12,13) и (12,35,37) длина одного из катетов равна 12. Можно доказать, что других прямоугольных треугольников с целыми сторонами и катетом длиной 12 нет. Таким образом, различных прямоугольных треугольников с целыми сторонами и катетом длиной 12 существует ровно четыре.
Для какого наименьшего целого числа a количество различных прямоугольных треугольников с целыми сторонами и катетом длиной a в точности равно 39062?

Рассмотрим три семейства функций:

f_1,n(x,y,z) = xⁿ⁺¹ + yⁿ⁺¹ – zⁿ⁺¹

f_2,n(x,y,z) = (x y + y z + z x)*(x^n-1 + y^n-1 – z^n-1)

f_3,n (x,y,z) = – x y z * (x^n-2 + y^n-2 – z^n-2)

и их сумму:

f_n (x,y,z) = f_1,n (x,y,z) + f_2,n (x,y,z) + f_3,n (x,y,z)

Будем называть (x,y,z) золотой тройкой порядка k, если x, y и z – положительные рациональные числа, представимые в виде правильных дробей со знаменателем, не превышающим k, и существует такое целое n, что f_n (x,y,z) = 0

Обозначим через s(x,y,z) = x + y + z.

Найдите сумму всех различных значений s для золотых троек порядка 50. Результат округлите до ближайшего целого. 

Рассмотрим число 44456656. Заметим, что соседние десятичные цифры в его десятичной записи отличаются не более чем на единицу. Будем называть такие натуральные числа ступенчатыми.
Найдите, сколько существует ступенчатых чисел, не превышающих 10⁴⁰ и содержащих в своей десятичной записи все цифры от 0 до 9.

Рассмотрим делители четырех последовательных натуральных чисел 242, 243, 244 и 245:

Число    Делители
242    1, 2, 11, 22, 121, 242
243    1, 3, 9, 27, 81, 243
244    1, 2, 4, 61, 122, 244
245    1, 5, 7, 35, 49, 245

Обратите внимание, что все эти числа имеют одинаковое количество делителей, а именно шесть.
Найдите количество натуральных чисел n, не превышающих 10⁷, для которых числа n, n+1, n+2 и n+3 имеют одинаковое количество делителей.

Сообщение в системе шифрования RSA представляет собой некоторое число m. Если необходимо зашифровать текст, сначала его каким-то известным образом превращают в число, а затем происходит собственно шифрование.

Шифрование осуществляется следующим образом:

• Выбирают два различных простых числа p и q.
• Вычисляют n=pq и φ=(p-1)(q-1). Число n должно быть достаточно велико, чтобы сообщения m попадали в интервал [0,n-1].
• Выбирают целое число e, 1<e<φ, не имеющее общих делителей с φ (gcd(e,φ)=1).
• Из числа m получают зашифрованное сообщение c=m^e mod n (здесь a mod b означает остаток от деления a на b).

Чтобы расшифровать текст, действуют следующим образом:

• Находят число d такое, что ed=1 mod φ
• Для зашифрованного сообщения c, вычисляют m=c^d mod n.

Однако иногда попадаются такие неудачные сочетания e и m, что m^e mod n=m. Будем называть такие сообщения нескрытыми. Необходимо выбирать e таким образом, чтобы нескрытых сообщений было меньше. Например, пусть p=19 и q=37.
Тогда n=19*37=703, и φ=18*36=648.
Если мы выберем e=181, абсолютно все сообщения m (0≤m≤n-1) окажутся нескрытыми, хотя условие gcd(181,648)=1 выполняется. Такой выбор крайне неудачен.
К сожалению, для любого e, выбранного согласно указанным правилам, всегда найдется сколько-то нескрытых сообщений.
Возьмем p=1009 и q=3643. Найдите количество таких e, 1<e<φ(1009,3643),  gcd(e,φ)=1, для которых количество нескрытих сообщений минимально.

Числа 25 и 1123 можно разбить на 2 части так, что в результате разбиения получаются два простых числа: 25 → 2 и 5, 1123 → 11 и 23. Число 1303 также разбивается на 13 и 03 (равное 3), а число 2347 можно разбить двумя способами: 2 и 347, 23 и 47. Сколько существует чисел, меньших 10¹⁰, которые допускают не менее двух разбиений на простые числа?

Возьмем натуральное число N и разделим его на k равных частей r=N/k. Тогда N = r + r + ... + r. Обозначим через P произведение этих частей: P = r × r × ... × r = r^k. Например, если разделить 11 на пять равных частей (11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2), P окажется равным 2.2⁵ = 51.53632. Обозначим через P_max(N) максимальное значение P, которое можно получить для данного значения N. Оказывается, что для N=11 максимум достигается при k=4: P_max= (11/4)⁴= 14641/256 = 57.19140625. Это число является конечной десятичной дробью. Однако для N=8 максимум достигается при разбиении на три части: P_max= 512/27, и это число не может быть представлено в виде конечной десятичной дроби. Определим функцию D(N) как число десятичных знаков после запятой в P_max(N) для случая, когда P_max(N) представимо конечной десятичной дробью. В случае, когда P_max(N) не может быть представлено в виде конечной десятичной дроби, будем считать, что D(N)=0. Например, D(11)=8, D(8)=0. Для 5 ≤ N ≤ 100 ΣD(N)=1027. Найдите ΣD(N) для 5 ≤ N ≤ 10000.

Вова и Дима играют в числовую угадайку: Вова задумывает число, а Дима пытается его угадать. После каждой попытки Вова сообщает Диме количество угаданных цифр. Например, Вова задумал число 1234, а Дима предположил, что число равно 2036. Вова сообщает ему, что угадана одна цифра. Действительно, цифра 3 стоит в обоих числах на одном и том же месте. О том, что есть еще цифра 2, которая есть в обоих числах, но на разных позициях, Вова Диме не говорит.
Вчера Вова задумал 5-значное число, и вот как проходила игра:
1) Дима: 90342;  Вова: 2 цифры угаданы
2) Дима: 70794;  Вова: 0 цифр угадано
3) Дима: 39458;  Вова: 2 цифры угаданы
4) Дима: 34109;  Вова: 1 цифра угадана
5) Дима: 51545;  Вова: 2 цифры угаданы
Получив эту информацию, Дима сообразил, что для задуманного числа осталось всего четыре возможности: 31348, 31442, 39345, 39542. Тогда Дима сделал еще один ход:
6) Дима: 12531;  Вова: 1 цифра угадана
и определил загаданное число:  39542, поскольку других вариантов не осталось.
А сегодня игру решили усложнить. Теперь Вова загадал 16-разрядное число. Вот протокол игры:

Дима долго думал и нашел все оставшиеся варианты. Найдите их и вы, а в качестве ответа укажите их сумму.

В некотором городе построили телефонную сеть на миллион абонентов с шестизначными телефонными номерами. Данные о телефонных звонках фиксировали в базе данных. Перед вами несколько первых записей из нее:

Номера абонентов S_2n-1 и S_2n для данной таблицы мы получили с помощью генератора псевдослучайных чисел Фибоначчи с запаздыванием:
При 1 ≤k≤55, S_k = [100003 - 200003k + 300007k³] (mod 1000000)
При 56 ≤k, S_k = [S_k-24 + S_k-55] (mod 1000000)
(p(mod q) означает остаток от деления p на q)
При необходимости полученные числа дополняли до шести знаков нулями слева.
Мы будем считать, что если X позвонил Y, или наоборот, Y позвонил X, X и Y становятся друзьями. Если X является другом Y, а Y другом Z, то мы также считаем X и Z друзьями, и так далее для сколь угодно длинных цепочек.
Телефонный номер мэра города – 100000. После очередного звонка количество друзей мэра превысило половину населения города. Сколько в этот момент у него оказалось друзей (включая его самого)?

Полупростым называется натуральное число, представимое в виде произведения двух простых чисел (не обязательно различных), например, 15 = 3 × 5; 9 = 3 × 3; 22 = 2 × 11.
Существует ровно десять полупростых чисел, не превышающих 30: 4, 6, 9, 10, 14, 15, 21, 22, 25, 26. Их сумма равна 152.
Найдите сумму полупростых чисел, не превышающих 10⁸.