Extraño divisores

Question

Deje $~m~$ $~n~$ ser enteros positivos. Vamos a llamar a (mi término - no asegurarse de que no hay ningún término oficial para tal cosa) número de $~m~$ un "extraño divisor" de número de $~n~$ si dividiendo $~n~$ $~m~$ tenemos equall cociente y el resto.

Por ejemplo, $~7 = 6\cdot 1 + 1~$ $~6~$ es una extraña divisor de $~7~$. Como otro ejemplo, $~15 = 4\cdot3 + 3~$ $~4~$ es extraño divisor de $~15$.

Desde mi definición anterior podemos deducir que $~m~$ es una extraña divisor de $~n~$ fib existe número $~0 \leq r < m~$ tal que $~n = (m + 1)r$. Vamos a denotar por $~f(n)~$ el número de todos los extraños divisores de número de $~n$. Me pregunto ¿cuál es el valor promedio de $~f(n)~$ por lo que necesitan una manera eficiente para calcular $~\sum_{n=1}^{N} f(n)~$. Alguna idea de cómo hacerlo rápido será muy apreciada. Creo que debe haber alguna manera de reducir el límite superior de $~N~$ $~\sqrt{N}~$ya que trabajamos con los divisores. Pero no veo la manera de hacerlo.

Answer 1

Dicen que tenemos: $$n=ab$$, Entonces: $$n = a(b-1)+a$$ Por lo $b-1$ sería lo que se llama un extraño divisor de $n$.

Así que lo que podría decir es que $$f(n) \approx \frac{1}{2}d(n)$$ Donde $d(n)$ es el número de divisores de a $n$. Desde $b-1$ debe ser mayor que $a$, sólo puede usar la mitad de los pares de $a,b$, que es la razón por la que se multiplican con la mitad.

Podemos aproximar $\sum_{N}^{n=1}f(n)$ cuando nos damos cuenta de que todos los números enteros de todos los divisible por $1$, la mitad de los números enteros es divisible por $2$, un tercio por $3$ etc. Obtenemos: $$\sum_{i=1}^{N}f(i) \approx \frac{1}{2}N\bigg(\sum_{i=1}^{N}\dfrac{1}{i}\bigg)=\frac{1}{2}N\cdot H_{N}\approx \frac{1}{2}N(\log N + \gamma)$$ Donde $\gamma$ es el de Euler-Mascheroni constante (alrededor de $0.5772$).

He comprobado esta fórmula y se sigue acercando. $$\sum_{i=1}^{100}f(i)=236$$ $$50(\log 100 + \gamma)=259$$

Y de una manera más: $$\sum_{i=1}^{10000}f(i)=46784$$ $$5000(\log 10000 + \gamma)=48938$$ El primer resultado es $7.47 \%$ y el segundo por $4.49\%$.

Answer 2

Vamos a trabajar hacia atrás:

m es un extraño y divisor de un número n, iff:

1. m+1 es un divisor de n, y
2. el cociente de n + m+1 es menor que m.

Lo que significa que, para un número m, es una extraña divisor de m+1, 2*(m+1), 3*(m+1).... (m-1)*(m+1), que es exactamente m-1 números.

Si nos tapa "extraño dividendos" de m a menos de un número fijo de N, entonces m va a ser un extraño divisor de:

min(piso($\frac{N}{(m+1)}$), m-1) números.

Aproximadamente, para valores de m < sqrt(n), la expresión es m-1. Para valores de m > sqrt(n), la expresión es baja(N/(m+1))

Hago la siguiente afirmación:

$\sum_{i=1}^N \text{(number of strange divisors of i)} = \sum_{m=1}^N \text{(number of numbers for which m is a strange divisor)}$

Así que nuestra suma es:

$\sum_{i=1}^{N} f(i) = \sum_{m=1}^{N} min(floor(\frac{N}{(m+1)}), m-1)$

$ \approx (\sum_{m=1}^{floor(\sqrt{N})} m - 1) + (\sum_{m=floor(\sqrt{N})}^N floor(\frac{N}{m+1})) $

$ \approx (floor(\sqrt{N}))*(floor(\sqrt{N}) - 1) * \frac{1}{2}$ + $ N*H_N - floor(\sqrt{N})*H_{floor(\sqrt{N})} $

donde $H_k$ $k^{th}$ número armónico

Nota: este valor no es exactamente la misma que la suma de los # divisores de los números de 1 a N, porque no todo divisor d corresponde a un extraño divisor d-1 (tiene que satisfacer a N/d < d-1)