Закономерность в столбце матрицы

[maravan]

Имеем большую матрицу $m \times m$, в строках есть простая закономерность - 1-ца появляется через столбец, потом через 2 (для следующей строки), и т.д.

$\begin{vmatrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & ...\\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & ...\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & ...\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & ...\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & ...\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & ...\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & ...\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ...\\ ... \end{vmatrix}$

Можно ли быстро посчитать сумму произвольного столбца, например, для 1-го - 0, для 2-го - 1, для 3-го -1, для 4-го - 2, и т.д?

В голову пришел приблизительно такой алгоритм:
1. Получаем формулу (получил) для $i$-той строки, до $j$-того столбца, т.е. $f(i,j)$, например$ f(1,2) = 1$, $f(1,3) = 10$, $f(1,4) = 101$, и т.д.
2. Получаем формулу $g(i,j)$ (не могу получить) последней цифры $f(i,j)$, например $g(1,2) = 1$, $g(1,3) = 0$, $g(1,4) = 1$
3. Суммируем $g(i,j)$ до $i$-ой строки для $j$-того столбца, $h(j) = \sum\limits_{k=1}^{j-1} g(k,j)$, и надеемся, что эта сумма свернется в функцию без суммы.

Подскажите пожалуйста можно ли получить формулу для пункта 2? Или существует ли другая стратегия решения задачи?

[AKM]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

[mihiv]

Сумма элементов $j-$ого столбца равна числу делителей числа $j$ минус 1.Например, $j=8$, делители: 1,2,4,8. Всего 4 штуки. Сумма элементов $4-1=3$.

[maravan]

2 mihiv: Т.е алгоритмическая сложность Вашего алгоритма, приблизительно будет $O(j^ \frac {1} {3})$, а быстрее можно, как Вы думаете мой алгоритм, имеет право на существование?

[ИСН]

Ваш алгоритм содержит слово "надеемся", т.е. относится к алгоритмам с божественным вмешательством. Тут напрямую сравнивать вообще нельзя.
Впрочем, конечно, сумма свернётся в функцию без суммы. Какая будет функция - тут два варианта: либо такая же, либо неправильная.