Четыре предмета, один из которых белый (Б), а три остальных – черные (Ч), можно сгруппировать семью способами:

(ЧЧЧБ) (Ч,ЧЧБ) (Ч,Ч,ЧБ) (Ч,Ч,Ч,Б) (Ч,ЧЧ,Б) (ЧЧЧ,Б) (ЧЧ,ЧБ)

Обозначим через f(b,w) количество способов, которыми можно сгруппировать множество из b черных и w белых предметов. Так, f(3,1)=7.

Найдите ∑f(60,p), где сумма берется для всех простых p, не превышающих 50.

Сообщение в системе шифрования 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.

Пусть I_r – множество точек с целыми координатами x и y, лежащих внутри круга радиуса r, т.е. x² + y² < r².

При r=2 I₂ содержит 9 точек (0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1) и (1,-1).

Рассмотрим треугольники, вершинами которых являются точки, принадлежащие I₂. Среди них найдется ровно 8 треугольников, содержащих начало координат в своей внутренней области. Два из них показаны на рисунке, а остальные можно получить поворотами.

При r=3 существует ровно 360 треугольников с вершинами, принадлежащими I₃, содержащих начало координат в своей внутренней области, а для r=5 таких треугольников будет 10600.

Сколько найдется треугольников, все вершины которых принадлежат I₅₀₀, а начало координат лежит в их внутренней области?

Вова и Дима играют в числовую угадайку: Вова задумывает число, а Дима пытается его угадать. После каждой попытки Вова сообщает Диме количество угаданных цифр. Например, Вова задумал число 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⁸.

Рассмотрим различные тройки взаимно простых натуральных чисел x < y  < z < 10⁷ таких, что x²+y²=z². Найдите количество натуральных чисел p < 10⁷, которые не входят ни в одну такую тройку.

В ряду 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,... представлены числа, которые имеют простые делители только числа 2, 3 и 5. Продолжите этот ряд и найдите число в этом ряду, которое находится на месте с номером 10000.