Demostrar que $10\mid A000793(n\ge16)$

Question

Demuestra que si $n\ge16$, entonces $10\mid g(n)$, donde $g(n)$ es el MCM más grande de las particiones de $n.

Para más información, visita http://oeis.org/A000793

Aquí está la lista de $g(n)$ para $n>0$, $g(15)=105, g(16)=140.$ $1, 2, 3, 4, 6, 6, 12, 15, 20, 30, 30, 60, 60, 84, 105, 140, 210, 210, 420, 420, 420, 420, 840, 840, 1260, 1260, 1540, 2310, 2520, 4620, 4620, 5460, 5460, 9240, 9240, 13860, \cdots$

Si $a_1+a_2+\cdots +a_k=n,$ y MCM$(a_1,a_2,\cdots ,a_k)=g(n),$ entonces necesitamos demostrar que al menos uno de $a_i$ es par, y uno de $a_i$ es divisible por 5.

PD: Esta es solo mi conjetura, quizás esté equivocada, visita http://oeis.org/A000793/b000793.txt

¡Gracias de antemano!

Answer 1

Voy a probar primero el reclamo por @Gerry Myerson en los comentarios: Para cada $m$ existe $n_0$ tal que $n>n_0$ implica $m \mid g(n)$. Al final, me muestran que la $10 \nmid g(n) \Rightarrow n<1550$.

En primer lugar, un trivial lema:

Lema 1: Si $a_1, a_2, \ldots , a_k \geq 2$ son enteros positivos, entonces $a_1a_2 \ldots a_k \geq a_1+a_2+ \ldots +a_k$.

Prueba: procedemos por inducción sobre $k$. Esto es claramente cierto al $k=1$. Al $k=2$, ya que el $(a_1-1)(a_2-1) \geq 1$, podemos llegar fácilmente a $a_1a_2 \geq a_1+a_2$. Supongamos que se tiene para $k=i$. A continuación, $a_1a_2 \ldots a_ia_{i+1} \geq (a_1+a_2+ \ldots +a_{i-1})+a_ia_{i+1}$ por la hipótesis de inducción. Por el caso base donde$k=2$,$a_ia_{i+1} \geq a_i+a_{i+1}$, de modo que se hace por inducción.

Ahora, supongamos que tenemos $n=x_1+x_2+ \ldots +x_t$, $lcm(x_1, x_2, \ldots, x_t)=g(n)$. Si $x_i$ ni $1$ ni una fuente primaria de energía para algunos $i$, entonces podemos escribir $x_i=a_1a_2 \ldots a_k, k \geq 2$, donde cada una de las $a_j$ es una fuente primaria de energía. Por el lema $1$, entonces podemos reemplazar $x_i$ $k+1$ términos: $a_1, a_2, \ldots , a_k$, e $x_i-(a_1+a_2+ \ldots +a_k)$. (El último término es inexistente si la igualdad tiene) Esto no va a disminuir el mcm de los números, por lo que podemos asumir con seguridad que todos los $x_i$ son los principales poderes (o 1).

Para un primer $p$, definir $f_p(n)=v_p(g(n))$. Claramente si $f_p(n) \geq 1$, $p^{f_p(n)}$ debe ser uno de los términos en la partición de $n$ con lcm $g(n)$. (Ya hemos asumido que todos los términos son de $1$, o el primer poderes)

Queremos demostrar que para cualquier entero positivo $m$, hay un número finito de $n$ s.t. $m \nmid g(n)$. Claramente no es suficiente para mostrar esto para $m$ una fuente primaria de energía. ($m=1$ es trivial)

Deje $m=p^a$. Supongamos que $m \nmid g(n)$. A continuación,$f_p(n) \leq a-1$.

Considere la posibilidad de cualquier prime $q \not =p$. Si $q \mid g(n)$, $q^{f_q(n)}$ es un término que en la partición. Definir $b_q=\lceil \frac{\log{q}}{\log{p}} \rceil$. A continuación,$p^{b_q}>q$.

Si $p^{a-1+b_q}+q^{f_q(n)-1} \leq q^{f_q(n)}$, podemos reemplazar $q^{f_q(n)}$ $3$ términos $p^{a-1+b_q}$, $q^{f_q(n)-1}$, y $q^{f_q(n)}-(p^{a-1+b_q}+q^{f_q(n)-1})$. (El tercer término es inexistente si la igualdad tiene) Ahora, $v_p(lcm)$ es ahora igual a $a-1+b_q \geq a$, e $v_q(lcm)$ al menos $f_q(n)-1$. Desde $p^{a-1+b_q}q^{f_q(n)-1}>p^{a-1}q^{f_q(n)} \geq p^{v_p(n)}q^{f_q(n)}$, el lcm de la partición se ha incrementado, por lo $g(n)$ no es el más grande de la lcm, una contradicción.

Por lo tanto,$p^{a-1+b_q}+q^{f_q(n)-1}>q^{f_q(n)}$. Por lo tanto $p^aq \geq p^{a-1+b_q}>q^{f_q(n)}-q^{f_q(n)-1}=(q-1)q^{f_q(n)-1}$, lo $f_q(n)<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}}$.

Si $q \nmid g(n)$,$f_q(n)=0<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}}$.

Por lo tanto si $p^a \nmid g(n)$, $f_q(n)<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}}$ para todos los números primos $q \not =p$.

Tenga en cuenta que $f_p(n)+1 \leq a<1+\frac{\log{(\frac{p}{p-1}p^a)}}{\log{p}}$.

Procedemos a mostrar que si $q$ es lo suficientemente grande (en relación a$p, a$),$p^a \nmid g(n) \Rightarrow q \nmid g(n)$.

Podemos probar, primero, $2$ lemas:

Lema 2: Deje $S$ ser un conjunto finito de números primos, y $q$ ser una de las primeras s.t. $q^2 \nmid g(n)$. Si $\sum_{s \in S}{s^{f_s(n)+1}} \leq q<\prod_{s \in S}{s}$,$q \nmid g(n)$.

Prueba: Si $q \mid g(n)$,$f_q(n)=1$, lo $q$ aparece en la partición. Podemos claramente reemplace $q$ por los términos de $s^{f_s(n)+1}, s \in S$$q-\sum_{s \in S}{s^{f_s(n)+1}}$. Desde $\prod_{s \in S}{s^{f_s(n)+1}}>\prod_{s \in S}{s^{f_s(n)}}q$, el lcm de la partición se ha incrementado como resultado, por lo que tenemos una contradicción. Por lo tanto,$q \nmid g(n)$.

Lema 3: Deje $p_i$ el valor del $i$th prime. A continuación, para$i \geq 3$,$p_{i+1}^2+p_{i+2}^2+p_{i+3}^2<p_{i}p_{i+1}p_{i+2}$.

Prueba: Por Bertrand postulado, $p_{i+3} \leq 2p_{i+2} \leq 4p_{i+1}$, lo $p_{i+1}^2+p_{i+2}^2+p_{i+3}^2<p_{i+1}p_{i+2}+2p_{i+1}p_{i+2}+8p_{i+1}p_{i+2} \leq p_ip_{i+1}p_{i+2}$$i \geq 4$. Al $i=3$, claramente tenemos $7^2+11^2+13^2=339<385=5(7)(11)$.

Ahora, tenga en cuenta que para el prime $q>p^a$,$q-1 \geq p^a$, lo $f_q(n)<1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \leq 2$. Por lo tanto $f_q(n) \leq 1$. Deje $c=\max(\pi(p^a), 2) \geq 2$, y considerar la posibilidad de $q \geq p_{c+1}^2+p_{c+2}^2+p_{c+3}^2$. Deje $d$ ser el mayor entero positivo tal que $q \geq p_d^2+p_{d+1}^2+p_{d+2}^2$. Claramente $d \geq c+1 \geq 3$, por lo que por el maximality de $d$ y el lema $3$ tenemos $q<p_{d+1}^2+p_{d+2}^2+p_{d+3}^2<p_dp_{d+1}p_{d+2}$.

Desde $q>p_{d+2}>p_{d+1}>p_d \geq p_{c+1}>p^a$, $f_{p_{d+2}}(n), f_{p_{d+1}}(n), f_{p_d}(n), f_q(n) \leq 1$. Por lo tanto,$p_d^{f_{p_d}(n)+1}+p_{d+1}^{f_{p_{d+1}}(n)+1}+p_{d+2}^{f_{p_{d+2}}(n)+1} \leq p_d^2+p_{d+1}^2+p_{d+2}^2 \leq q<p_dp_{d+1}p_{d+2}$, así que por lema $2$ tenemos $q \nmid g(n)$.

Por lo tanto, $p^a \nmid g(n) \Rightarrow q \nmid g(n)$$q \geq p_{c+1}^2+p_{c+2}^2+p_{c+3}^2$.

La combinación de esta con la anterior límites en $f_q(n)$, obtenemos:

$$p^a \nmid g(n) \Rightarrow pg(n) \mid \prod_{q \text{prime} \atop q< p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}$$

Esto le da

$$g(n)<pg(n) \leq \prod_{q \text{prime} \atop q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}=\prod_{q \text{prime} \atop q \leq p^a}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}\prod_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q}$$

Esto implica claramente que el

$$\begin{align} n<\sum_{q \text{prime} \atop q \leq p^a}{q^{\left \lfloor 1+\frac{\log{(\frac{q}{q-1}p^a)}}{\log{q}} \right \rfloor}}+\sum_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q} & \leq \sum_{q \text{prime} \atop q \leq p^a}{(\frac{q^2}{q-1}p^a)}+\sum_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q} \\ & \leq p^a\sum_{q \text{prime} \atop q \leq p^a}{(q+2)}+\sum_{q \text{prime} \atop p^a<q<p_{c+1}^2+p_{c+2}^2+p_{c+3}^2}{q} \end{align}$$

Así pues, hemos demostrado que para cualquier entero positivo $m$ existe $n_0$ s.t. $n>n_0$ implica $m \mid g(n)$. De hecho, las anteriores obligado se ve fácilmente ser $O(m^4)$.

Aplicación a $m=10$: Tenemos que $$2 \nmid g(n) \Rightarrow n<2\sum_{q \text{prime} \atop q \leq 2}{(q+2)}+\sum_{q \text{prime} \atop 2<q<5^2+7^2+11^2}{q}=3837$$

$$5 \nmid g(n) \Rightarrow n<5\sum_{q \text{prime} \atop q \leq 5}{(q+2)}+\sum_{q \text{prime} \atop 5<q<7^2+11^2+13^2}{q}=10261$$

Por lo tanto $10 \nmid g(n) \Rightarrow n<10261$.

De hecho, podemos hacer mucho mejor con un simple refinamiento. Tenga en cuenta que por los resultados anteriores, $2 \nmid g(n) \Rightarrow q \nmid g(n)$$q \geq 5^2+7^2+11^2=195$. Observar que $f_2(n)=0$$f_p(n) \leq 1$$p \geq 3$. Considere la posibilidad de $85 \leq q<195$, entonces a partir de la $$2^{f_2(n)+1}+3^{f_3(n)+1}+5^{f_5(n)+1}+7^{f_7(n)+1} \leq 2^1+3^2+5^2+7^2=85 \leq q<195<2(3)(5)(7)$$ , we have by lemma $2$ ($f_q(n) \leq 1$) that $q \nmid g(n)$.

El mismo argumento, a continuación, da $$2 \nmid g(n) \Rightarrow n<2\sum_{q \text{prime} \atop q \leq 2}{(q+2)}+\sum_{q \text{prime} \atop 2<q<85}{q}=880$$

Del mismo modo, $5 \nmid g(n) \Rightarrow q \nmid g(n)$$q \geq 7^2+11^2+13^2=339$. Observar que $f_5(n)=0$$f_p(n) \leq 1$$p \geq 5$. Considere la posibilidad de $175 \leq q<339$, entonces a partir de la $$5^{f_5(n)+1}+7^{f_7(n)+1}+11^{f_{11}(n)+1} \leq 5^1+7^2+11^2=175 \leq q<339<(5)(7)(11)$$ , we have by lemma $2$ ($f_q(n) \leq 1$) that $q \nmid g(n)$.

Ahora$f_2(n)<\lfloor 1+\frac{\log{2(5)}}{\log{2}} \rfloor=5$$f_3(n)<\lfloor 1+\frac{\frac{3}{2}(5)}{\log{3}} \rfloor=3$. Por lo tanto $f_2(n) \leq 4, f_3(n) \leq 2$. Considere la posibilidad de $113 \leq q<175$, entonces a partir de la $$2^{f_2(n)+1}+3^{f_3(n)+1}+5^{f_5(n)+1}+7^{f_7(n)+1} \leq 2^5+3^3+5+7^2=113 \leq q<175<2(3)(5)(7)$$ , we have by lemma $2$ ($f_q(n) \leq 1$) that $q \nmid g(n)$.

El mismo argumento, a continuación, da $$5 \nmid g(n) \Rightarrow n<5\sum_{q \text{prime} \atop q \leq 5}{(q+2)}+\sum_{q \text{prime} \atop 5<q<113}{q}=1550$$

Por lo tanto $10 \nmid g(n) \Rightarrow n<1550$. La pequeña de los casos se puede comprobar fácilmente con un ordenador.