В этой задаче мы будем рассматривать натуральные числа, имеющие ровно три простых делителя. Например, число 240 имеет простые делители 2,3 и 5. Это наибольшее число, не превышающее 250, имеющее эти три простых делителя и не имеющее других.

Для различных простых чисел p, q и r обозначим через M(p,q,r,N) наибольшее натуральное число, не превышающее N, которое делится на p, q и r, но не имеет других простых делителей. Если таких чисел нет, будем считать, что M(p,q,r,N)=0.

Например:

• M(2,3,5,250)=240.
• M(2,3,7,250)=168, а не 210, поскольку число 210 имеет 4 простых делителя.
• M(3,7,13,250)=0, поскольку нет натуральных чисел, не превышающих 250, которые делятся на 3, 7 и 13.

Пусть S(N) – сумма различных значений M(p,q,r,N) для всех сочетаний p, q и r. Так, S(250)= 4588.

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

Многие числа могут быть представлены в виде суммы куба и квадрата, а некоторые из них даже несколькими способами.
Рассмотрим число 37873.
Во-первых, оно может быть записано в виде суммы куба и квадрата тремя способами:

37873 = 18³+179² = 22³+165² = 33³+44²

Во-вторых, оно является палиндромом, то есть его десятичная запись читается слева направо и справа налево одинаково.

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

В этой задаче мы будем рассматривать конечные последовательности натуральных чисел, например, (2,4,6), (2,6,4), (10,6,15,6) и (11).
Наибольшим общим делителем последовательности (gcd) будем называть наибольшее натуральное число, являющееся делителем каждого члена последовательности. Например, gcd(2,6,4) = 2, gcd(10,6,15,6) = 1 и gcd(11) = 11.
Наименьшим общим кратным последовательности (lcm) будем называть наименьшее натуральное число, кратное каждому члену последовательности, например, lcm(2,6,4) = 12, lcm(10,6,15,6) = 30 и lcm(11) = 11.
Обозначим через f(G, L, N) количество последовательностей длины N у которых gcd ≥ G и lcm ≤ L. Например:
f(10, 100, 1) = 91.
f(10, 100, 2) = 327.
f(10, 100, 3) = 1135.
f(10, 100, 1000) mod 101⁴ = 3286053.
Здесь a mod b означает остаток от деления a на b.
Найдите f(10⁶, 10¹², 10¹⁰⁰) mod 101⁴.

Рассмотрим множества, состоящие из взаимно простых натуральных чисел, не превышающих n.
Обозначим через Co(n) максимально возможную сумму элементов такого множества.
Например, Co(10)=30, и это значение достигается для множества {1, 5, 7, 8, 9}.
Можно проверить, что Co(30) = 193 и Co(100) = 1356.
Найдите Co(1000000).

Пусть a(n) – наибольший корень многочлена P(x) = x³ - 3ⁿx² + n, например a(2)=8,97517184...
Пусть t(n,p)=[a(n)^p], где скобки […] означают округление вниз до целого.

Найдите восемь младших десятичных знаков суммы ∑t(i,333333333) для i=1,2,3,...30.

Возьмем натуральное число n и рассмотрим последовательность s(n)={1+n/1, 2+n/2, 3+n/3, …k+n/k,…}. Если эта последовательность не содержит целых составных чисел, будем говорить, что число n не порождает составных.
Легко проверить, что последовательность s(30)={31, 17, 13, 11.5, 11, 11, …} содержит только простые и нецелые числа. Поэтому число 30 не порождает составных.
Найдите количество восьмизначных чисел, которые не порождают составных.

Циклическим называют натуральное число из n знаков, обладающее следующим интересным свойством: если умножить его на 1, 2, 3, 4,…, n-1 или n, то произведение будет состоять из тех же цифр, но переставленных циклически.

Если не считать тривиального числа 1, наименьшим циклическим числом будет 142857:
142857 × 1 = 142857
142857 × 2 = 285714
142857 × 3 = 428571
142857 × 4 = 571428
142857 × 5 = 714285
142857 × 6 = 857142

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

0588235294117647 × 1 = 0588235294117647
0588235294117647 × 2 = 1176470588235294
0588235294117647 × 3 = 1764705882352941
...
0588235294117647 × 16 = 9411764705882352

Найдите наибольшее циклическое число, которое начинается цифрами 00000000123 и заканчивается цифрами 56789 (то есть число вида 00000000123...56789, где многоточие означает некоторое неизвестное количество цифр). В качестве ответа укажите сумму его цифр.