Назовем коэффициентом несократимости знаменателя d отношение количества несократимых правильных дробей со знаменателем d к общему количеству правильных дробей со знаменателем d, например R(12) = 4⁄11.
Можно показать, что коэффициент несократимости

R(d)= φ(d)/(d – 1), где φ – функция Эйлера.

Теперь определим коэффициент сократимости C(d):

C(d)= (d-φ(d))/(d – 1 )
Например, для простых чисел p

C(p)=1/(p-1)

Существует ровно 2 составных d<100, для которых C(d) является дробью с числителем, равным 1: это 15 и 85.
Найдите количество составных d, не превышающих 2×10¹¹, для которых C(d) – дробь с числителем, равным единице.

Рассмотрим область под гиперболой, ограниченную условиями 1≤x и 0≤y≤1/x.
Пусть S₁ – наибольший квадрат, который можно поместить в область под кривой, S₂ – наибольший квадрат, укладывающийся в оставшуюся часть области, и так далее, как показано на рисунке, где каждый квадрат S_n помечен его номером n.

<page-break/>

Припишем каждому квадрату S_n пару чисел, одно из которых указывает, сколько квадратов лежит левее Sn, а другое – сколько квадратов находится ниже S_n.
Например, левее квадрата S₂ расположен единственный квадрат, а ниже него квадратов нет вовсе. Поэтому квадрату S₂ соответствует пара (1,0). Легко видеть, что пара чисел  (1,1) сопоставлена двум квадратам: S₃₂ и S₅₀.
Сумма таких n, для которых квадрату S_n соответствует пара (1,1), равна 32+50=82.
Найдите сумму таких n, для которых квадрату S_n соответствует пара (3,3).

Напомним, что функция Эйлера φ(n) определена для натуральных аргументов n и равна количеству натуральных чисел, не больших n и взаимно простых с ним.
6227180929 является наименьшим числом, для которых φ(n)=13!
Найдите сумму всех n, для которых φ(n)=13!

Дано множество простых чисел, не превышающих 5000:
S = {2, 3, 5, ..., 4999}
Найдите, сколько оно содержит подмножеств, у которых количество элементов нечетно, а сумма элементов является простым числом.
В качестве ответа укажите последние 16 знаков результата.

Найдите количество непустых подмножеств множества

{1²⁵⁰²⁵⁰, 2²⁵⁰²⁴⁹, 3²⁵⁰²⁴⁸,... , 250249², 250250¹},

у которых сумма элементов кратна числу 250. В качестве ответа укажите 16 младших десятичных цифр результата.

Тройку натуральных чисел (a,b,c) будем называть тройкой Кардано, если она удовлетворяет условию:

Например, тройка (2,1,5) является тройкой Кардано.
Найдите, сколько существует троек Кардано при a, b и  c меньших, чем 30 000 000.

Мальчику подарили развивающую игру-пазл "числовая змейка", состоящую из 40 фигурных элементов, которые можно собирать цепочкой один за другим и только в определенной последовательности. Элементы перенумерованы в соответствии с этой последовательностью числами от 1 до 40.

Каждый вечер папе приходится собирать элементы, разбросанные по полу в детской. Он подбирает их по одному случайным образом и сразу ставит на нужное место. При этом они образуют несколько готовых отрезков из нескольких идущих подряд элементов, должным образом соединенных между собой. Понятно, что сначала, до того как папа начинает выкладывать змейку, таких отрезков нет, когда он кладет первый элемент, получается один отрезок, состоящий из единственного элемента, а в конце работы остается  также один отрезок, состоящий из всех 40 элементов. По ходу дела количество готовых отрезков может увеличиваться и уменьшаться, достигая в какой-то момент максимума. Вот пример его работы:

Обозначим через M максимальное количество готовых отрезков, которое достигалось в процессе сборки. В таблице ниже приведено количество вариантов сборки, при которых наблюдаются максимальные числа отрезков M для змейки, состоящей из 10 элементов.

Как видно, наиболее вероятное значение M равно 3, и оно реализуется 1815264 различными способами, а 181526 — это первые шесть значащих цифр данного числа.
Найдите наиболее вероятное значение M для змейки из 40 элементов и количество способов сборки, при которых достигается это число. В качестве ответа укажите первые шесть значащих цифр результата.

Определим f(n) как сумму факториалов цифр числа n. Например, f(342) = 3! + 4! + 2! = 32.
Определим sf(n) как сумму цифр числа f(n). Например, sf(342) = 3 + 2 = 5.
Определим g(i) как наименьшее натуральное n, для которого sf(n) = i. Так, sf(342) = 5 и sf(25) = 5, и при этом можно проверить, что  наименьшим n, для которого sf(n) = 5 является число 25, поэтому g(5) = 25.
Определим sg(i) как сумму цифр числа g(i). Например, sg(5) = 2 + 5 = 7.
Для некоторых i значения sg(i) совпадают. Например, sg(5)=sg(10)=7;
Можно проверить, что сумма различных значений sg(i) при 1 ≤i ≤20 равна 108.
Найдите сумму различных значений sg(i) при 1 ≤i≤150.