Використовуючи визначення, наведені вище, можна переписати перевірку подільності на 37 наступним чином:
while n>=1000 do
n:=n div 1000 + n mod 1000;
n:=n-111*min(min(rdigit(n,1), rdigit(n,2)), rdigit(n,3));
if n in [0, 37, 74, 370, 740, 703, 407]
then write ('ділиться на 37')
else write ('не ділиться на 37')
Іншими словами, на другому етапі (коли число вже зменшено до значення в межах тисячі) треба вибрати найменшу з трьох цифр, помножити її на 111 і відняти від числа (або відняти цю найменшу цифру від кожної з трьох цифр, що те ж саме). У результаті, отримуємо число, серед трьох цифр якого є щонайменше один 0. Ця дія дозволяє скоротити кількість значень, з якими треба звірити результат: є лише сім чисел, менших за тисячу, що містять нуль (у т.ч., початковий нуль) і при цьому діляться на 37.
Подібний прийом доступний далеко не для всіх дільників: має існувати число з самих одиниць (або з одиниць і нулів), що ділиться на цей дільник. Наприклад, 41*271=11111, що можна використати для допоміжного зменшення при перевірці подільності на 41. Тобто, якщо в нас є п'ятицифрове число, можемо так само взяти найменшу його цифру й відняти від усіх цифр. Проте, користі від цього не так багато: так можна зменшити лише п'ятицифрове число (тобто, початково достатньо велике), і реальна користь буде, лише якщо найменшою є перша або остання цифра (котру, після перетворення її на нуль, можна відкинути й далі працювати з чотирицифровим числом, яке потім усе одно треба буде зменшувати, використовуючи інші прийоми). Чисел, що діляться на 41 і містять нуль, усе одно лишається забагато — такого ефекту, як у випадку 37, ми не досягнемо. З іншого боку, якщо отримане число — п'ятицифрове з нулями посередині, до його цифр можна додати 41 зі зміщенням (так, щоб четвірка стала навпроти нуля) й повторити спробу — доти, доки нуль нарешті не опиниться скраю.
Якщо число містить більше цифр, ніж нам потрібно (тобто, в випадку 41, складається з більш ніж п'яти цифр), цей же прийом можна застосувати до частини цифр (у випадку 41 — до п'яти найправіших чи п'яти найлівіших): обираємо серед них найменшу й віднімаємо від цих крайніх цифр. Якщо в результаті з'явився нуль скраю всього числа, цей нуль відкидаємо (і далі працюємо з числом, що містить на одну цифру менше), інакше додаємо зміщений дільник, подільність на який перевіряємо (тобто, 41). Таким способом можна скорочувати як-завгодно велике число, але, в випадку 41, це не дуже вигідно: простіше скористатися тим, що 99999 ділиться на 41 — а отже, можна розбити число на частини по п'ять розрядів, додати ці частини й перевірити подільність отриманої суми на 41 — це простіше, ніж прийом з відніманням найменшої цифри.
Р.Ѕ.
▼Алгоритм перевірки подільності на 41 у вигляді коду
uses digits;
var i,md,n,n0:integer;
begin
write('n='); readln(n); n0:=n;
while n>100000 do
n:=(n div 100000) + (n mod 100000);
while ndigits(n)=5 do begin
while rdigit(n,1)=0 do n:=n div 10;
if ndigits(n)<5 then break;
for i:=2 to 4 do
if ldigit(n,i)=0 then
n:=ldigit_add(n,i+1, 41);
md:=10;
for i:=1 to 5 do md:=min(rdigit(n,i), md);
n:=n-11111*md;
end;
while n>2000 do n:=abs((n div 2000)*9 - (n mod 2000));
while n>200 do n:=abs((n div 200)*5 - (n mod 200));
if n in [0,41,82, 123, 164]
then writeln (n0, ' mod 41 = 0')
else writeln (n0, ' mod 41 != 0')
end.