Menor potência de um primo cujas fatorações não têm somas distintas de fatores

Aug 18 2020

Problema

Dado um primo $p$, encontre o menor $n$ de modo que algumas fatorações não ordenadas de $p^n$ têm somas iguais de fatores.

As fatorações não ordenadas são fatorações em que a ordem dos fatores é irrelevante e não incluem o fator trivial $1$. Notar que$n\gt 1$ para todos os primos $p$ porque os números primos têm apenas uma fatoração não ordenada.


Exemplos

Prime $p=2$. É trivial que$n=2$ para $p=2$ Porque $2+2=2\cdot 2$. Ou seja, fatorações não ordenadas de$2^2$ está $4$ e $2\cdot 2$, e ambos têm a mesma soma de fatores $4 = 2+2$.

Prime $p=3$. Mas,$n=2$ não é uma solução para $p=3$ Porque $9\ne 3+3$. Nem é$n=3$ Porque $27\ne 3+9 \ne 3+3+3$. Nem é$n=4$ Porque $81\ne 27 + 3\ne 9 + 9\ne 9 + 3 + 3\ne 3 + 3 + 3 + 3$. Eventualmente, descobrimos que$n=12$ é o menor que se ajusta, porque então existem as seguintes somas duplicadas de fatores:

$$\begin{align}{} 3^{12}&=&27\cdot3^9&=&9^6 &\implies& 27+\sum_{i=1}^{9}3 &=& \sum_{i=1}^{6}9 &=& 54 \\ 3^{12}&=&81\cdot9\cdot 3^6&=&27^4 &\implies& 81+9+\sum_{i=1}^{6}3 &=& \sum_{i=1}^{4}27 &=& 108 \end{align}$$

Observe que se $p^{n}$ ou qualquer número em geral satisfaz essa propriedade, então todos os múltiplos desse número também a satisfazem.


Solução?

Prime $p\in\mathbb P$. Deixei$a(k)$ seja o menor tal $n_k$ Considerando a $k$o primeiro$p_k$. Nós temos:

$$a(k) = 2, 12, 26, 34, 50, 58, 74, 82, \dots$$

É possível encontrar e provar uma fórmula para esta sequência?

Percebi que o seguinte parece funcionar até agora: $a(1)=2,a(2)=12,a(k)=4p_k+6,k\ge 3$.

Isso ocorre por causa das seguintes fatorações não ordenadas:

$$\begin{align} p_k &\quad n &\quad \\ 2 &\quad 2 &\quad (2)(2) &=(2^2) \\ 3 &\quad 12 &\quad (3)^9(3^3) &= (3^2)^6 &\quad (3)^6(3^2)(3^4) &= (3^3)^4 \\ 5 &\quad 26 &\quad (5^2)^{11} (5^4) &= (5)^5(5^3)^7 \\ 7 &\quad 34 &\quad (7)^{15}(7^4) &= (7)^7(7^3)^9 \\ 11 &\quad 50 &\quad (11^2)^{23}(11^4) &= (11)^{11}(11^3)^{13}\\ 13 &\quad 58 &\quad (13^2)^{27}(13^4) &= (13)^{13}(13^3)^{15}\\ 17 &\quad 74 &\quad (17^2)^{35}(17^4) &= (17)^{17}(17^3)^{19}\\ 19 &\quad 82 &\quad (19^2)^{39}(19^4) &= (19)^{19}(19^3)^{21}\\ \end{align}$$

Observe que os primos $p_k\ge 5$ siga o seguinte padrão:

$$ (p^2)^{2p+1}(p^4) = (p)^{p}(p^3)^{p+2} \implies (p^2)\cdot(2p+1)+(p^4) = (p)\cdot p+(p^3)\cdot(p+2) $$

Isso nos dá um limite superior $a(k)\le 4p_k+6$ porque o padrão é válido para todos os números naturais.

A igualdade foi comprovada computacionalmente para alguns pequenos primos (como você pode ver acima).

Podemos provar que a igualdade sempre é válida? Ou seja, podemos provar$a(k)\ge 4p_k+6, k\ge 3$ ?

Ou seja, resta provar que todas as fatorações não ordenadas de números da forma

$$ p^{4p+5} $$

têm somas distintas de fatores para todos os primos $p\ge 5$.

Em outras palavras, precisamos provar que $\text{A001055}$$(p^{4p+5})$ $=$ $\text{A069016}$$(p^{4p+5})$.

Ou talvez exista um primo $p$isso é um contra-exemplo? Ie$p_k : a(k)\lt 4p_k+6$ ?

Respostas

3 QuangDao Aug 18 2020 at 18:05

Nota: minha solução é bastante longa e contém muitos casos, então alguns erros são inevitáveis. Avise-me se houver algo que precise de explicação.


Deixei $n$ seja o menor número tal que $p^n$têm duas fatorações não ordenadas com igual soma de fatores. Vamos assumir que$n \le 4p+5$ e derivar uma contradição.

Denotado por $A=(p^{a_1})^{n_1}\dots (p^{a_k})^{n_k}$ e $B=(p^{b_1})^{m_1}\dots(p^{b_l})^{m_l}$ as duas fatorações não ordenadas, com $a_1 > \dots > a_k$ e $b_1 > \dots > b_l$. Sem perda de generalidade, assuma que$A$ tem o poder superior de $p$, ou seja, que $a_1 \ge b_1$.

Observação 1: $\{a_1,\dots,a_k\} \cap \{b_1,\dots,b_l\}=\emptyset$.

Porque se $a_i=b_j$ para alguns $i,j$, então podemos subtrair $p^{a_i}$ de ambas as fatorações para obter duas fatorações não ordenadas com igual soma para $p^{n-a_i}$, contradizendo a minimalidade de $n$.

Observação 2: $a_1 \le 5$.

Isso vem considerando as equações $$\begin{equation}\label{eqn1} b_1m_1+\dots+b_lm_l=n \qquad (1)\end{equation}$$ e $$ \begin{equation} m_1p^{b_1}+\dots+m_lp^{b_l}=n_1p^{a_1}+\dots+n_kp^{a_k}\qquad (2)\end{equation}$$ Se você resolver para o máximo do LHS de (2) dado (1) (e com $m_j \in \mathbb{R}$ em vez disso), então o máximo é atingido em $m_1=n/b_1$ e $m_j=0$ para todos $j \ge 2$, onde o valor máximo é $\frac{n}{b_1}p^{b_1}$. Por outro lado, o RHS de (2) dá o limite inferior de$p^{a_1}$, portanto, devemos ter $$ \frac{n}{b_1} p^{b_1} \ge p^{a_1} \iff n \ge b_1 p^{a_1-b_1} .$$ Desde a $n \le 4p+5 \le p^2$ para $p \ge 5$, nós temos isso $$ a_1-b_1=2, b_1=1 \qquad \text{or} \qquad a_1-b_1=1, b_1 \le 4$$ e em ambos os casos $a_1 \le 5$.

Agora consideramos os vários casos $a_1 \in \{2,3,4,5\}$, com $a_1=4$ sendo o mais difícil.

  1. E se $a_1=2$, então $b_1=1$ e temos duas fatorações $(p^2)^{n/2}$ e $p^n$. Eles não têm igual soma de fatores para$p>2$.

  2. E se $a_1=3$, então temos as seguintes opções:

    • $a_2=2$, $b_1=1$. Temos duas fatorações$(p^3)^{n_1}(p^2)^{n_2}$ e $p^n$. Eles não têm soma igual desde$$np \le (4p+5)p < p^3$$ para $p \ge 5$.
    • $a_2=1$, $b_1=2$. Temos duas fatorações$(p^3)^{n_1}p^{n_2}$ e $(p^2)^{n/2}$. Desde a$$\frac{n}{2}p^2 \le \frac{4p+5}{2}p^2 < 3p^3$$ para $p \ge 5$, nós temos isso $n_1 \in \{1,2\}$. Qualquer um dos valores não leva à soma igual.
    • $b_1=2$, $b_2=1$. Temos duas fatorações$(p^3)^{n/3}$ e $(p^2)^{m_1}p^{m_2}$. Então$$ m_1 p^2+m_2p \le \frac{n}{2}p^2 < \frac{n}{3}p^3. $$
    • $b_1=2$. Nós temos$(p^3)^{n/3}$ e $(p^2)^{n/2}$, cujas somas não são iguais.
    • $b_1=1$. Nós temos$(p^3)^{n/3}$ e $p^n$, cujas somas não são iguais.
  3. E se $a_1=5$, então $b_1=4$como argumentamos acima. Pela mesma linha de argumento, podemos ver que$$ m_1p^4+\dots +m_l p^{b_l} < 2p^5 $$ para todas as escolhas de $m_1,\dots,m_l$, então $n_1=1$e $$ m_1p^4+\dots +m_l p^{b_l} \ge p^5 $$ apenas quando $m_1 \ge p$. Portanto, temos que$$ A = (p^5)\cdot(\text{unordered factorization of }p^{n-5}) \quad \text{and} \quad B= (p^4)^p\cdot(\text{unordered factorization of }p^{n-4p}).$$ Em particular, isso implica que $n \in \{4p, \dots, 4p+5\}$. Mais algumas verificações mostram que, para tal$n$, nenhuma fatoração de $p^{n-5}$ tem a mesma soma de fatores que qualquer fatoração de $p^{n-4p}$.

  4. E se $a_1=4$, então $b_1=3$ do argumento na Observação 2. Usando o mesmo argumento do caso acima, concluímos que $n_1=1$ e $m_1 \ge p$. Portanto, temos$$ A = (p^4)\cdot(\text{unordered factorization of }p^{n-4}) \quad \text{and} \quad B= (p^3)^p\cdot(\text{unordered factorization of }p^{n-3p}).$$ Resta considerar as seguintes opções para $a_2,\dots,a_k$:

    • $a_2=1$. Então se$A=(p^4)p^{n-4}$ e $B=(p^3)^{m_1}(p^2)^{m_2}$ ter soma igual, devemos ter $$ (n-4)p=(m_1-p)p^3+m_2p^2 \ge \frac{n}{2} p^2,$$ o que é falso para $p \ge 5$ e $n \le 4p+5$.
    • $a_2=2$, $a_3=1$. Então$A=(p^4)(p^2)^{n_2}p^{n_3}$ e $B=(p^3)^{n/3}$. Se suas somas forem iguais, então$$ (n/3-p)p^3=n_2p^2+n_3p$$ então em particular $p \mid n_3$. Desde a$n_3 \le n-4 \le 4p+1$ nós devemos ter $n_3 \in \{p,2p,3p,4p\}$. Conectando cada valor de$n_3$ e $n_2=n-4-n_3$ na equação, descobrimos que nenhum produz um valor inteiro para $n$.
    • $a_2=2$. Então$A=(p^4)(p^2)^{(n-4)/2}$ e $B=(p^3)^{m_1}p^{m_2}$. Se a soma deles for igual, então$$\frac{n-4}{2}p^2=(m_1-p)p^3+m_2p$$ então $p \mid m_2$, e semelhante ao anterior, obtemos $m_2 \in \{p,2p,3p\}$. Novamente, conectando cada valor de$m_2$ e $m_1=n-m_2$ na equação, descobrimos que nenhum produz um valor inteiro para $n \le 4p+5$.