Напомним, что функцией Эйлера φ(n) для натуральных n называют количество натуральных чисел, не превышающих n и взаимно простых с n.
Взяв некоторое число n,  будем строить цепочку n, φ(n), φ(φ(n)), φ(φ(φ(n)))…, пока не получим 1. Например, начав с 5, получим последовательность 5,4,2,1, содержащую 4 члена. Ниже приведены все последовательности, содержащие 4 члена.

5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1

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

k-значное натуральное число называется сбалансированным, если сумма его первых  [k/2]  цифр его равна сумме последних  [k/2] цифр. Здесь  x  обозначает округление вверх, например, [π] = 4 и [5] = 5.
Понятно, что все палиндромы являются сбалансированными, как и число 13722.
Обозначим через T(n) сумму всех сбалансированных чисел, меньших, чем 10ⁿ.
Например, T(1) = 45, T(2) = 540 and T(5) = 334795890.
Найдите остаток от деления T(2000) на 3¹⁵.

Пусть A и B - битовые последовательности,  составленные из нулей и единиц.
Если A состоит из k битов и совпадает с отрезком  длиной k, с которого начинается B (k левых битов), то A называют префиксом B.
Например, 00110 является префиксом последовательности 001101001, но не  является префиксом последовательностей 00111 и 100110.
Префиксным кодом длины n будем называть набор из n битовых последовательностей, ни одна из которых них не является префиксом другой.
Вот, например, префиксный код длины 6:
00, 010,011,100,101,1111

Теперь предположим, что затраты на передачу нуля составляют 1 копейку, а затраты на передачу единицы - 4 копейки. Тогда стоимость вышеприведенного кода составит 2+6+9+6+9+16=48 копеек. Это далеко не самый дешевый код. Самый дешевый код длины 6 стоит 35 копеек и может быть реализован двумя способами:
1,01,00000,001,0001,00001
0000,01,10,001,0001,11

А сколькими способами может быть реализован самый дешевый код длиной 946583626

Будем называть натуральное число A александрийским, если есть такие целые p, q, r, что
A = p·q·r и 1/A=1/p+1/q+1/r.
Примером александрийского числа является 630 (p = 5, q = -7, r = -18). Вот семь первых александрийских чисел:
6, 42, 120, 156, 420, 630, 930.
930 – наибольшее александрийское число, не превышающее 1000.
Найдите наибольшее александрийское число, не превышающее 1,5?10¹⁵.

Возьмем вещественное число x.
Наилучшим его приближением со знаменателем, не превышающим d, назовем квадратный корень из несократимой дроби r/s (s≤d), такой, что у любого рационального числа, лежащего ближе к x, чем r/s, знаменатель будет больше, чем d:
|p²/q²-x| < |r²/s²-x| => q>d.
Найдите сумму знаменателей наилучших приближений ³√n со знаменателем, не большим, чем 10¹⁰, для всех простых чисел n, не превышающих 100000.

Функция бланманже определена на промежутке [0, 1] следующим образом:
,
Где s(x) – расстояние между x и ближайшим к нему целым числом.
График функции бланманже представлен на рисунке. Область под кривой, закрашена розовым. Ее площадь равна ½.

Построим теперь круг C с центром в точке (3/8, 1/2) и радиусом 3/8.
Найдите площадь той части круга C, которая лежит под графиком  функции бланманже.
Результат умножьте на 10⁷ и округлите до целого.

Рассмотрим число
G(n) = (n²)!/(n!)ⁿ,
где n – натуральное. Несложно показать, что G(n) – тоже натуральное число.
Например, G(3)=1680. Разложим 1680 на простые множители, а затем их сложим:

1680=2⁴×3×5×7=2×2×2×2×3×5×7,
и
2 + 2 + 2 + 2 + 3 + 5 +7 = 23.
Таким образом, сумма простых множителей числа G(3) равна 23.

Найдите сумму простых множителей числа G(4444).

Для целого n≥4 определим нижний простой квадратный корень из n как наибольшее простое число, не превышающее √n. Обозначим это число через lps(n).
Аналогично, обозначим через ups(n) верхний простой квадратный корень из n, т.е. наименьшее простое число, большее или раное √n.
Например, lps(4) = 2 = ups(4), lps(1000) = 31, ups(1000) = 37.
Назовем число n≥4 полуделимым, если оно делится на lps(n) или на  ups(n), но не кратно обоим этим числам одновременно. Первые три полуделимых числа – это 8, 10 и 12. Число 15 не является полуделимым, поскольку  оно кратно и lps(15)=3, и ups(15)=5. Сумма первых трех полуделимых чисел равна 30. Сумма первых 92 полуделимых чисел равна 34825.
Найдите сумму первых 3711717 полуделимых чисел.

Решите уравнение относительно r:

Результат округлите до целого.

Построим последовательность случайных чисел s_n при помощи генератора Блюм-Блюма-Шуба:
s₀=14025256
s_n+1=s_n² mod 20300713,
и запишем полученные числа s₀ s₁ s₂… подряд в одну бесконечную строку w: w=14025256741014958470038053646…

Для натурального числа k выберем все подстроки строки w, для которых сумма цифр равна k и обозначим через p(k) положение самой левой цифры в этих подстроках. Если не найдется ни одной подстроки с суммой цифр, равной k, будем считать, что p(k)=0.

Например,
Сумму цифр k=7 имеют подстроки 1402, 025, 25, 52, 25, 7 …, начинающиеся, соответственно, с 1, 3, 4, 5, 6, 9 … позиции. Поэтому p(7)=1.
Сумму цифр k=11 имеют подстроки 4025, 56, 74, 47, 470, 4700, 0038 …, начинающиеся, соответственно, со 2, 7, 9, 18, 18, 18, 20 … позиции. Поэтому p(11)=2.
Сумму цифр k=20 имеют подстроки 025256, 25256, 2567, 101495 …, начинающиеся, соответственно, со 3, 4, 6, 11 … позиции. Поэтому p(20)=3.

Можно показать, что среди значений p(k) для 0<k≤10³ найдется 614 нечетных и 386 четных.
А сколько нечетных значений p(k) найдется для  0<k≤2•10¹⁵?