Попробуем построить признак делимости для делителя p > 1, взаимно простого с 10. Мы хотим найти для каждого натурального n другое число n₁, которое делится на p тогда и только тогда, когда n делится на p. Два целых числа называются равноделимыми на p, если либо они оба делятся на p, либо оба не делятся. Если b – последняя цифра числа n, и n=10a+b, мы будем искать n₁ в виде:
n₁ = a + b ? m.
Остается найти подходящее значение  m < p, которое будем  называть фактором делимости. Тогда для достаточно больших n мы сможем построить убывающую последовательность равноделимых чисел.
Например, для p=113 фактор делимости равен 34.
При n=76275 получим n₁ = 7627 + 5 * 34 = 7797, и оба числа 76275 и 7797 делятся на 113.
При n=12345 получим n₁ = 1234 + 5 * 34 = 1404, и оба числа 12345 и 1404 не делятся на 113.
Сумма факторов делимости для всех простых p вида 4k+3, не превышающих 1000, равна 19961.
Найдите сумму факторов делимости для всех простых p вида 4k+3, не превышающих 2*10⁷.

Определим модифицированную последовательность Коллатца как последовательность натуральных чисел, начинающуюся с числа a₁, а далее задаваемую рекуррентно по следующим правилам:

• a_n+1 = a_n/3, когда a_n делится на 3. Обозначим такой переход от  a_n к a_n+1 символом "D".
• a_n+1 = (4a_n + 2)/3, если a_n дает остаток 1 при делении на 3. Обозначим этот случай символом "U".
• a_n+1 = (2a_n - 1)/3 , если a_n дает остаток 2 при делении на 3.

Обозначим этот случай символом "d".
Последовательность заканчивается первой встретившейся единицей.
Например, при a₁ =231 получим последовательность чисел {231,77,51,17,11,7,10,14,9,3,1} и соответствующую строку символов - "DdDddUUdDD".
Для a₁ =1004064 получим строку символов DdDddUUdDDDdUDUUUdDdUUDDDUdDD, которая начинается с DdDddUUdDD.

Найдите все a₁<10¹⁵, у которых цепочка символов, соответствующая модифицированной последовательности Коллатца, начинается с dDUddDDUUUUUdDDUdUdDUdDUddUDUd.
В качестве ответа укажите их сумму.

Трехзначное число 376 в десятичной системе счисления обладает одним интересным свойством: его квадрат заканчивается теми же цифрами 3, 7 и 6, 376² = 141376.Будем называть натуральные числа, обладающие этим свойством, устойчивыми.

Устойчивые числа есть и в других системах счисления. Например, в системе счисления по основанию 14 устойчивым является число c37. Действительно, c37² = aa0c37. Наибольшее 10-значное устойчивое число в 14-ичной системе счисления равно 7337aa0c37. В десятичной записи это число равно 149429406721.

(В 14-ичной системе счисления буквами a, b, c и d мы обозначили цифры 10, 11, 12 и 13, подобно тому, как это делается в 16-ичной системе счисления.)

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

Сколько существует 18-значных натуральных чисел n, таких, что сумма цифр n равна сумме цифр числа 137n?

Назовем пифагоровым многоугольником выпуклый многоугольник, обладающий следующими свойствами:

• Он имеет не менее  трех вершин
• Никакие три его вершины не лежат на одной прямой
• Все вершины имеют целые координаты
• Все стороны многоугольника имеют целочисленную длину

Обозначим через Q(n) количество различных пифагоровых многоугольников, периметр которых равен n. При этом различными будем считать многоугольники, которые нельзя преобразовать друг в друга путем параллельного переноса.

Тогда Q(4)=1, Q(30) =1242, Q(60) =248282.

Найдите Q(120).

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

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

Рассмотрим бесконечную строку 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.

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

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

Например, если взять число 137, индикатор покажет последовательность "137"→"11"→"2", а затем погаснет до прихода нового числа.

Каждая цифра на индикаторе состоит из нескольких отрезков, как показано на рисунке.

Например, цифра "8" использует семь отрезков – четыре вертикальных и три горизонтальных, цифра "1" состоит из двух вертикальных, а именно, правого верхнего и правого нижнего, а цифра "4" – из четырех отрезков: левого верхнего, правого верхнего и правого нижнего вертикальных и горизонтального, лежащего посередине.

Индикатор потребляет электроэнергию, только когда отрезки включаются или выключаются. Так, включение или выключение числа 2 требует пяти единиц энергии, а числа 7 – четырех единиц энергии.

Сэм и Макс предложили разные конструкции прибора.

Работа прибора Сэма показана на картинке слева. Когда  этот прибор получает число 137, оно отображается на индикаторе, затем полностью гаснет, затем прибор показывает число 11, которое также гаснет, и, наконец, загорается число 2, которое тоже гаснет

В таблице приведен расчет энергопотребления прибора Сэма для числа 137.

"137":(2 + 5 + 4) ?× 2 = 22 переключений ("137" включается и выключается).

"11":(2 + 2) × 2 = 8 переключений ("11" включается и выключается).

"2":(5) × 2 = 10 переключений ("2" включается и выключается).

Всего получается 40 переключений и, соответственно, тратится 40 единиц энергии.

Прибор Макса (изображен справа) работает по-другому. Он не выключает каждый раз весь индикатор, а выбирает только те отрезки, которые не понадобятся для следующего числа.

Вот, как он будет работать с числом 137:

"137":2 + 5 + 4 = 11 переключений (включение трех цифр числа "137"), 7 переключений (выключение отрезков, не нужных для числа "11"). 0 переключений (число "11" уже и так горит)

"11":3 переключения (выключение первой единички и нижней части второй единички; верхняя часть остается гореть, поскольку она нужна для цифры "2").

"2":4 переключения (включение оставшихся отрезков цифры "2"), 5 переключений (выключение цифры "2").

Итого: 30 переключений.

Понятно, что прибор Макса тратит меньше энергии. Так, при подсчете однозначной суммы цифр для числа 137 экономия составляет 10 единиц энергии.

Найдите общую экономию энергии при подсчете однозначной суммы цифр для всех простых чисел, не превышающих  2×10⁷.