Запишем число 57 в системах счисления по основанию 4 и 28:

57₁₀=321₄=21₂₈

В обоих случаях 

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

При выполнении этих условий будем говорить, что число имеет специальный вид в данной системе счисления.

Так, число 57 имеет специальный вид в системах счисления с основаниями 4 и 28.

Существует пять натуральных чисел 1<n<500, имеющих специальный вид хотя бы в двух системах счисления, а именно 57, 121, 209, 321 и 457. Их сумма равна 1165.

Найдите сумму n (1<n<10¹²), имеющих специальный вид хотя бы в двух системах счисления.

В этой задаче мы будем рассматривать натуральные числа, имеющие ровно три простых делителя. Например, число 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²

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

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

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

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

Пусть в начальный момент все клетки доски белые, а муравей находится в точке с координатами x=0 и y=0. Клетки доски ориентированы вдоль координатных осей и имеют единичный размер.
Найдите |x|+|y| после 10¹⁸ шагов.

В этой задаче мы будем рассматривать конечные последовательности натуральных чисел, например, (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=5:

Из центра сада можно увидеть только часть деревьев, поскольку некоторые (они на рисунке обозначены зеленым цветом) заслонены другими, растущими ближе к наблюдателю. Легко подсчитать, что для сада со стороной n=5 количество заслоненных деревьев равно 30.
Обозначим через H(n) количество заслоненных деревьев для шестиугольного сада со стороной n.
Можно проверить, что H(5) = 30, H(10) = 138, а H(1000) = 1177848.
Найдите H(1234567890).

Степени двойки, как известно, редко начинаются с цифры 9 (см. задачу 316). Так, первый раз это случается только для 53-й степени (2⁵³ = 9007199254740992). С двух девяток подряд начинается 93-я степень, а с трех девяток - только 2621-я.

Найдите минимальный показатель степени n такой, что десятичная запись числа 2ⁿ начинается с десяти девяток подряд.

Известно, что некий вирус поражает 2% овец. Ветеринару нужно выявить зараженных животных в стаде из 25 голов. При этом в его распоряжении имеется достаточно дорогой, но очень чувствительный метод анализа, позволяющий обнаруживать инфекцию в крови при крайне низких ее концентрациях.

Чтобы сэкономить дорогостоящие реактивы, ветеринар решил не проверять каждую овцу, а разработал следующую программу действий:
Он разбил стадо на 5 групп по 5 овец в каждой. Пробы крови для каждой группы были объединены и проанализированы. Затем, если в объединенной пробе вирус не обнаружен, все овцы из данной группы считаются здоровыми. В противном случае анализируются пробы крови для каждого из пяти животных группы.
Поскольку вероятность заражения отдельной овцы равна 0,02, первый тест для каждой группы даст
• Отрицательный результат с вероятностью 0,98⁵ = 0,9039207968. Для такой группы дополнительные тесты не понадобятся.
• Положительный результат с вероятностью 1 - 0,9039207968 = 0,0960792032. Для такой группы потребуется проанализировать еще 5 отдельных проб.
Тогда ожидаемое количество анализов для каждой группы составит 1 + 0,0960792032 × 5 = 1,480396016, а для всего стада – 1,480396016 × 5 = 7,40198008 тестов, то есть экономия составит более 70%!
Однако это не предел. Алгоритм можно еще усовершенствовать следующим образом:
• Сначала можно проанализировать объединенную пробу для всех 25 овец. Легко проверить, что примерно в 60,35% случаев результат будет отрицательный, и дальнейшее исследование не потребуется.
• Если групповая проба для 5 овец была положительной, и первые четыре овцы из группы оказались здоровы, то пятую можно не проверять – она наверняка инфицирована.
• Можно попробовать поварьировать размер и количество групп. Это позволит минимизировать ожидаемое количество анализов.
Чтобы не усложнять задачу, мы несколько ограничим круг рассматриваемых алгоритмов. Мы примем следующее дополнительное правило: если проанализирована объединенная проба для группы овец, то овцы, не входящие в данную группу, не исследуются, пока не поставлен окончательный диагноз каждой овце из данной группы.
Оставаясь в рамках данного правила, мы можем найти оптимальную стратегию, позволяющую ограничиться всего 4,155452 тестами в среднем для стада из 25 овец и вероятности заражения 0,02.
Обозначим через T(s,p) ожидаемое количество тестов при использовании оптимальной стратегии, когда стадо состоит из s овец, а вероятность заражения отдельной овцы равна p.
Тогда T(25, 0,02) ≈ 4,155452 и T(25, 0,10) ≈ 12,702124.
Найдите p, для которого T(10000, p)=5000. Результат умножьте на миллион и округлите вниз до целого.

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

Одну из ячеек занимает пчелиная матка.
Обозначим через B(L) количество ячеек, удаленных от матки на расстояние L (в этой задаче мы будем измерять расстояния между центрами ячеек).
Считая соты достаточно большими, получим  B(√3) = 6, B(√21) = 12 и B(111 111 111) = 54.

Найдите количество таких L ≤ 3•10¹¹, для которых B(L) = 378.

Ответ:

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