A triangular representation for the divisor summatory function, $D(x)$

Solution 1:

Yes, this is true. Write $D(x) = \sum_{n \le x} d(n) = \sum_{n \le x} \sum_{d | n} 1 = \sum_{d \le x} \lfloor \frac{x}{d} \rfloor$; this is equivalent to the pattern you observe. The last step is exchanging the order of summation together with the observation that the number of times a number $d$ appears in the double sum is the number of numbers less than or equal to $x$ it divides.

Solution 2:

This answer is a bit of a work in progress, but if $n=2^x-1$, then $$\frac{D(n)+u}{2}=\sum_{j\in\mathcal{N}}\sum_{i=1}^{n}{h_{i,j}} \text{ where } u=\lfloor\sqrt{n}\rfloor$$

where $h_{i,j}$ is the value in the corresponding row,column of the matrix described in https://crypto.stackexchange.com/questions/27003/has-anyone-heard-of-matrix-based-roman-doll-encryption-techniques

Furthermore, letting $r_j=\sum_{i\in\mathcal{N}}{h_{i,j}}$, we write:

$$ D(2^k-1)=u-\xi+2\sum_{l=0}^{k-1}\frac{(k-l+1)(k-l)}{2}\sum_{j=\lfloor 2^{l-1}\rfloor }^{2^l-1}{r_j} $$

where $\xi$ is computed using the program:

input k
unsigned step = 1
unsigned y = 1
unsigned $\xi$ = 0
while y < 2^k {
    unsigned bin=(unsigned)log2(y)
    $\xi$ = $\xi$ + (k-bin)(k-bin+1-(k-bin)%2)
    y = y + 8* step
    step = step + 1
}
output $\xi$

This suggests a slim possibility of computing $D(x)$ in $log_2(x)$ time.