Число "гугол" (googol) 10¹⁰⁰ - довольно большое, но сумма его цифр равна 1. Найдите максимальную сумму цифр чисел mⁿ, 0<m<2⁸, 0<n<2⁸.

Известно, что √3 = 1 + 1/(1 + 1/(2 + 1/(1 + 1/(2 + ...

То есть может быть представлен как цепная дробь с периодом (1, 2).

Посчитаем частичные суммы такой цепной дроби:

1 + 1/(1 + 1/2) = 5/3

1 + 1/(1 + 1/(2 + 1/(1 + 1/2))) = 19/11

1 + 1/(1 + 1/(2 + 1/(1 + 1/(2 + 1/(1 + 1/2))))) = 71/41

Следующие частичные суммы дают такие дроби: 265/153, 989/571, 3691/2131, 13775/7953,...

Для последней из записанных дробей - числитель имеет больше цифр чем знаменатель. Среди первых 2009 таких частичных сумм найдите дроби у которых цифр в числителе больше чем в знаменателе. В ответе укажите количество таких дробей.

Рассмотрим спираль из натуральных чисел:

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

Спираль формируется так: в центре 1, а затем числа последовательно  дописываются по спирали против часовой стрелки. Нас интересуют только числа находящиеся на одной горизонтали или вертикали с единицей. Для спирали с длиной стороны 7 доля простых среди них 4/13. Рассмотрите спирали с нечетными длинами сторон. Найдите спираль минимального размера, но большую чем дана в примере, для которой доля простых среди чисел меньше 1/10. В ответе запишите длину стороны такой спирали.

Известно, что оригинал зашифрованного текста написан на русском языке в кодировке - Windows-1251, также известен, алгоритм шифрования:

Задумано кодовое слово из трёх строчных кириллических символов, и затем к его концу просто дописывалось оно же необходимое число раз (например, абвабв...абв).

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

Расшифруйте отрывок, не имея кодового слова. В ответ запишите сумму всех чисел соответствующих номерам символов расшифрованного текста в кодовой странице Windows-1251.

Вот зашифрованный отрывок:

47,11,8,25,11,18,11,197,7,12,1,10,0,13,194,1,197,47,11,23,2,19,0,194,3,197,12,
25,1,7,0,25,15,5,197,10,203,15,12,6,20,10,0,13,17,7,5,14,3,201,194,8,11,0,5,21,
10,0,13,194,7,8,12,8,11,194,4,11,207,31,21,2,6,19,17,12,20,8,3,201,194,4,11,
207,6,0,14,14,19,8,3,197,10,203,10,12,198,14,2,25,30,15,3,201,194,5,20,17,13,1,
2,0,13,194,5,1,10,6,197,6,27,22,1,5,6,12,199,197,13,27,11,13,3,20,25,9,5,9,3,
197,19,11,9,25,14,197,18,11,2,15,5,11,3,27,5,5,6,30,7,203,14,7,1,5,18,26,23,0,
11,197,12,25,197,0,26,0,23,203,13,14,203,13,5,9,0,19,25,8,25,30,197,3,5,14,7,12,
8,7,2,222,194,6,11,194,6,13,194,5,1,15,5,9,17,203,13,5,203,8,10,30,197,15,14,
197,13,27,13,23,5,1,10,0,5,194,9,197,1,5,14,12,9,22,194,25,5,194,4,21,12,26,23,
2,20,197,14,16,20,9,23,201,194,28,23,12,203,13,14,203,8,7,203,9,12,13,0,16,203,
4,25,25,25,194,3,2,0,14,20,16,6,5,194,25,5,194,10,11,9,14,2,15,23,201,194,1,11,
16,5,21,12,2,197,19,25,21,2,15,5,9,11,197,47,11,23,2,19,5,206,203,15,2,1,197,15,
14,197,14,5,3,7,25,197,3,16,23,30,203,13,5,9,0,19,25,8,2,203,8,10,203,11,6,6,5,
194,10,11,9,14,2,15,23,201,194,1,11,16,5,21,12,2,197,12,15,0,18,13,13,14,203,3,
10,9,11,11,203,18,7,0,11,0,14,15,216,203,13,3,5,197,8,11,3,6,16,12,194,13,13,0,
5,12,194,28,0,9,5,7,7,1,197,10,7,0,7,25,197,19,9,11,10,203,11,19,5,4,7,6,8,12,
26,23,10,203,13,194,9,20,7,8,1,2,203,13,14,14,0,16,203,11,19,5,4,7,6,8,17,21,
197,10,203,20,0,5,27,194,6,11,0,24,27,206,203,20,9,5,3,15,24,27,206,203,8,7,3,2,
0,14,20,16,6,22,28,203,9,7,15,13,20,3,8,7,203,4,12,0,0,5,6,25,206,203,8,7,203,4,
12,0,0,5,6,25,194,0,0,1,1,13,23,199,197,13,14,18,7,6,13,206,203,15,12,13,13,206,
203,20,7,27,1,20,11,201,194,6,0,18,9,11,0,203,13,194,25,203,6,197,201,194,12,5,
13,3,20,2,6,8,25,30,197,0,203,9,7,15,13,20,3,8,7,199,197,15,5,197,3,5,14,7,12,8,
30,199,197,19,5,20,16,5,26,27,24,27,194,3,2,194,5,1,15,5,6,12,203,13,5,203,4,7,
26,18,10,26,14,7,6,8,25,30,197,19,5,0,6,3,8,7,6,13,11,203,7,194,26,23,18,11,1,2,
6,13,29,30,197,31,25,13,23,203,11,18,8,5,15,5,7,204,203,56,16,11,197,13,27,11,
19,25,5,29,203,9,25,26,14,30,203,8,7,203,9,12,8,14,2,203,10,18,3,16,12,15,13,16,
23,197,6,5,15,16,5,21,2,7,197,202,25,5,8,203,3,7,199,197,8,11,15,194,6,0,194,7,
11,4,14,23,194,4,21,10,2,23,10,203,15,12,0,1,17,6,22,194,7,30,19,0,25,206,203,
18,16,5,197,12,6,197,15,14,197,14,5,3,7,25,197,8,5,14,6,5,7,2,25,25,203,203,10,
12,25,11,14,24,201,194,28,23,12,203,13,23,203,1,7,0,11,194,13,13,5,6,13,194,26,
11,19,25,11,29,0,11,194,9,197,16,5,9,206,203,18,16,5,4,25,203,14,7,28,13,16,23,
201,194,4,11,16,5,9,17,199,197,21,25,11,194,12,5,194,25,11,194,5,8,10,203,10,12,
0,22,21,11,14,10,203,1,7,6,25,1,3,201,194,3,197,13,5,23,12,7,22,206,203,18,16,5,
197,15,11,197,31,25,11,194,15,0,9,5,197,12,6,13,194,4,11,16,27,5,16,3,14,10,203,
14,17,28,29,10,14,197,1,5,1,25,203,20,0,5,0,11,203,3,10,12,8,10,197,197,47,5,
197,1,0,5,0,6,11,7,203,114,194,7,30,19,0,25,194,22,23,2,203,8,7,203,9,12,8,14,2,
203,10,18,3,12,16,3,197,6,5,15,16,5,21,2,7,197,13,5,23,12,7,22,206,203,18,16,5,
197,12,6,13,194,9,13,6,14,14,10,199,197,21,25,11,194,5,8,10,203,8,7,26,11,14,6,
0,15,6,11,194,4,11,9,14,2,15,16,201,194,3,197,3,16,14,10,203,1,7,2,20,16,9,13,
16,14,14,30,6,11,194,4,11,9,14,2,15,16,197,6,0,26,194,9,20,7,30,197,6,5,9,2,19,
8,10,30,197,50,5,20,16,5,7,25,30,203,194,37,8,10,203,4,25,0,13,194,4,11,9,14,2,
15,16,197,15,14,197,13,5,23,12,7,22,206,203,18,16,5,197,5,11,20,16,11,7,9,20,14,
10,203,10,18,5,6,9,11,23,25,9,5,16,23,197,3,5,14,30,6,22,28,203,4,12,0,25,26,14,
12,194,28,5,19,25,25,28,203,7,18,14,1,15,16,0,194,9,0,27,14,20,16,9,5,194,195,7,
18,14,1,194,22,23,12,25,197,3,16,14,194,7,5,9,5,197,21,24,7,19,25,7,10,25,0,9,
14,8,206,203,10,12,25,11,14,24,197,21,25,11,194,9,21,7,15,8,25,14,197,0,14,28,7,
26,23,0,11,197,6,11,7,2,0,13,19,23,197,0,203,9,2,0,11,14,203,15,12,0,13,21,14,
20,16,9,0,203,199,197,15,5,197,12,6,13,194,4,11,9,14,2,15,16,201,194,6,0,12,10,
16,12,15,13,14,16,201,194,6,0,10,12,4,7,13,8,25,203,4,25,0,13,194,195,10,18,3,
18,10,6,5,194,124,197,13,5,18,7,7,22,194,9,20,7,8,1,2,203,0,19,25,25,194,3,197,
3,24,1,17,25,197,14,6,13,14,16,0,194,3,2,9,14,18,10,25,0,9,3,201,194,9,11,18,5,
3,7,3,201,194,8,11,14,14,11,13,11,23,25,203,13,194,11,14,9,5,10,2,25,30,203,203,
10,12,25,11,14,24,201,194,28,23,12,203,11,15,3,197,17,15,11,0,0,0,16,9,11,18,20,
14,10,203,8,18,11,7,19,25,7,7,6,8,12,2,197,13,5,23,18,14,4,15,5,20,16,3,197,3,5,
14,30,6,11,11,203,13,194,0,27,6,14,12,206,203,14,28,10,26,27,3,16,194,10,11,9,
23,8,17,21,203,194,37,8,10,203,22,6,5,7,9,14,23,0,5,21,29,0,13,194,25,11,11,203,
7,7,28,8,12,2,197,21,14,14,12,9,0,21,14,20,8,5,12,194,4,11,16,27,0,3,6,11,19,25,
13,194,6,5,6,14,3,6,16,197,15,11,197,12,10,14,7,8,18,7,6,13,7,199,197,13,5,23,
18,14,4,15,5,20,16,3,197,19,5,18,17,9,20,16,9,13,29,203,13,194,15,0,29,25,0,9,
23,8,12,26,23,10,199,197,8,5,23,12,27,30,7,203,13,19,4,30,16,16,7,2,14,23,194,
28,0,9,5,7,7,1,197,0,5,197,0,27,0,14,20,197,19,25,21,2,15,5,15,3,26,204,203,43,
15,3,197,17,15,11,0,0,0,16,9,11,18,20,14,10,203,23,12,2,197,0,14,18,15,5,12,206,
203,18,7,0,11,0,14,18,7,26,15,12,2,197,117,203,2,2,7,0,16,6,11,11,203,7,194,27,
0,3,14,8,8,14,197,0,203,20,2,7,11,11,203,10,7,27,7,12,10,30,16,6,11,11,203,17,
12,27,9,7,203,114,194,4,11,16,27,0,3,6,11,19,25,13,194,4,11,16,14,21,7,25,25,
194,25,11,194,7,0,19,25,11,206,203,15,12,25,11,18,5,0,194,24,29,10,10,14,7,6,11,
204,203,53,7,10,0,15,5,15,194,24,4,30,14,23,19,20,197,10,203,23,12,25,18,2,26,
197,4,14,197,3,14,3,10,25,197,0,203,21,17,1,13,194,7,5,16,14,21,10,199,197,15,
20,8,30,1,13,194,15,14,29,203,23,12,8,11,206,203,18,16,5,4,25,203,0,14,24,197,
13,5,19,7,0,11,0,11,14,10,203,13,194,4,11,16,14,21,9,3,197,3,5,14,30,6,11,7,203,
9,7,26,23,12,199,197,10,203,0,14,24,197,6,14,14,2,14,23,19,20,197,9,14,6,21,14,
201,194,1,11,1,15,5,194,10,11,9,23,8,12,14,197,14,14,20,16,5,197,13,5,23,18,24,
23,194,3,14,10,203,10,12,29,0,9,24,27,16,197,197,50,14,4,7,6,11,8,203,8,7,203,7,
7,27,13,16,199,197,21,25,11,3,16,197,17,203,20,10,0,25,15,14,12,26,3,16,194,3,
197,14,24,1,18,14,12,26,3,16,194,14,6,12,203,8,7,203,4,25,0,11,194,26,21,7,15,
20,16,9,197,13,5,9,12,28,25,194,14,6,12,203,4,12,0,13,204,203,45,194,6,5,6,14,3,
6,11,197,15,11,197,12,10,14,7,8,18,7,6,13,7,203,13,194,9,30,18,11,3,7,6,13,7,
203,20,12,28,22,0,26,23,0,3,26,194,9,197,16,5,197,0,27,0,14,20,201,194,1,5,8,
203,9,2,25,25,194,25,21,7,25,197,7,8,11,194,19,13,26,1,22,206,203,22,16,14,29,2,
21,23,194,14,6,12,197,197,202,41,11,11,6,5,194,3,197,14,3,21,203

Некоторые пары простых чисел обладают таким свойством: если записать их подряд в произвольном порядке, то получится тоже простое число. Например, этим свойством обладают числа 3 и 7, поскольку 37 и 73 тоже простые.

Найдите среди простых чисел меньших 10000 все возрастающие четверки простых чисел такие, что любая пара из четверки обладает описанным свойством. Например, такой четвёркой является 3, 7, 109, 673. В разных четверках числа могут повторяться.

Вычислите сумму всех чисел во всех четверках.

Назовём число a представимым n-ной степенью, если существует натуральные числа x и n, такие что a = xⁿ.

Найдите количество n-значных чисел, которые являются представимыми степенью n или n/2.

Например, четырехзначное число 1024 представимо как вторая степень (32²), а число шестизначное число 531441 представимо как шестая степень (9⁶).

Известно, что любое число вида √n, где n - не является полным квадратом, представимо в виде периодической цепной дроби. Например,

Нас будет интересовать количество различных значений в периоде таких цепных дробей. В приведенном примере:

√2=[1;(2)], длина периода: 1, различных значений в периоде: 1;

Приведем еще примеры:

√3=[1;(1,2)], длина периода: 2, различных значений в периоде: 2;
√5=[2;(4)], длина периода: 1, различных значений в периоде: 1;
√6=[2;(2,4)], длина периода: 2, различных значений в периоде: 2;
√7=[2;(1,1,1,4)], длина периода: 4, различных значений в периоде: 2;
√8=[2;(1,4)], длина периода: 2, различных значений в периоде: 2;
√10=[3;(6)], длина периода: 1, различных значений в периоде: 1;
√11=[3;(3,6)], длина периода: 2, различных значений в периоде: 2;
√12= [3;(2,6)], длина периода: 2, различных значений в периоде: 2;
√13=[3;(1,1,1,1,6)], длина периода: 5, различных значений в периоде: 2.

Для всех натуральных n, не больших 2009, не являющихся полными квадратами, найдите количество различных значений в периоде цепной дроби √n. В ответе укажите сумму всех количеств.

Известно, что tg(1) представляется следующей непериодической цепной дробью:

tg(1) = [ 1, 1, 1, 3, 1, 5, ... , 1, 2*k - 1, ... ]

Если рассмотреть цепную дробь только с несколькими первыми, значениями получим приближение tg(1).

Для первого значения приближение tg(1) ~ 1.

Для первых двух: tg(1) ~ 1 + 1/1 = 2.

Трёх: 1 + 1 / ( 1 + 1 / 1 ) = 3/2.

Четырех: 1 + 1 / ( 1 + 1 / ( 1 + 1 / 3 )) = 11/7.

Найдите 2009-ое и 2010-ое приближения цепными дробями tg(1). Вычислите разность этих приближений и запишите в ответ сумму цифр знаменателя этой разности.

Рассмотрим такие диофантовы уравнения:

x²-Dy²=1.

Мы будем искать минимальные (по x) решения этого уравнения в натуральных x и y. Например, для D=13 минимальное решение такое:

649²-13*180²=1.

Легко показать, что для D - полного квадрата решений не существует.

Рассмотрим минимальные решения D <= 10:

3² - 2*2²=1;

2² - 3*1²=1;

9² - 5*4²=1;

5² - 6*2²=1;

8² - 7*3²=1;

3² - 8*1²=1;

19² - 10*6²=1.

Нас будут интересовать только те D, минимальные решения которых больше всех ему предшествующих. Здесь это 2, 5, 10.

Среди всех D≤1000 не полных квадратов, найдите те у которых минимальное решение (по x) больше (по x) всех минимальных решений для меньших D. В ответе укажите сумму таких D.

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

Пример:

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.