Вообще-то я хотел опубликовать это обычным постом, но раз уж сел за компьютер, напишу статью

Всем привет, меня зовут Мынка, я снова страдаю хуйнёй. Вы же знаете достаточно дохуя признаков делимости на разные числа?

Там типа
"число делится на 11 тогда и только тогда, когда сумма его чётных цифр отличается от суммы нечётных на число, кратное 11"
или
"число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9".

Вчера я посидел, полежал и придумал признаки делимости ДЛЯ ВСЕХ НАХУЙ ЧИСЕЛ. (ну или для 99,9% из них, хотя, вроде всё-таки для всех)

Как это работает? Признаки делимости для 2, 4, 8, 16 известны.
Число делится на 2ⁿ тогда и только тогда, когда число, образованное последними n цифрами исходного делится на 2ⁿ. Это работает потому, что 10ⁿ точно делится на 2ⁿ, а 10ⁿ это 1 и n нулей. То есть дальше числа будут повторяться по кругу:
2 4 6 8 0 для 2¹
04 08 12 16 20... для 2²
008, 016, 024...104, 112... для 2³ и так далее.

Я это к тому, что для всех чётных чисел можно будет собрать признак, если знать признаки всех нечётных.

Аналогично для 5ⁿ. Поэтому для всех чисел, кратных 5, мы тоже найдём производный признак.

Остаются числа, которые оканчиваются на 1, 3, 7 и 9.

И с ними я вчера разбирался.

Давайте сразу обозначим всё, с чем мы будем работать.

Есть два основных числа. Первое — делимость которого мы проверяем, а второе — делимость на которое мы проверяем. Обозначим их за X и Y соответственно.

Знаете же такие понятия, как целочисленное деление и остаток от деления? Они обычно обозначаются как div и mod. Ну, например,
27 : 4 = 6 (3 ост.), поэтому
27 div 4 = 6
27 mod 4 = 3

Думаю, вы это знаете, но всё же.

Нам этот приём нужен чтобы выделить из чисел X u Y две части: отдельно разряд единиц и отдельно всё, кроме разряда единиц.

Введём такие обозначения:

Dx = X div 10 — число десятков в числе Х
Dy = Y div 10 — число десятков в числе Y
Mx = X mod 10 — число единиц в числе X
My = Y mod 10 — число единиц в числе Y

Так вот. Мы с вами рассматриваем те Y, для которых My = 1, 3, 7, 9.

В какой-то момент до меня дошло, что если Y представим в виде
Y = Dy + k*My, где k — какой-то целый коэффициент, то
число X делится на Y тогда и только тогда, когда
Dx + k*Mx делится на Y.

В общем-то, тут вопрос только в том, что…эээ, у меня проблемы с формулировкой предложения. Короче, вопрос в существовании k. Если k существует, то такой признак есть. Если не существует, надо думать дальше.

И вот какое дело.

Предположим, число Y оканчивается цифрой 1. Поскольку Dy — десятки и все большие разряды, а My — единицы, то
Y = 10*Dy + My

С другой стороны, нам нужно, чтобы
Y = Dy + k*My

Раз последняя цифра — 1, то и My = 1.
Y = 10*Dy + 1 = Dy + k*1
k = 9Dy + 1

Ну, очевидно, это целое число. Значит, для единиц k существует. Тогда:

Число X делится на число Y, оканчивающееся цифрой 1, тогда и только тогда, когда Dx + (9Dy + 1)Mx делится на Y.

Круто. Давайте посмотрим на примере 11.
D11 = 1
M11 = 1

По нашей формуле, k = 9*1 + 1 = 10

Число 7 168 459 805 606 делится на 11. Это прям факт, потому что я только что взял калькулятор, умножил 11 на какую-то хуйню, и получил это.

Двигаемся по нашему принципу.

7 168 459 805 606.
716 845 980 560 + 60 = 716 845 980 620

716 845 980 620.
71 684 598 062 + 0 = 71 684 598 062

71 684 598 062.
7 168 459 806 + 20 = 7 168 459 826

7 168 459 826.
716 845 982 + 60 = 716 846 042

716 846 042.
71 684 604 + 20 = 71 684 624

71 684 624.
7 168 462 + 40 = 7 168 502

7 168 502.
716 850 + 20 = 716 870

716 870.
71 687 + 0 = 71 687

71 687.
7 168 + 70 = 7 238

7 238.
723 + 80 = 803

803.
80 + 30 = 110

110.
11 + 0 = 11

Вуаля. 11 делится на 11, значит, и все числа выше делятся на 11.

Для 11, конечно, есть более простой признак, хотя он вытекает из этого. Но вот, например, для 31, признак, выведенный нами — самый простой, если не единственный. И, главное, он работает для всех чисел, оканчивающихся цифрой 1. Возможно, конечно, проще просто разделить столбиком, но хуй знает, вдруг пригодится.

Теперь рассмотрим числа, которые заканчиваются на 3.

То есть, My = 3.

Мы уже с вами вывели формулу:

10*Dy + My = Dy + k*My
10*Dy + 3 = Dy + 3k
3k = 9*Dy + 3
k = 3*Dy + 1

Снова красота. Ещё проще, чем для 1. Думаю, вы уже заметили, что 9 тоже идеально подходит, а вот 7 отпадает.

Ну и формулируем свойство:

Число X делится на число Y, оканчивающееся цифрой 3, тогда и только тогда, когда Dx + (3Dy + 1)Mx делится на Y.

На примере 13 это очень красиво видно. В общем-то, мы это с вами разбирали в сентябре, в этой статье.

Можете также сами пораскидывать эти числа, приятное дело.

Аналогично, My = 9.

10*Dy + My = Dy + k*My
10*Dy + 9 = Dy + 9k
9k = 9Dy + 9
k = Dy + 1

Сверхзаебато.

Число X делится на число Y, оканчивающееся цифрой 9, тогда и только тогда, когда Dx + (Dy + 1)Mx делится на Y.

Самое приятное — это работает и в других системах счисления, это работает ещё, например, если вместо
div 10
mod 10
взять
div 100
mod 100

Короче, прикольно.

Но что делать с числами, оканчивающимися на 7?

7k = 9Dy + 7

k не может быть целым. Поэтому расширим границы свойства.

Чтобы X делилось на Y необходимо и достаточно, чтобы Dy + k*My было кратно Y, и Dx + k*Mx было кратно Y.

Тогда мы будем уже рассматривать не
Y = Dy + k*My, а
n*Y = Dy + k*My, где n — некоторый вспомогательный целый множитель.

По сути, то, что мы рассматривали выше — частный случай при n = 1.

Вернёмся к уравнению.

Напоминаю, что мы имеем:

Y = 10*Dy + My
My = 7
n*Y = Dy

n(10Dy + 7) = Dy + 7k
7k = 10n*Dy + 7n - Dy
7k = (10n - 1)Dy + 7n
k = (10n - 1)Dy/7 + n

Как вы видите, нам подойдёт любое n, при котором 10n - 1 делится на 7. Ну, кстати, исключение — случаи, когда Dy делится на 7. В таких случаях нам пойдёт даже n = 0.

Но мы рассматриваем это в общем случае, так что ищем 10n - 1, кратное 7. Конечно, таких n много, но нам бы хотелось что-то максимально простое, близкое к нулю.

Среди отрицательных 10n - 1 будет заканчиваться цифрой 1. Среди положительных — цифрой 9. Мы знаем, что -21 делится на 7, и 49 делится на 7.

-21 = 10*(-2) - 1
49 = 10*5 - 1

Так что самые близкие к нулю n — -2 и 5. Зависит от того, что вы больше любите делать — умножать или вычитать.

Так что:
k = -21Dy/7 - 2
k = 49Dy/7 + 5

k = -(3Dy + 2)
k = 7Dy + 5

Выбирайте сами. Я рекомендую второй случай для небольших Dy, а первый — для больших.

Рассмотрим на примере числа 7, у которого k = -2; 5.

14.
1 + 4*5 = 21.
1 - 4*2 = -7.

21.
2 + 1*5 = 7.
2 - 1*2 = 0.

8769775.
876977 + 5*5 = 877002
87700 + 2*5 = 87710
8771 + 0*5 = 8771
877 + 1*5 = 882
88 + 2*5 = 98
9 + 8*5 = 49

8769775.
876977 - 5*2 = 876967
87696 - 7*2 = 87682
8768 - 2*2 = 8764
876 - 4*2 = 868
86 - 8*2 = 70
7 - 0*2 = 7

Красиво.

Кажется, кто-то говорил, что у него по пятницам — воскресеньям выходной.

Ну и да, эти признаки должны быть известны миру, но всегда приятно открывать что-то самому, да?