Plus petite puissance d'un nombre premier dont les factorisations n'ont pas de sommes distinctes de facteurs
Problème
Étant donné un prime $p$, trouve le plus petit $n$ telle que certaines factorisations non ordonnées de $p^n$ ont des sommes égales de facteurs.
Les factorisations non ordonnées sont des factorisations où l'ordre des facteurs n'est pas pertinent et n'incluent pas le facteur trivial $1$. Remarquerez que$n\gt 1$ pour tous les nombres premiers $p$ car les nombres premiers n'ont qu'une seule factorisation non ordonnée.
Exemples
Premier $p=2$. C'est trivial que$n=2$ pour $p=2$ car $2+2=2\cdot 2$. Autrement dit, des factorisations non ordonnées de$2^2$ sont $4$ et $2\cdot 2$, et ils ont tous deux la même somme de facteurs $4 = 2+2$.
Premier $p=3$. Mais,$n=2$ n'est pas une solution pour $p=3$ car $9\ne 3+3$. Ni l'un ni l'autre$n=3$ car $27\ne 3+9 \ne 3+3+3$. Ni l'un ni l'autre$n=4$ car $81\ne 27 + 3\ne 9 + 9\ne 9 + 3 + 3\ne 3 + 3 + 3 + 3$. Finalement, nous constatons que$n=12$ est la plus petite qui correspond, car il existe alors les sommes de facteurs en double suivantes:
$$\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}$$
Notez que si $p^{n}$ ou tout nombre en général satisfait cette propriété, alors tous les multiples de ce nombre la satisfont également.
Solution?
Premier $p\in\mathbb P$. Laisser$a(k)$ être le plus petit $n_k$ Compte tenu du $k$e prime$p_k$. Nous avons:
$$a(k) = 2, 12, 26, 34, 50, 58, 74, 82, \dots$$
Est-il possible de trouver et de prouver une formule pour cette séquence?
J'ai remarqué que ce qui suit semble tenir jusqu'à présent: $a(1)=2,a(2)=12,a(k)=4p_k+6,k\ge 3$.
Ceci est dû aux factorisations non ordonnées suivantes:
$$\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}$$
Notez que les nombres premiers $p_k\ge 5$ suivez le schéma suivant:
$$ (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) $$
Cela nous donne une limite supérieure $a(k)\le 4p_k+6$ parce que le modèle est valable pour tous les nombres naturels.
L'égalité a été prouvée par calcul pour certains petits nombres premiers (comme vous pouvez le voir ci-dessus).
Pouvons-nous prouver que l'égalité est toujours valable? Ie pouvons-nous prouver$a(k)\ge 4p_k+6, k\ge 3$ ?
Autrement dit, il reste à prouver que toutes les factorisations non ordonnées de nombres de la forme
$$ p^{4p+5} $$
ont des sommes distinctes de facteurs pour tous les nombres premiers $p\ge 5$.
En d'autres termes, nous devons prouver que $\text{A001055}$$(p^{4p+5})$ $=$ $\text{A069016}$$(p^{4p+5})$.
Ou peut-être qu'il existe un prime $p$c'est un contre-exemple? C'est à dire$p_k : a(k)\lt 4p_k+6$ ?
Réponses
Remarque: ma solution est assez longue et contient de nombreux cas, certaines erreurs sont donc inévitables. Faites-moi savoir s'il y a quelque chose à expliquer.
Laisser $n$ être le plus petit nombre tel que $p^n$ont deux factorisations non ordonnées avec une somme égale de facteurs. Nous supposerons que$n \le 4p+5$ et dériver une contradiction.
Dénoter par $A=(p^{a_1})^{n_1}\dots (p^{a_k})^{n_k}$ et $B=(p^{b_1})^{m_1}\dots(p^{b_l})^{m_l}$ les deux factorisations non ordonnées, avec $a_1 > \dots > a_k$ et $b_1 > \dots > b_l$. Sans perte de généralité, supposons que$A$ a le pouvoir supérieur de $p$, c'est à dire que $a_1 \ge b_1$.
Observation 1: $\{a_1,\dots,a_k\} \cap \{b_1,\dots,b_l\}=\emptyset$.
C'est parce que si $a_i=b_j$ pour certains $i,j$, alors nous pouvons soustraire $p^{a_i}$ à partir des deux factorisations pour obtenir deux factorisations non ordonnées avec une somme égale pour $p^{n-a_i}$, contredisant la minimalité de $n$.
Observation 2: $a_1 \le 5$.
Cela vient de la considération des équations $$\begin{equation}\label{eqn1} b_1m_1+\dots+b_lm_l=n \qquad (1)\end{equation}$$ et $$ \begin{equation} m_1p^{b_1}+\dots+m_lp^{b_l}=n_1p^{a_1}+\dots+n_kp^{a_k}\qquad (2)\end{equation}$$ Si vous résolvez pour le maximum de la LHS de (2) donné (1) (et avec $m_j \in \mathbb{R}$ à la place), alors le maximum est atteint à $m_1=n/b_1$ et $m_j=0$ pour tous $j \ge 2$, où la valeur maximale est $\frac{n}{b_1}p^{b_1}$. D'autre part, le RHS de (2) donne la borne inférieure de$p^{a_1}$, donc nous devons avoir $$ \frac{n}{b_1} p^{b_1} \ge p^{a_1} \iff n \ge b_1 p^{a_1-b_1} .$$ Depuis $n \le 4p+5 \le p^2$ pour $p \ge 5$, nous avons ça $$ a_1-b_1=2, b_1=1 \qquad \text{or} \qquad a_1-b_1=1, b_1 \le 4$$ et dans les deux cas $a_1 \le 5$.
Nous considérons maintenant les différents cas $a_1 \in \{2,3,4,5\}$, avec $a_1=4$ étant le plus dur.
Si $a_1=2$, puis $b_1=1$ et nous obtenons deux factorisations $(p^2)^{n/2}$ et $p^n$. Ils n'ont pas une somme égale de facteurs pour$p>2$.
Si $a_1=3$, alors nous avons les options suivantes:
- $a_2=2$, $b_1=1$. Nous obtenons deux factorisations$(p^3)^{n_1}(p^2)^{n_2}$ et $p^n$. Ils n'ont pas de somme égale depuis$$np \le (4p+5)p < p^3$$ pour $p \ge 5$.
- $a_2=1$, $b_1=2$. Nous obtenons deux factorisations$(p^3)^{n_1}p^{n_2}$ et $(p^2)^{n/2}$. Depuis$$\frac{n}{2}p^2 \le \frac{4p+5}{2}p^2 < 3p^3$$ pour $p \ge 5$, nous avons ça $n_1 \in \{1,2\}$. Les deux valeurs ne conduisent pas à une somme égale.
- $b_1=2$, $b_2=1$. Nous obtenons deux factorisations$(p^3)^{n/3}$ et $(p^2)^{m_1}p^{m_2}$. ensuite$$ m_1 p^2+m_2p \le \frac{n}{2}p^2 < \frac{n}{3}p^3. $$
- $b_1=2$. On a$(p^3)^{n/3}$ et $(p^2)^{n/2}$, dont les sommes ne sont pas égales.
- $b_1=1$. On a$(p^3)^{n/3}$ et $p^n$, dont les sommes ne sont pas égales.
Si $a_1=5$, puis $b_1=4$comme nous l'avons expliqué ci-dessus. Par la même ligne d'argumentation, nous pouvons voir que$$ m_1p^4+\dots +m_l p^{b_l} < 2p^5 $$ pour tous les choix de $m_1,\dots,m_l$, alors $n_1=1$, et $$ m_1p^4+\dots +m_l p^{b_l} \ge p^5 $$ seulement quand $m_1 \ge p$. Par conséquent, nous avons cela$$ 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}).$$ En particulier, cela implique que $n \in \{4p, \dots, 4p+5\}$. Quelques vérifications supplémentaires montrent que pour de tels$n$, pas de factorisation de $p^{n-5}$ a la même somme de facteurs que toute factorisation de $p^{n-4p}$.
Si $a_1=4$, puis $b_1=3$ de l'argument de l'Observation 2. En utilisant le même argument que dans le cas ci-dessus, nous concluons que $n_1=1$ et $m_1 \ge p$. Par conséquent, nous avons$$ 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}).$$ Il reste à considérer les options suivantes pour $a_2,\dots,a_k$:
- $a_2=1$. Puis si$A=(p^4)p^{n-4}$ et $B=(p^3)^{m_1}(p^2)^{m_2}$ avoir une somme égale, nous devons avoir $$ (n-4)p=(m_1-p)p^3+m_2p^2 \ge \frac{n}{2} p^2,$$ ce qui est faux pour $p \ge 5$ et $n \le 4p+5$.
- $a_2=2$, $a_3=1$. ensuite$A=(p^4)(p^2)^{n_2}p^{n_3}$ et $B=(p^3)^{n/3}$. Si leurs sommes sont égales, alors$$ (n/3-p)p^3=n_2p^2+n_3p$$ donc en particulier $p \mid n_3$. Depuis$n_3 \le n-4 \le 4p+1$ nous devons avoir $n_3 \in \{p,2p,3p,4p\}$. Brancher chaque valeur de$n_3$ et $n_2=n-4-n_3$ dans l'équation, nous trouvons qu'aucune ne donne une valeur entière pour $n$.
- $a_2=2$. ensuite$A=(p^4)(p^2)^{(n-4)/2}$ et $B=(p^3)^{m_1}p^{m_2}$. Si leur somme est égale, alors$$\frac{n-4}{2}p^2=(m_1-p)p^3+m_2p$$ alors $p \mid m_2$, et similaire à ci-dessus, nous obtenons $m_2 \in \{p,2p,3p\}$. Encore une fois, en branchant chaque valeur de$m_2$ et $m_1=n-m_2$ dans l'équation, nous trouvons qu'aucune ne donne une valeur entière pour $n \le 4p+5$.