Una representación triangular para el divisor summatory función, $D(x)$

Question

Deje $d(n)$ representan el divisor de la función como

$d(n)=\displaystyle\sum\limits_{k|n}1$

y el divisor summatory función como

$D(x)=\displaystyle\sum\limits_{n \leq x}d(n)$

He encontrado el siguiente triangular representación de los valores de $D(n)$

$$ \begin{array}{ccccccccc} D(1)=&&&&&&&&& 1 &&&&&&&&&&=1\\ &\\ D(2)=&&&&&&&& 2 &+& 1 &&&&&&&&&=3\\ &\\ D(3)=&&&&&&& 3 &+& 1 &+& 1 &&&&&&&&=5\\ &\\ D(4)=&&&&&& 4 &+& 2 &+& 1 &+& 1 &&&&&&&=8\\ &\\ D(5)=&&&&&5 &+& 2 &+& 1 &+& 1 &+& 1&&&&&&=10\\ &\\ D(6)=&&&&6 &+& 3 &+& 2 &+& 1 &+& 1 &+& 1&&&&&=14\\ &\\ D(7)=&&&7 &+& 3 &+& 2 &+& 1 &+& 1 &+& 1&+& 1 &&&&=16\\ &\\ D(8)=&&8 &+& 4 &+& 2 &+& 2 &+& 1 &+& 1&+& 1&+&1&&&=20\\ &\\ \end{array} $$

Los valores de la derecha son la suma de todos los elementos en una fila.

---

EDIT 1:

La imagen de arriba es el resultado de la siguiente observación:

Deje $v_{m}(n)$ ser el mayor poder de la $m$ que divide $n$$ m,n \in \mathbb{N}$ , por lo que tenemos que

$D(n)=\displaystyle\sum\limits_{m=2}^{\infty}v_{m}(p^{n}), p \in \mathbb{P}$ donde $p$ fijo es un número primo.

Yo no tratamos de probar este. No sé cómo hacerlo, pero espero que alguno tendrá alguna idea sobre cómo probar o refutar esta hipótesis.

---

Me gustaría saber si esto es un hecho conocido. No tengo una prueba, pero he probado un montón de valores y trabaja todo el tiempo.

Gracias.

Answer 1

Sí, esto es cierto. Escribir $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$; esto es equivalente a que el patrón que se observa. El último paso es el intercambio de la orden de la recapitulación, junto con la observación de que el número de veces que un número $d$ aparece en el doble de la suma es el número de números de menos de o igual a $x$ se divide.

Answer 2

Esta respuesta es un poco de un trabajo en progreso, pero si $n=2^x-1$, $$\frac{D(n)+u}{2}=\sum_{j\in\mathcal{N}}\sum_{i=1}^{n}{h_{i,j}} \text{ where } u=\lfloor\sqrt{n}\rfloor$ $

donde $h_{i,j}$ es el valor en la correspondiente fila,columna de la matriz se describe en http://crypto.stackexchange.com/questions/27003/has-anyone-heard-of-matrix-based-roman-doll-encryption-techniques

Además, dejando $r_j=\sum_{i\in\mathcal{N}}{h_{i,j}}$, podemos escribir:

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

donde $\xi$ se calcula utilizando el programa:

de entrada k
unsigned paso = 1
sin firmar y = 1
sin signo $\xi$ = 0
mientras que y < 2^k {
unsigned bin=(unsigned)log2(y)
$\xi$ = $\xi$ + (k-bin)(k-bin+1-(k-bin)%2)
y = y + 8* * * paso
paso = paso + 1
}
salida $\xi$

Esto sugiere una pequeña posibilidad de computación $D(x)$ $log_2(x)$ del tiempo.