Для каждого натурального числа n определим f(n) как наименьшее натуральное число, кратное n, десятичная запись которого состоит из нулей, двоек и троек.

Например, f(1)=2, f(3)=3, f(4)=f(5)=f(10)=20, f(7)=203, f(9)=333, f(89)= 20203.

Можно подсчитать, что 

f(1)/1 + f(2)/2 + f(3)/3+ ... + f(100)/100 = 19443

Найдите f(1)/1 + f(2)/2 + f(3)/3+ ... + f(10000)/10000

Как известно, последовательность Фибоначчи определяется рекуррентно:

f(0)=0 , f(1)=1, и f(n)=f(n-1)+f(n-2) при n>1.

Найдите Σf(p_i), где p_i – простые числа, и 10¹⁴< p_i <10¹⁴+5*10⁶.

Остаток от деления полученной суммы на 1234567891011 будет ответом к этой задаче.

Как и в стандартной игре Ним, в игре Простой Ним участвуют два игрока, которые по очереди берут камни из трех куч. Каждым ходом игрок может взять из одной кучи некоторое количество камней, если это количество выражается простым числом.

Проигрывает тот, кто не может сделать очередной ход.

Позиция в Простом Ниме характеризуется тройкой неотрицательных целых чисел (a,b,c).

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

Можно подсчитать, что при 0≤a≤b≤c≤29 существует 651 проигрышная позиция.

Найдите, сколько существует проигрышных позиций при 0≤a≤b≤c≤20000.

Рассмотрим вещественное число √2+√3 и рассчитаем его четные степени:

(√2+√3)² = 9.898979485566356...

(√2+√3)⁴ = 97.98979485566356...

(√2+√3)⁶ = 969.998969071069263...

(√2+√3)⁸ = 9601.99989585502907...

(√2+√3)¹⁰ = 95049.999989479221...

(√2+√3)¹² = 940897.9999989371855...

(√2+√3)¹⁴ = 9313929.99999989263...

(√2+√3)¹⁶ = 92198401.99999998915...

Интересно, что количество девяток в дробной части полученных значений не убывает, и можно доказать, что сама дробная часть при больших n стремится к 1.

В этой задаче мы рассматриваем только вещественные числа, которые можно представить в виде √p+√q , где p и q – натуральные числа, p<q, а дробная часть выражения (√p+√q)²ⁿ стремится к 1 при больших n.

Пусть C(p,q,n) — количество девяток после запятой в числе (√p+√q)²ⁿ, а N(p,q) — минимальное значение n, при котором C(p,q,n)≥2013.

Найдите количество чисел вида √p+√q, где 1≤p<q≤2013, для которых N(p,q)>2013.

Пусть последовательность n натуральных чисел x₁, x₂,..., x_n обладает следующими свойствами:

• x₁ = 2
• для всех 1 <  i ≤  n : x_i-1 <  x_i
• для всех i и j из интервала 1 ≤ i, j ≤  n выполняется неравенство (x_i)^j <  (x_j + 1)ⁱ

Существует всего 5 таких последовательностей длины 2, а именно {2,4}, {2,5}, {2,6}, {2,7} и {2,8}, 293 таких последовательности длины 5, например {2,5,11,25,55}, {2,6,14,36,88}, {2,8,22,64,181}.

Пусть t(n) — количество таких последовательностей длины n.

Тогда t(10) = 86195 и t(20) = 5227991891.

Найдите 7 последних цифр Σt(2^k) для 0 ≤ k ≤ 33.

Обозначим через U(n,m) количество биномиальных коэффициентов C^k_m, которые не делятся ни на 2, ни на 5, где натуральные числа m,n и k удовлетворяют неравенству m≤k<n.

Например, U( 1234567890, 10⁷-10) = 24.

Найдите U(1234567890987654321, 10¹²-10).

Вагоны поезда обозначены буквами латинского алфавита: A,B,C,D..., и последовательность вагонов в железнодорожном составе можно задать с помощью соответствующей цепочки букв.

В правильно сформированном составе вагоны должны следовать алфавитном порядке. Добиваются этого на сортировочной станции, где установлен большой поворотный круг.

Когда состав въезжает на круг, несколько последних вагонов отцепляют, после чего локомотив с остальными вагонами съезжает с круга. Вагоны, стоящие на круге, поворачивают на 180 градусов и вновь прицепляют в хвост состава, но уже в обратном порядке. Эту операцию повторяют несколько раз, пока не достигают желаемого результата.

В некоторых случаях сформировать состав совсем просто. Например, когда исходный порядок вагонов ADCB, вагоны можно расцепить между A и D, затем развернуть фрагмент DCB, и, наконец, сцепить вагоны в нужном порядке. Результат достигается всего за один шаг, т.е. за один поворот круга на 180 градусов.

Возможно, процесс можно оптимизировать, но машинист пользуется совсем простым алгоритмом. Сначала он стремиться прицепить вагон A следом за паровозом, затем следом за ним вагон B, и так далее.

Машинист выяснил, что для состава из четырех вагонов потребуется не более 5 шагов. Максимальное количество - 5 операций - требуется для двух начальных последовательностей, а именно DACB и DBAC. Последовательности вагонов, требующие наибольшего количества операций для упорядочения, будем называть пессимальными.

Порядок формирования состава для начальной последовательности  DACB показан на рисунке.

Для состава из шести вагонов машинист составил список пессимальных последовательностей. Список содержал 24 последовательности. Последовательности он расположил в алфавитном порядке, и цепочка DFAECB оказалась на десятом месте от начала.

Представьте, что вам поручили составить список пессимальных последовательностей для составов из 11 вагонов и упорядочить получившийся список в алфавитном порядке.

На каком месте в списке окажется последовательность CIAKBGHFJDE?

Возьмем натуральное число k, и будем выписывать последовательность рациональных чисел a_i = x_i/y_i следующим образом:
a₁ = 1/k
a_i = (x_i-1+1)/(y_i-1-1) при i>1.
При этом все дроби x_i/y_i будем приводить к несократимому виду.
Мы будем продолжать последовательность до тех пор, пока нам не встретится целое число n.
Определим функцию  f(k)  как f(k) = n.
Например, при k = 20:

1/20 → 2/19 → 3/18 = 1/6 → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 = 6

Поэтому f(20) = 6.

Можно проверить, что f(2) = 2, f(3) = 1 и Σf(k³) = 18764 для простых k, не превышающих 100.

Найдите Σf(k³) для простых k, не превышающих 5×10⁶.

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

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

Пусть в начальный момент все клетки доски белые, а муравей находится в точке с координатами x=0 и y=0. Клетки доски ориентированы вдоль координатных осей и имеют единичный размер.
Найдите |x|+|y| после 10¹⁸ шагов.

Сколькими различными способами можно разрезать шестиугольник из 54-х одинаковых равносторонних треугольников по линиям сетки на три конгруэнтных n–угольника?

Разрезания, являющиеся симметрическими отображениями друг друга, считать только один раз. Т.е., нужно найти количество «неконгруэнтных разрезаний».