Назовем натуральное число 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-значных сильно ахиллесовых чисел.

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

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.

Две лестницы длиной x и y опираются на противоположные стены коридора шириной w, как показано на рисунке. Пусть h – высота, на которой лестницы пересекаются. Нас интересуют случаи, когда все четыре числа – x,y,w и h – оказываются целыми.

Например, для x = 70 и y = 119 можно найти пару подходящих целых чисел h = 30 и w = 56. При 0<x<y<200 есть ровно пять пар (x,y), для которых существуют целые h и w, а именно: (70, 119), (74, 182), (87, 105), (100, 116) и (119, 175).

А сколько существует пар (x,y) при 0<x<y<1 000 000, для которых можно подобрать целые значения w и h?

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

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

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

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

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

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

Пусть ABCD – выпуклый четырехугольник с  целыми сторонами, и 1 ≤ AB < BC < CD < AD. Точка O – середина диагонали BD. Будем называть четырехугольник ABCD биклинным, если длины отрезков BO, DO, AO и CO – целые числа, и AO = CO < BO = DO.

Например, когда AB = 19, BC = 29, CD = 37, AD = 43, BD = 48 и AO = CO = 23, четырехугольник ABCD является биклинным.

Обозначим через B(N) количество различных биклинных четырехугольников ABCD с целыми сторонами, у которых |AB|²+|BC|²+|CD|²+|AD|² ≤ N..

Можно проверить, что B(10 000) = 48 и B(1 000 000) = 38108. 

Найдите B(10 000 000 000).

Когда стали раздавать бесплатные участки на Луне, были установлены следующие правила. Каждому государству выделяется квадратная площадка размером 500 х 500 м. Площадка расчерчена на клетки размером 1 х 1 м, в углах которых установлено 251001 столбов. Забор должен состоять из прямолинейных отрезков, соединяющих столбы. 

Однако нужно учитывать, что строительство заборов в лунных условиях недешево.

Конечно, богатые государства построили себе ограды длиной 2000 м, которые ограничивали площадь 250 000 м2. Но финансы княжества Фенвик расстроены, и правительство поручило вам, Главному Программисту, найти оптимальную форму забора, обеспечивающую максимальное отношение площади огороженного участка к длине забора.

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

Для квадратного забора длиной 2000 м площадь участка получается равной 250 000 м², а отношение площади к длине ограды  равно 125.

Если бы разрешалось строить криволинейные заборы, то для круглого участка диаметром 500 м площадь будет равна π*250² м², длина ограды - π*500 м, и отношение будет равно тому же числу 125.

Если же отрезать от четырех углов площадки четыре равнобедренных прямоугольных треугольника с катетами 75 м, как показано на рисунке зеленым цветом, можно достичь существенного выигрыша. Действительно, площадь участка станет равной 238750 м², длина забора будет равна 1400+300√2 м, а интересующее нас отношение составит примерно 130,87. При этом будет использовано 1700 столбов.

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

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

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

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

Последовательность Голомба {G(n)}  определяют как единственную неубывающую последовательность натуральных чисел, содержащую ровно G(n)  вхождений каждого натурального числа n.
Вот несколько первых значений G(n):

Можно подсчитать, что G(2¹⁰) = 87, G(2²⁰) = 6320, и что ΣG(2ⁿ) = 857297 при 1 ≤ n < 30.

Найдите ΣG(2ⁿ)для 1 ≤ n < 60.

Возьмем натуральное число 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⁶.