Числа харшад

МАТЕМАТИЧЕСКИЙ КРУЖОК

Числа харшад

А.ТОЛПЫГО

КРУГ ЗАДАЧ, КОТОРЫЕ РАССМАтриваются в этой статье, можно описать одной фразой: Как часто бывает, что число делится на сумму своих цифр? Оказывается, что этот простой вопрос приводит к целому циклу довольно разнообразных задач. Числа, обладающие этим свойством, называют числами Нивена, или числами харшад (от санскритского «харша» – великая радость); такое название дал им индийский математик Д.Ч.Капрекар; для краткости будем их называть Х-числами. Поскольку однозначные числа заведомо являются таковыми, сразу условимся, что мы рассматриваем только те Х-числа, в которых не менее двух (или даже лучше, не менее трех) знаков. Начнем с того очевидного факта, что все числа с суммой цифр 3 или 9 – харшад. Легко также привести примеры Х-чисел с другими небольшими суммами цифр; например, таковы все четные числа с суммой цифр 2 или 6. Нетрудно придумать и другие примеры: это числа 224, 605 или 999999999. А как быть, если сумма цифр велика? Всегда ли можно построить такое число харшад? Ответ – положительный. Утверждение 1. Для любого натурального m существует Х-число с суммой цифр m. Доказательство. Рассмотрим числа 1, 10, 100, …, $10^{k}$, … Согласно принципу Дирихле, существует такой остаток r, что сколь угодно большое количество из этих чисел дают при делении на m остаток r. Теперь достаточно взять сумму m соответствующих чисел $10^{k}$ для разных таких k (можно и для совпадающих, но в количестве не более 9). Пример 1. Пусть m 37. Поскольку 999 делится на 37, то все числа $1, 10^{4}, 10^{7}$, … $..., 10^{3k1}$ дают одинаковые остатки при делении на 37. Таким образом, мы можем взять

DOI: https://doi.org/10.4213/kvant20201004

число 100100100…1 (и так 37 раз); но проще взять, например, число 9009009009001. Замечание. Ниже будет доказано существенно более сильное утверждение, а именно: каково бы ни было m, доля Х-чисел среди всех чисел с суммой цифр m больше нуля (стремится к пределу, который больше нуля; более точная формулировка будет дана ниже).

Длинные ряды

Назовем рядом длины k последовательность чисел n, n 1, n 2, …, $n k_{–} 1,$ которые все харшад. Поскольку ряд всегда полностью определяется своим первым членом, в дальнейшем мы, как правило, будем выписывать только его. Нетрудно привести пример ряда длины 3: он может, например, начинаться с числа 110, поскольку 111 и 112 – тоже Х-числа. (Годятся также числа 1010, 10010 и т.д.) А можно ли построить ряд подлиннее? Утверждение 2. Существует ряд длины 10. Для доказательства, конечно, достаточно привести пример (что мы сейчас и сделаем), но интересно ведь знать, как его построить. Можно, разумеется, поручить дело компьютеру (и этот способ приводит к цели), но тогда – где же тут математика? Было бы очень легко построить пример, если бы нам разрешалось рассматривать однозначные числа (все числа от 1 до 10 делятся на сумму своих цифр), но это запрещено. Тем не менее это подсказывает идею: пусть первое число оканчивается нулем, и пусть сумма его цифр равна r. Тогда следующие числа будут кончаться на 1, 2, …, 9, а их суммы цифр будут r 1, …, r 9. Нетрудно было бы найти число (притом даже с заданной суммой цифр, если только она достаточно велика), которое делится на все эти числа, но нам нужно, чтобы делилось не одно число, а последовательные. Но это тоже можно сделать, если применить вот какую хитрость. Начнем с некоторого «удобного» числа (в чем именно состоит его «удобство», будет видно дальше), которое мы примем за r, т.е. за сумму цифр первого из чисел нашего ряда. Это число мы назовем опорным числом. Для начала возьмем в качестве опорного число 30. Предположим, что первое наше число заканчивается цифрами …30 или,