Cómo probar$\left\lfloor\frac{\sigma{(n-1)}+1}{2}\right\rfloor\le f(n)<\left\lfloor\frac{\sigma{(n-1)}+1}{2}\right\rfloor+n$

Question

Pregunta:

deje que$x_{1},x_{2},\cdots,x_{n}$ sea tal que $$n\ge 3,x_{1}\le x_{2}\le\cdots \le x_{n},$$$ $x_{1}x_{2}x_{3}\cdots x_{n}=x_{1}+x_{2}+\cdots +x_{n}.$ $

Deje que el número de pares ordenados de enteros positivos$(x_{1},x_{2},\cdots,x_{n})$ sea$f(n)$.

Demuestre que:$$\left\lfloor{\dfrac{\sigma{(n-1)}+1}{2}}\right\rfloor\le f(n)<\left\lfloor{\dfrac{\sigma{(n-1)}+1}{2}}\right\rfloor +n

donde$\lfloor{x}\rfloor$ es el número entero más grande que no sea mayor que$x$ y$\sigma(n)$ es el número de divisores (positivos) de n.

Answer 1

Para el LHS: si $d\mid(n-1)$$d\geq\frac{n-1}{d}$, luego eligiendo la opción $x_n=d+1$, $x_{n-1}=\frac{n-1}{d}+1$ y todos los otros $(n-2)$ variables igual a uno, se obtiene: $$\prod_{i=1}^{n} x_i = n-1+d+\frac{n-1}{d}+1 = (d+1)+\left(\frac{n-1}{d}+1\right)+(n-2)=\sum_{i=1}^{n} x_i$$ como quería. Tenemos $d(n-1)/2$ opciones si $(n-1)$ no es un cuadrado y $(d(n-1)+1)/2$ lo contrario. Ya hemos dado cuenta de todas las posibilidades $(x_1,x_2,\ldots,x_{n-1},x_n)=(1,1,\ldots,a,b)$, con el fin de demostrar la RHS sólo necesitamos limitar el número de soluciones que tienen tres o más coordenadas diferente de uno. Desde $y_1,\ldots,y_m\geq 2$ implica $$\prod_{i=1}^{m}y_i =\prod_{i=1}^{m}(1+(y_1-1))\geq\sum_{i=1}^{m}y_i+2^m-2m,$$ si $(1,1,\ldots,y_1,\ldots,y_m)$ es una solución con la última $m$ coordenadas $\geq 2$,$2^m-m \leq n$, lo $m$ está delimitado por $1+\log_2 n$. Si logramos demostrar que $y_m$ no puede ser demasiado grande, demasiado, casi hemos terminado. Desde: $$m y_m + (n-m)\geq\sum x_i =\prod x_i \geq 2^{m-1} y_m,$$ asumiendo $m\geq 3$ tenemos $y_m\leq\frac{n-m}{2^{m-1}-m}\leq\frac{n-m}{2^{m-3}}$, por lo que el número de soluciones con $m\geq 3$ está delimitada por: $$\sum_{m=3}^{\left\lfloor 1+\log_2 n\right\rfloor}\frac{(8n-8m)^m}{2^{m^2} m!}=O(n^3),$$ todavía demasiado. De todos modos, el multi-dimensional de Dirichlet hipérbola método da que el número de $(z_1,\ldots,z_m)\in\mathbb{N}_{\geq 2}^m$ tal que $$\prod_{i=1}^{m}z_i-\sum_{i=1}^{m}z_1 = L$$ es $L\log L+O(L)$, de ahí que el número de la solución con tres o más coordenadas mayor que dos es la delimitada por: $$\sum_{m=3}^{\lfloor 1+\log_2 n\rfloor}\frac{2(n-m)\log(n-m)}{m!}\leq\frac{1}{2}n\log n$$ que es sólo un logarítmica del factor aparte de lo que queremos demostrar.

---

Una convexidad argumento de conjunto de la cuestión. La variedad algebraica en ${\mathbb{R}_{+}^{m}}$ da por: $$\prod_{i=1}^{m}z_i-\sum_{i=1}^{m}z_i = L$$ es convexa, por lo que no puede tener más de $m$ entero puntos en ella. Como consecuencia, el número de soluciones con tres o más coordenadas mayor que dos es la delimitada por: $$\sum_{m=3}^{\lfloor 1+\log_2(n)\rfloor}\!\!\!m\leq\frac{(1+\log_2 n)^2}{2}.$$ En conclusión, para cualquier $n\geq 6$:

$$\left\lfloor\frac{d(n-1)+1}{2}\a la derecha\rfloor\leq f(n)< \left\lfloor\frac{d(n-1)+1}{2}\a la derecha\rfloor+\log_2^2 n.$$

El resto de los casos se $n=3,4,5$ son de fácil comprobación por la mano.