Número de triples de divisores que son relativamente primos como un triple

Question

Dado un número $n \in \mathbb{N}$, definir $a(n)=\{(d_1,d_2,d_3): d_i|n,\ \gcd(d_1,d_2,d_3)=1,\ 1 \leq d_1 \leq d_2 \leq d_3\}$. ¿Qué es $|a(n)|$?

Allí fueron similares a preguntas frecuentes acerca de los pares en lugar de triples aquí: Número de pares de trivial relativamente primos divisores y aquí: Número de Relativamente Factores Primos , pero la adición de la tercera componente parece que los argumentos que se usan en estas dos preguntas obsoletos.

Un ejemplo:

Deje $n=p$ para algunos prime $p$. Entonces los divisores de $n$$\{1,p\}$, y los triples de los divisores de los cuales son relativamente primos (no importa el orden) como un triple a se $\{(1,1,1),(1,1,p),(1,p,p)\}$. Así vemos que para cualquier prime, la respuesta es $|a(n)|=3$.

De manera similar, (no es difícil comprobar) por $n=p^2$,$|a(n)|=6$.

De hecho, si dejas $n=p^k$$0 \leq k \in \mathbb{Z}$, parece que $|a(n)|={{k+2} \choose {2}}$.

También para $n=pq$ donde $p$ $q$ son distintos de los números primos, $|a(n)|=13$ (de nuevo, no es difícil de comprobar).

Esto me lleva a creer que, como en los otros las respuestas a las dos preguntas que se hace referencia, la respuesta se puede encontrar el uso de algunas buenas combinaciones, pero si miraba justo a la derecha de un Número perspectiva Teórica, puede ser una función multiplicativa o composición de funciones multiplicativas, basado en las respuestas parecen depender sólo de las potencias de los números primos en la factorización en primos de un número.

Answer 1

Como en el par de casos, primero se debe encontrar el número de ordenadas triples sin restricciones en el orden de las entradas.

Cada primer factor de $p_i$ con multiplicidad $a_i$ se produce en más de dos divisores.

No es $1$ camino de $p_i$ a ocurrir en divisores de cero.

Hay $3a_i$ formas para $p_i$ a ocurrir en un divisor.

Hay $3a_i^2$ formas para $p_i$ a ocurrir de dos divisores.

Por lo tanto, en total hay $3a_i^2+3a_i+1$ formas de distribuir $p_i^{a_i}$ más de los divisores, y por lo tanto no se $\prod_i(3a_i^2+3a_i+1)$ ordenado triples. De esto queremos deducir el número de desordenada triples (o, de manera equivalente, el número de ordenadas triples, con el fin de las restricciones en las entradas).

Hay una triple con tres de la igualdad de las entradas, es decir,$(1,1,1)$. Hay $\prod_i(2a_i+1)-1$ pares ordenados de distintas coprime divisores de cada uno de los cuales corresponde a tres ordenó triples, con dos igualdad de las entradas pero sólo una desordenada triple con dos igualdad de las entradas. Así, el conde de desordenada triples es

$$ \frac{\prod_i(3a_i^2+3a_i+1)-3\left(\prod_i(2a_i+1)-1\right)-1}6+\prod_i(2a_i+1)-1+1=\frac{\prod_i(3a_i^2+3a_i+1)+3\prod_i(2a_i+1)+2}6\;. $$

Usted puede comprobar que su ejemplos de todo saliera bien.

Answer 2

De hecho, si dejas $n=p^k$$0 \leq k \in \mathbb{Z}$, parece que $|a(n)|={{k+2} \choose {2}}$.

Si $n=p^k$ podemos escribir el triple como $(p^r, p^s, p^t)$$r \le s \le t$. Desde el MCD de la triple a es $1$, claramente $r = 0$. Así que usted está contando los valores enteros de a $s, t$ tal que $0 \le s \le t \le k$. Si $s \neq t$ hay $\binom{k+1}{2}$ maneras de elegir de $k+1$ opciones; si $s = t$ hay $\binom{k+1}{1}$ formas; y $\binom{k+1}{2} + \binom{k+1}{1} = \binom{k+2}{2}$.

---

En la general de la cuestión, vamos a $q$ ser el primer y coprime a $n$, y considerar la posibilidad de $(d_1, d_2, d_3) \in a(nq^k)$. Podemos proyectar $d_i$ a $n$ $q^k$ tomando el MCD, por lo $\textrm{sort}(\gcd(d_1, n), \gcd(d_2, n), \gcd(d_3, n)) \in a(n)$ (donde $\textrm{sort}$ da la orden de triple) y de manera similar para $q^k$. Esto le da un límite superior $$a(nq^k) \le 3!\, a(n)\, a(q^k)$$ where the factor of $3!$ is the number of ways to sort 3 items (wlog the triple from $q^k$, when pairing up its elements with the elements of the triple from $$ n). Sin embargo, necesitamos tener en cuenta el hecho de que los triples no están obligados a tener 3 diferentes valores, por lo que algunas de las órdenes de crear duplicados.

Podemos dividir $a(n)$ hasta en tres partes: triples, con un valor distinto a $a_1(n) = \{(1,1,1)\}$; triples, con dos valores distintos $a_2(n)$; y triples con tres valores distintos $a_3(n)$. Triples, con dos valores distintos romper $(r, r, s)$ o $(r, s, s)$. Al $n=p^k$ tenemos $(1, 1, p^r)$ o $(1, p^r, p^r)$$0 < r \le k$, por lo que $a_2(p^k) = 2k$. $a_3(p^k) = \binom{k}{2}$ por argumentos similares a la primera sección. Como una comprobación de validez, $a_1(p^k) + a_2(p^k) + a_3(p^k) = 1 + 2k + \binom{k}{2} = \binom{k+2}{2}$.

Ahora tenemos nueve casos para la vinculación de un elemento de $a(n)$ con un elemento de $a(q^k)$. Cinco de ellos están cubiertos por la observación de que $(1,1,1)$ emparejado con un elemento de $i$ valores distintos da un elemento de $i$ valores distintos. Que hojas:

• Dos con dos: $(d_1, d_1, d_2)$ emparejado con la $(e_1, e_1, e_2)$ da $(d_1 e_1, d_1 e_1, d_2, e_2)$ (dos elementos distintos) y $(d_1 e_1, d_1 e_2, d_2 e_1)$ (ya que estamos construyendo desde coprime partes) tiene tres elementos distintos.
• Dos, con tres: tres permutaciones de cada uno de los tres elementos distintos.
• Tres con tres: los seis permutaciones de tres elementos distintos.

Así, obtenemos la recurrencia $$\begin{eqnarray} a_1(nq^k) &=& a_1(n) a_1(q^k) \\ a_2(nq^k) &=& a_1(n) a_2(q^k) + a_2(n) a_1(q^k) + a_2(n) a_2(q^k) \\ a_3(nq^k) &=& a_1(n) a_3(q^k) + a_3(n) a_1(q^k) + a_2(n) a_2(q^k) +\\&& 3a_2(n) a_3(q^k) + 3a_3(n) a_2(q^k) + 6a_3(n) a_3(q^k) \end{eqnarray}$$

y podemos sustituir y simplificar a

$$\begin{eqnarray} a_1(nq^k) &=& 1 \\ a_2(nq^k) &=& (2k+1)(a_2(n)+1) - 1 \\ a_3(nq^k) &=& \left(3k^2 + 3k + 1\right) a_3(n) + \frac{(3k+1)k}{2} a_2(n) + \frac{k(k-1)}{2} \end{eqnarray}$$

Si definimos $a_{1+2}(n) = a_1(n) + a_2(n)$, hay un buen simple recurrencia $a_{1+2}(nq^k) = (2k+1)a_{1+2}(n)$, pero no por $a_3$.