4. Признаки делимости

Почему признак делимости на три именно такой, какой мы знаем ? Просто потому, что все числа в ряду 1, 10, 100, 1000, ... при делении на 3 дают в остатке единицу.

Аналогично и для признака делимости на 11. Здесь остатки 1, или -1. Минус единицу можно заменить на 10.

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

Например, при делении на 7 возникает ряд остатков: 1, 3, 2, 6, 4, 5, 1, ... Далее остатки повторяются. Повторение возникает всегда ввиду конечности множества остатков при делении на конкретное число. Число 1999 на 7 не делится, потому что получается сумма 9 1 + 9 3 + 9 2 + 1 6 = 9 + 27 + 18 + 6 = 60, которая на 7 не делится.

Здесь предлагается программа, которая для заданного числа строит алгоритм, который является по существу признаком делимости на заданное число. Функция divide получает в качестве аргументов заданное число и число, которое проверяется на делимость. Последовательно вычисляются остатки от деления и накапливается сумма, аналогичная сумме цифр числа для признака делимости на 3.

В качестве примеров приведены признаки делимости на 3 ( MST-схема div3.mst и результирующая программа r_div3.ref ), на 7 ( div7.mst , r_div3.ref ) и на 12 ( div12.mst , r_div12.ref ).

Множество остальных интересных случаев можно получить самостоятельно.

Отметим, что небольшие программы получаются для признаков делимости на 37, 101, 41, 271, 13, 999. Интересны признаки делимости на степени двойки, степени пятерки, степени десятки. Можно попробовать числа 6, 15, 18, 75.

Общее замечание про суперкомпилятор - реально построены лишь те функции, имена которых начинаются с F, остальные функции строятся лишь для удобства чтения получающейся программы. Это является свойством данной реализации суперкомпилятора. Таким образом, для признаков делимости получается чаще всего одна функция.

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

Одно из действий, которое постоянно пробует совершать суперкомпилятор - это обобщение. Он пытается некоторые похожие ситуации объединять. Функция Const__ запрещает применять обобщение к свому аргументу. В примере с признаками делимости этот механизм приводит к успеху.

Невозможно раз и навсегда задать правила действий суперкомпилятора. Иногда хорошо получается так, иногда по-другому. Причина здесь принципиальная - алгоритмическая неразрешимость задачи, с которой работает суперкомпилятор.

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

Я считаю, что подобного рода применение суперкомпилятора не менее важно, чем оптимизация алгоритмов. Другой пример применения суперкомпилятора для получения математических формул можно посмотреть в параграфе 10.

Наконец заметим, что при получении признака делимости фактически происходит доказательство его методом математической индукции.