Предоставляется такой, довольно-таки простой код с пре- и пост- условиями:
Надо доказать, что число в 2ичной системе счисления делится на 3, согда знакопеременная сумма его цифр делится на 3.
В более общем виде - число имеет тот же остаток от деления на n+1, что и знакопеременная сумма его цифр в n-ичной системе счисления.
Итак, есть число
a0 + a1*n + a2*n*n + a3*n*n*n + a4*n*n*n*n + ...
вычитаем из него (a0-a1+a2-a3+a4-...)
получаем
(a0*(1-1)) +
(a1*(n+1)) +
(a2*(n*n-1)) +
(a3*(n*n*n+1)) +
(a4*(n*n*n*n-1)) + ...
известно, что n^(2k)-1 делится на n+1 : n^(2k)-1 = (n^2-1)(1+n^2+...+n^(2k-2)) = (n+1)(n-1)(1+n^2+...+n^(2k-2))
и что n^(2k+1)+1 делится на n-1: n^(2k+1)+1 = (n+1)(1-n+n^2-...+n^(2k))
значит и вся сумма делится на n+1
а если разность двух чисел делится на n+1, значит у них одинаковый остаток от деления на него.
просто, и со вкусом (с)
TarasBer, благодарю