Будем называть четное натуральное число N приемлемым, если все его различные простые делители являются последовательными простыми числами. В частности, все положительные степени 2 являются приемлемыми. Число N=630 приемлемо, поскольку оно четно, а его различные простые множители – 2,3,5,7 – это последовательные простые числа. Число N=660 неприемлемо, поскольку в последовательности его простых множителей – 2,3,5,11 – пропущено простое число 7. 

Если N – приемлемое число, то наименьшее число M>1, для которого N+M – простое число, будем называть псевдо-форчуновым числом приемлемого числа N.

Найдите наименьшее приемлемое N, для которого псевдо-форчуново число равно 97.

Для натурального числа k обозначим через d(k) сумму его десятичных цифр. Например, d(42) = 4+2 = 6.

Обозначим через S(n) количество натуральных чисел k < 10ⁿ, таких что 

• k делится на 69;
• d(k) = 69. 

Можно подсчитать, что S(9) = 5464, и S(20) = 36035277144875036.

Найдите остаток от деления S(20¹²) на 10⁹.

Как известно, каждый член последовательности Фибоначчи является суммой предыдущих двух. Начав с чисел 1 и 2, получим последовательность 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

Каждое натуральное число может быть единственным образом записано в виде суммы некоторого набора различных чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Например, 100 = 3 + 8 + 89.

Такую сумму называют представлением Цекендорфа.

Обозначим через z(n) число слагаемых в представлении Цекендорфа для натурального числа n. Тогда z(5)=1, z(14)=2, z(100)=3.

∑z(n) для всех шестизначных n равна 7236250.

Найдите ∑z(n) для всех 17-значных n.

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

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

• Лёва забывает то число, которое не выдавалось генератором наиболее продолжительное время
• Петя забывает то число, которое первым попало в память.

В начале соревнования память игроков свободна.

Вот пример начала игры:

Обозначим количество очков, которые Лёва и Петя набрали после 50 туров через L и P, соответственно. Найдите математическое ожидание величины (L-P)², результат умножьте на 10⁸ и округлите до ближайшего целого.

В сильно  упрощенной модели белки можно рассматривать как цепочки гидрофобных (H) и полярных (P) элементов, например HHPPHHHPHHPH.

В этой задаче мы будем считать, что ориентация белка существенна, то есть белки HPP и PPH мы будем считать различными, а количество белков из n элементов будет равно 2ⁿ.

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

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

На рисунке показаны две конфигурации одного белка (связи H-H отмечены красными точками)

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

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

77 из 256 восьмиэлементных цепочек в оптимальной конфигурации имеют более 4 связей H-H.

Сколько цепочек, состоящих из 15 элементов, в оптимальной конфигурации будут иметь более 9 связей H-H?

Назовем натуральное число n мощным, если для его любого простого делителя p число n делится также на p².

Назовем натуральное число n точной степенью, если оно является степенью другого натурального числа.

Назовем натуральное число n ахиллесовым, если оно мощное, но не является точной степенью. Например, числа 864 = 2⁵•3³ и 1800 = 2³•3²•5² — ахиллесовы.

Назовем натуральное число S сильно ахиллесовым, если и S, и φ(S) — ахиллесовы.  Здесь φ(S) означает функцию Эйлера. 

Например, число 864 — сильно ахиллесово число, поскольку φ(864) = 288 = 2⁵•3², а число 1800 — ахиллесово, но не сильно ахиллесово, так как φ(1800) = 480 = 2⁵•3¹•5¹.

Существует 2 трехзначных и 5 четырехзначных сильно ахиллесовых чисел, а восьмизначных насчитывается 396.

Найдите количество 18-значных сильно ахиллесовых чисел.

Для каждого натурального числа 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 будет ответом к этой задаче.

Рассмотрим бесконечную строку S, состоящую из записанных подряд натуральных чисел в десятичной записи:

S =1234567891011121314151617181920212223242...

Ясно, что десятичная запись каждого натурального числа n встретится в строке S бесконечно много раз. Будем отмечать, где именно встретились такие вхождения. Например, число 12 первый раз встретится, начиная с позиции 1 строки S, а второй раз — с позиции 14, и так далее.

Обозначим через f(n) номер позиции в строке S, с которого начинается n-ое вхождение числа n. Например, f(1)=1, f(5)=81, f(11)=235, а f(7780)=111111365.

Найдите ∑f(11^k), где 1≤k≤6.

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

• При n=1 первый игрок автоматически проигрывает, поскольку не может сделать ни одного хода.
• При n=2 есть только один ход, который автоматически ведет к победе.
• При n=3 первый игрок может выбрать один из двух различных ходов, и оба они ведут к немедленной победе.
• При n=4 есть три варианта хода. Среди них есть один выигрышный ход, когда игрок закрашивает две средние клетки.
• При n=5 есть четыре варианта хода (они показаны на рисунке красным цветом), но все они ведут к поражению: второй игрок (показан синим цветом) всегда может выиграть.

Таким образом, первые три значения n, при которых первый игрок выигрывает – это 2,3 и 4, а первые два проигрышных значения – это 1 и 5. Третье проигрышное значение n=9, десятое: n=43.

Найдите миллионное значение n, при котором второй игрок всегда может победить.