Рассмотрим дробь n/d, где n и d - натуральные числа. Если числа n и d - взаимно простые, и n<d, такую дробь называют правильной несократимой.
Если мы возьмем все правильные несократимые дроби с d ≤ 8 и выпишем их в порядке возрастания, то получим следующую последовательность:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
Сумма знаменателей этих дробей:
8+7+6+5+4+7+3+8+5+7+2+7+5+8+3+7+4+5+6+7+8
равна 122.
Если выписать таким же образом правильные несократимые дроби с d ≤ 1 000 000, то какой будет сумма их знаменателей?

Рассмотрим дробь n/d, где n и d - натуральные числа. Если числа n и d - взаимно простые, и n<d, такую дробь называют правильной несократимой.
Если мы возьмем все правильные несократимые дроби с d ≤ 8 и выпишем их в порядке возрастания, то получим следующую последовательность:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
Между 1/3 и 1/2 расположены 3 дроби: 3/8, 2/5, 3/7, а сумма их числителей равна 8.
Если выписать таким же образом все правильные несократимые дроби с d ≤ 10 000, то какова будет сумма числителей дробей, лежащих между 1/3 и 1/2?

Найти наименьшее число n, такое что n! имеет в конце 1000000 нулей.

Пусть A₁=2009, ..., A_k+1=2009^A_k.
Найти последние 40 цифр числа A₂₀₀₉.

Вам необходимо найти спуск по треугольнику с наибольшей суммой - от вершины до основания. Сумма считается по всем числам, через которые проходит путь. Разрешается спускаться прямо вниз, вниз-влево и вниз-вправо (смотрите пример). В ответе укажите максимальную сумму.

Пример:

3

6 2 5

3 1 9 2 3

4 3 1 1 6 2 4

3 7 8 7 8 7 9 6 7

1 1 4 9 0 5 4 8 8 8 5

3 1 5 1 9 3 2 3 2 8 4 6 1

7 0 9 0 7 0 5 1 7 0 8 6 6 3 4

5 2 7 9 4 9 5 1 7 9 1 2 5 8 6 6 3

7 1 0 4 1 2 1 4 0 2 5 2 5 4 6 0 9 4 3

2 2 0 0 8 8 1 1 4 5 2 9 1 3 0 1 9 7 3 7 5

1 5 3 5 9 7 4 4 3 6 6 6 2 5 9 8 6 7 7 8 2 0 6

2 7 9 2 1 5 6 4 0 7 8 1 0 2 0 0 0 1 1 4 8 0 1 5 9

2 3 1 3 7 6 5 2 2 2 0 5 8 6 3 2 7 6 2 3 7 4 7 1 3 1 9

5 0 7 6 1 0 1 4 8 7 4 3 6 0 0 4 9 6 0 7 2 9 5 7 4 0 4 1 7

0 9 8 8 3 8 0 2 4 4 0 5 0 0 7 2 3 3 6 5 1 2 2 6 6 2 6 9 9 8 8

6 8 1 2 0 4 4 7 3 3 6 9 7 8 7 0 4 5 4 2 9 8 2 3 2 7 2 7 4 8 0 7 9

4 8 2 8 2 2 6 6 3 0 2 3 8 5 8 5 8 7 6 6 4 7 0 8 8 8 2 6 9 0 8 5 8 3 3

7 2 9 9 8 4 3 3 7 2 0 9 2 1 9 9 5 8 6 8 2 9 4 5 0 7 1 5 4 6 8 4 0 1 4 5 4

0 0 3 7 9 4 8 6 3 9 5 0 9 1 0 3 5 4 9 1 4 4 9 7 3 2 0 6 5 7 5 0 8 5 0 7 9 4 9

3 1 0 8 3 8 6 8 4 5 9 9 8 8 5 6 6 9 7 1 8 0 5 3 1 9 6 0 4 9 8 9 5 4 1 0 2 4 1 2 7

7 9 5 0 5 5 6 2 2 9 1 8 5 2 1 3 6 3 3 0 7 1 9 5 1 9 8 0 5 7 0 1 7 2 2 0 1 9 7 1 1 6 3

3 0 1 0 4 9 4 9 6 7 4 6 5 4 4 7 3 6 8 3 7 7 6 8 3 7 6 7 4 6 8 0 4 4 3 4 0 4 5 4 9 0 1 5 7

0 0 2 9 2 7 6 8 2 9 4 7 3 0 1 1 0 9 1 3 1 4 7 2 6 7 7 8 8 6 7 5 2 5 4 7 0 7 5 1 9 3 5 0 0 4 6

9 2 1 8 6 1 8 7 6 9 3 8 8 0 3 3 2 3 8 5 5 9 8 9 6 0 2 7 5 5 8 2 4 6 8 7 5 7 7 6 1 9 1 1 4 2 3 0 7

7 5 7 8 0 3 6 4 1 5 7 8 6 6 8 5 0 6 5 4 5 2 6 5 8 7 9 9 0 8 1 1 9 2 7 4 5 7 1 1 7 7 6 8 5 1 5 8 8 9 2

7 0 4 6 6 0 9 6 2 6 3 4 1 1 4 8 3 7 7 3 7 3 9 6 0 5 1 0 9 0 6 0 5 0 8 9 8 1 5 1 8 5 4 1 3 8 4 4 5 7 5 0 3

9 9 7 9 6 7 2 3 8 6 9 3 7 6 8 5 2 8 9 4 7 6 8 3 6 9 5 4 5 4 3 0 9 1 4 1 6 7 7 1 3 8 1 1 7 7 4 2 4 1 1 7 1 6 0

3 1 2 1 4 7 2 7 3 7 1 6 6 8 2 4 1 2 9 7 9 8 6 1 2 0 5 0 4 5 7 1 5 4 2 1 7 6 6 8 1 8 6 3 7 6 1 3 5 0 9 9 7 0 3 3 4

4 2 4 2 5 8 2 2 1 0 0 4 5 9 7 9 6 7 3 5 4 0 5 1 1 7 4 7 5 6 3 8 0 5 4 8 3 9 8 6 9 3 4 9 7 3 7 5 1 1 0 7 6 4 4 6 0 5 8

Сумма для пути в примере: 176.

Функция Эйлера φ(n) определяется так: для любого натурального n>1 её значение равно количеству натуральных чисел, меньших n и взаимно простых с n, по определению φ(1)=1, в частности φ(9)=6 (числа 1, 2, 4, 5, 7, 8 - взаимно просты с числом 9). 

Необходимо найти число n≤=1000000, для которого отношение n²/φ(n) максимально.

Функция Эйлера φ(n) определяется так: для любого натурального n>1 её значение равно количеству натуральных чисел, меньших n и взаимно простых с n, по определению φ(1)=1, в частности φ(9)=6 (числа 1, 2, 4, 5, 7, 8 - взаимно просты с числом 9). 

Значение функции φ(87109) = 79180 интересно тем, что оно может быть получено перестановкой цифр в аргументе функции 87109. Найти такое n, 1<n<10⁷, для которого φ(n) является перестановкой n, а разность n-φ(n) максимальна.

Рассмотрим дробь n/d, где n и d - натуральные числа. Если числа n и d - взаимно простые, и n<d, такую дробь называют правильной несократимой.
Если возьмем все правильные несократимые дроби с d ≤  8, и выпишем их в порядке возрастания, то получим следующую последовательность:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
В этом ряду дробь 3/4 - ближайшая справа от 5/7.
Если выписать таким же образом правильные несократимые дроби с d ≤ 1 000 000 000 000 в порядке возрастания, то какой числитель будет у дроби, ближайшей справа от 5/7?

Для каждого p можно посчитать количество пифагоровых треугольников с таким периметром. Например для 12 и 24 таких треугольников ровно по одному: (3,4,5) и (6,8,10) соответственно. А для периметра 120 таких треугольников уже 3: (30,40,50), (20,48,52), (24,45,51).

Найдите количество периметров p ≤ 10000000, для которых число различных пифагоровых треугольников с данным периметром является простым.

Каждому числу сопоставим сумму факториалов его цифр.

Например: 15 → 1! + 5! = 121

Среди всех чисел есть числа которым сопоставлены они сами. Например 145 → 1! + 4! + 5! = 145

Если для каждого числа строить цепочку чисел, каждый раз применяя данную операцию, легко показать, что числа начиная с какого-то будут повторяться.

Оказывается что циклов длиной более одного всего 3:

169 → 363601 → 1454 → 169

871 → 45361 → 871

872 → 45362 → 872

Также известно, что для чисел меньше 1000000 цепочки, прежде чем числа начнут повторяться, будут содержать не более 60 членов.

Найдите все цепочки максимальной длины начинающиеся с чисел меньших 1000000. В ответе укажите сумму всех первых значений таких цепочек.