¿Cuántos posibles valores toma el producto de números de $n$?

Question

Que $S = \{1,2,...n\}$ y $s$, un elemento de $S$. Semejantemente, $T = \{1,2,...m\}$ y $t$ un elemento de $T$. Mi pregunta es, ¿cuántos valores de $st$ existen? Más generalmente, si estoy dado de $x$ tales establece cuántos valores de $stuv...$ existen (multiplicando los elementos de $x$).

Motivación: estaba tratando de resolver una versión más general de la $1990$ $B3$ de Putnam que cuadrar números de forma $st$ después de la multiplicación de matrices.

Answer 1

No es realmente una respuesta, pero sólo algunas observaciones que dan un límite superior y un límite inferior en el número de $p$ de los elementos de la $ST$.

Debemos tener los siguientes límites en $p$:

\begin{align*} mn \geqslant p \geqslant mn-m+1-\sum_{i=1}^m \left\lfloor \frac{(i-1)n}{i} \right\rfloor. \end{align*} La primera desigualdad es fácil, ya que $mn$ es el número más grande en $ST$. En cuanto a la segunda: podemos escribir todas las $s \in S$ $st$ tomando $t = 1 \in T$, el cual representa el $n$ elementos en $ST$. Tomando $t = 2$ y multiplicando este con todos los $s \in S$, vamos a conseguir los números de $2,4,\ldots, 2n$. Con el fin de asegurar que no estamos obteniendo cualquiera de los números que ya se han producido, tenemos que tomar $s \in S$$2s > n$, es decir. $s > \frac{n}{2}$, y por lo $s \geqslant \lfloor \frac{n}{2} \rfloor+1$. Esto nos da $n - \lfloor \frac{n}{2} \rfloor - 1$ nuevos números. Ahora, tomando $t = 3$ y multiplicar con todos los $s \in S$, obtendremos $3,6,\ldots,3n$. De nuevo, para asegurar que estamos recibiendo nuevos números, podemos tomar $s \in S$$3s > 2n$, que los rendimientos de $s \geqslant \lfloor \frac{2n}{3} \rfloor + 1$, y de este modo conseguimos $n - \lfloor \frac{2n}{3} \rfloor - 1$ nuevos números, y así sucesivamente.

Tengo la fuerte sospecha de que una respuesta precisa es la forma, la manera más difficiult a obtener.