Трехзначное число 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.

Вагоны поезда обозначены буквами латинского алфавита: A,B,C,D..., и последовательность вагонов в железнодорожном составе можно задать с помощью соответствующей цепочки букв.

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

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

В некоторых случаях сформировать состав совсем просто. Например, когда исходный порядок вагонов ADCB, вагоны можно расцепить между A и D, затем развернуть фрагмент DCB, и, наконец, сцепить вагоны в нужном порядке. Результат достигается всего за один шаг, т.е. за один поворот круга на 180 градусов.

Возможно, процесс можно оптимизировать, но машинист пользуется совсем простым алгоритмом. Сначала он стремиться прицепить вагон A следом за паровозом, затем следом за ним вагон B, и так далее.

Машинист выяснил, что для состава из четырех вагонов потребуется не более 5 шагов. Максимальное количество - 5 операций - требуется для двух начальных последовательностей, а именно DACB и DBAC. Последовательности вагонов, требующие наибольшего количества операций для упорядочения, будем называть пессимальными.

Порядок формирования состава для начальной последовательности  DACB показан на рисунке.

Для состава из шести вагонов машинист составил список пессимальных последовательностей. Список содержал 24 последовательности. Последовательности он расположил в алфавитном порядке, и цепочка DFAECB оказалась на десятом месте от начала.

Представьте, что вам поручили составить список пессимальных последовательностей для составов из 11 вагонов и упорядочить получившийся список в алфавитном порядке.

На каком месте в списке окажется последовательность CIAKBGHFJDE?

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

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

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

Возьмем матрицу n×n, выберем из нее n элементов так, чтобы никакие два из них не стояли в одной строке или столбце, и найдем их сумму. Минимальное значение такой суммы будем называть матричной суммой для данной матрицы.
Например, для матрицы:

  7  53 183 439 863
497 383 563  79 973
287  63 343 169 583
627 343 773 959 943
767 473 103 699 303

матричной суммой будет число 1075=7+79+343+343+303.

Найдите матричную сумму для матрицы:

  7  53 183 439 863 497 383 563  79 973 287  63 343 169 583
627 343 773 959 943 767 473 103 699 303 957 703 583 639 913
447 283 463  29  23 487 463 993 119 883 327 493 423 159 743
217 623   3 399 853 407 103 983  89 463 290 516 212 462 350
960 376 682 962 300 780 486 502 912 800 250 346 172 812 350
870 456 192 162 593 473 915  45 989 873 823 965 425 329 803
973 965 905 919 133 673 665 235 509 613 673 815 165 992 326
322 148 972 962 286 255 941 541 265 323 925 281 601  95 973
445 721  11 525 473  65 511 164 138 672  18 428 154 448 848
414 456 310 312 798 104 566 520 302 248 694 976 430 392 198
184 829 373 181 631 101 969 613 840 740 778 458 284 760 390
821 461 843 513  17 901 711 993 293 157 274  94 192 156 574
 34 124   4 878 450 476 712 914 838 669 875 299 823 329 699
815 559 813 459 522 788 168 586 966 232 308 833 251 631 107
813 883 451 509 615  77 281 613 459 205 380 274 302  35 805