О признаках делимости
Можно заметить, что признаки делимости на 3, 7, 11 и др. - это обман трудящихся, поскольку они не дают асимптотически значимого выигрыша по сравнению с прямолинейным делением. Например, признак делимости на 3 требует сложить цифры числа по модулю 3, что дает ~N операций, где N - количество цифр числа, в то время как деление уголком дает те же O(N). А если при делении не записывать цифры частного, а только остатки, то и коэффициент при O можно считать равным единице, поскольку в обоих случаях элементарные операции примерно совпадают по сложности.
Истинными же являются признаки делимости на 2 и на 5 (а также на любое число, составленное из 2 и 5), которые имеют сложность O(1).
В связи с этим предлагаю теорему (точнее, пока гипотезу). Для любой системе счисления с основанием q не существует хороших признаков делимости (то есть имеющих сложность лучше чем O(N)) ни на какие числа, за исключением тех, что составлены из делителей q (для них сложность O(1)).
Истинными же являются признаки делимости на 2 и на 5 (а также на любое число, составленное из 2 и 5), которые имеют сложность O(1).
В связи с этим предлагаю теорему (точнее, пока гипотезу). Для любой системе счисления с основанием q не существует хороших признаков делимости (то есть имеющих сложность лучше чем O(N)) ни на какие числа, за исключением тех, что составлены из делителей q (для них сложность O(1)).