Рассмотрим дробь 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?

В игре "Пятнашки" необходимо в квадратной коробке размера 4х4 переставить пятнадцать произвольно расположенных плашек по порядку, при этом единственным разрешенным действием является перемещение одной из плашек в соседнюю незанятую в коробке позицию (http://ru.wikipedia.org/wiki/Пятнашки). Определите, за какое минимальное количество ходов можно решить данную головоломку при следующем начальном расположении плашек в коробке (незанятая позиция обозначена числом 0):

5 13 2 9 

11 15 7 10 

0 8 12 14 

3 6 4 1

Найти вторую цифру числа 2²⁰⁰⁹.

На газоне, в каждой точке которого с целыми координатами растет один пучок травы, был подстрижен прямоугольный участок с координатами левого нижнего угла (51500, -51515) и правого верхнего угла (98785, 98368). Пучки травы, находящиеся на границе этого прямоугольника, также были подстрижены. В точке с координатами (100000,14) была размещена дождевальная установка, которая имела радиус действия струи 92835. Установка полила все пучки, расстояние от которых до точки (100000,14) не превышало радиуса. Сколько подстриженных пучков травы оказались политыми?

Найти наименьшее число 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.

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

Выберем наименьшее "внешнее" число, в данном случае 4, и соответствующую ему тройку (4,3,2 в данном примере). Начиная с этой тройки, будем двигаться по часовой стрелке, выписывая тройки одну за другой: 4,3,2; 6,2,1; 5,1,3. Получившаяся последовательность однозначно определяется исходным "магическим" кольцом.

Треугольное "магическое" кольцо можно заполнить 8 различными способами, а сумма троек может быть 9, 10, 11 или 12:

Сумма   Последовательность 
9          4,2,3; 5,3,1; 6,1,2
9          4,3,2; 6,2,1; 5,1,3
10        2,3,5; 4,5,1; 6,1,3
10        2,5,3; 6,3,1; 4,1,5
11        1,4,6; 3,6,2; 5,2,4
11        1,6,4; 5,4,2; 3,2,6
12        1,5,6; 2,6,4; 3,4,5
12        1,6,5; 3,5,4; 2,4,6

Каждую последовательность можно объединить в 9-значное число; минимальное такое число для 3-угольного кольца  равно 146362524.

Если числа от 1 до 10, расставить в пятиугольном кольце на втором рисунке, можно аналогичным образом сформировать 16-значную или 17-значную последовательность. Определите минимальное 17-значное число, которое можно получить описанным способом из "магического" пятиугольного кольца.

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

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