Potenza minima di un numero primo le cui fattorizzazioni non hanno somme distinte di fattori
Problema
Dato un numero primo $p$, trova il più piccolo $n$ tale che alcune fattorizzazioni non ordinate di $p^n$ avere la stessa somma di fattori.
Le fattorizzazioni non ordinate sono fattorizzazioni in cui l'ordine dei fattori è irrilevante e non includono il fattore banale $1$. Notare che$n\gt 1$ per tutti i numeri primi $p$ perché i numeri primi hanno una sola fattorizzazione non ordinata.
Esempi
Prime $p=2$. È banale che$n=2$ per $p=2$ perché $2+2=2\cdot 2$. Cioè, fattorizzazioni non ordinate di$2^2$ siamo $4$ e $2\cdot 2$ed entrambi hanno la stessa somma di fattori $4 = 2+2$.
Prime $p=3$. Ma,$n=2$ non è una soluzione per $p=3$ perché $9\ne 3+3$. Nemmeno lo è$n=3$ perché $27\ne 3+9 \ne 3+3+3$. Nemmeno lo è$n=4$ perché $81\ne 27 + 3\ne 9 + 9\ne 9 + 3 + 3\ne 3 + 3 + 3 + 3$. Alla fine, lo troviamo$n=12$ è il più piccolo che si adatta, perché allora esistono le seguenti somme duplicate di fattori:
$$\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}$$
Notare che if $p^{n}$ o qualsiasi numero in generale soddisfa questa proprietà, allora anche tutti i multipli di quel numero la soddisfano.
Soluzione?
Prime $p\in\mathbb P$. Permettere$a(k)$ essere il più piccolo tale $n_k$ dato che $k$esimo primo$p_k$. Abbiamo:
$$a(k) = 2, 12, 26, 34, 50, 58, 74, 82, \dots$$
È possibile trovare e provare una formula per questa sequenza?
Ho notato che quanto segue sembra valere finora: $a(1)=2,a(2)=12,a(k)=4p_k+6,k\ge 3$.
Ciò è dovuto alle seguenti fattorizzazioni non ordinate:
$$\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}$$
Nota che i numeri primi $p_k\ge 5$ segui lo schema seguente:
$$ (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) $$
Questo ci dà un limite superiore $a(k)\le 4p_k+6$ perché il modello vale per tutti i numeri naturali.
L'uguaglianza è stata dimostrata computazionalmente per alcuni piccoli numeri primi (come puoi vedere sopra).
Possiamo dimostrare che l'uguaglianza vale sempre? Cioè possiamo dimostrarlo$a(k)\ge 4p_k+6, k\ge 3$ ?
Cioè, resta da dimostrare che tutte le fattorizzazioni non ordinate dei numeri della forma
$$ p^{4p+5} $$
hanno somme distinte di fattori per tutti i numeri primi $p\ge 5$.
In altre parole, dobbiamo dimostrarlo $\text{A001055}$$(p^{4p+5})$ $=$ $\text{A069016}$$(p^{4p+5})$.
O forse esiste un numero primo $p$questo è un controesempio? Cioè$p_k : a(k)\lt 4p_k+6$ ?
Risposte
Nota: la mia soluzione è piuttosto lunga e contiene molti casi, quindi alcuni errori sono inevitabili. Fammi sapere se c'è qualcosa che deve essere spiegato.
Permettere $n$ essere il numero più piccolo tale che $p^n$hanno due fattorizzazioni non ordinate con uguale somma di fattori. Lo assumeremo$n \le 4p+5$ e derivare una contraddizione.
Denota da $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}$ le due fattorizzazioni non ordinate, con $a_1 > \dots > a_k$ e $b_1 > \dots > b_l$. Senza perdere la generalità, assumilo$A$ ha il potere più alto di $p$, cioè quello $a_1 \ge b_1$.
Osservazione 1: $\{a_1,\dots,a_k\} \cap \{b_1,\dots,b_l\}=\emptyset$.
Questo perché se $a_i=b_j$ per alcuni $i,j$, quindi possiamo sottrarre $p^{a_i}$ da entrambe le fattorizzazioni per ottenere due fattorizzazioni non ordinate con uguale somma per $p^{n-a_i}$, contraddicendo la minimalità di $n$.
Osservazione 2: $a_1 \le 5$.
Questo deriva dal considerare le equazioni $$\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 risolvi per il massimo del LHS di (2) dato (1) (e con $m_j \in \mathbb{R}$ invece), viene raggiunto il massimo a $m_1=n/b_1$ e $m_j=0$ per tutti $j \ge 2$, dove è il valore massimo $\frac{n}{b_1}p^{b_1}$. D'altra parte, l'RHS di (2) fornisce il limite inferiore di$p^{a_1}$, quindi dobbiamo avere $$ \frac{n}{b_1} p^{b_1} \ge p^{a_1} \iff n \ge b_1 p^{a_1-b_1} .$$ Da $n \le 4p+5 \le p^2$ per $p \ge 5$, ce l'abbiamo $$ a_1-b_1=2, b_1=1 \qquad \text{or} \qquad a_1-b_1=1, b_1 \le 4$$ e in entrambi i casi $a_1 \le 5$.
Consideriamo ora i vari casi $a_1 \in \{2,3,4,5\}$, con $a_1=4$ essere il più difficile.
Se $a_1=2$, poi $b_1=1$ e otteniamo due fattorizzazioni $(p^2)^{n/2}$ e $p^n$. Non hanno la stessa somma di fattori per$p>2$.
Se $a_1=3$, quindi abbiamo le seguenti opzioni:
- $a_2=2$, $b_1=1$. Otteniamo due fattorizzazioni$(p^3)^{n_1}(p^2)^{n_2}$ e $p^n$. Da allora non hanno la stessa somma$$np \le (4p+5)p < p^3$$ per $p \ge 5$.
- $a_2=1$, $b_1=2$. Otteniamo due fattorizzazioni$(p^3)^{n_1}p^{n_2}$ e $(p^2)^{n/2}$. Da$$\frac{n}{2}p^2 \le \frac{4p+5}{2}p^2 < 3p^3$$ per $p \ge 5$, ce l'abbiamo $n_1 \in \{1,2\}$. Entrambi i valori non portano a una somma uguale.
- $b_1=2$, $b_2=1$. Otteniamo due fattorizzazioni$(p^3)^{n/3}$ e $(p^2)^{m_1}p^{m_2}$. Poi$$ m_1 p^2+m_2p \le \frac{n}{2}p^2 < \frac{n}{3}p^3. $$
- $b_1=2$. Noi abbiamo$(p^3)^{n/3}$ e $(p^2)^{n/2}$, le cui somme non sono uguali.
- $b_1=1$. Noi abbiamo$(p^3)^{n/3}$ e $p^n$, le cui somme non sono uguali.
Se $a_1=5$, poi $b_1=4$come abbiamo affermato sopra. Dalla stessa linea di argomentazione, possiamo vederlo$$ m_1p^4+\dots +m_l p^{b_l} < 2p^5 $$ per tutte le scelte di $m_1,\dots,m_l$, così $n_1=1$, e $$ m_1p^4+\dots +m_l p^{b_l} \ge p^5 $$ solo quando $m_1 \ge p$. Pertanto, abbiamo quello$$ 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}).$$ In particolare, ciò implica che $n \in \{4p, \dots, 4p+5\}$. Qualche altro controllo mostra che per tale$n$, nessuna fattorizzazione di $p^{n-5}$ ha la stessa somma di fattori di qualsiasi fattorizzazione di $p^{n-4p}$.
Se $a_1=4$, poi $b_1=3$ dall'argomento dell'osservazione 2. Usando lo stesso argomento del caso precedente, concludiamo che $n_1=1$ e $m_1 \ge p$. Pertanto, abbiamo$$ 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 da considerare le seguenti opzioni per $a_2,\dots,a_k$:
- $a_2=1$. Allora se$A=(p^4)p^{n-4}$ e $B=(p^3)^{m_1}(p^2)^{m_2}$ avere uguale somma, dobbiamo avere $$ (n-4)p=(m_1-p)p^3+m_2p^2 \ge \frac{n}{2} p^2,$$ che è falso per $p \ge 5$ e $n \le 4p+5$.
- $a_2=2$, $a_3=1$. Poi$A=(p^4)(p^2)^{n_2}p^{n_3}$ e $B=(p^3)^{n/3}$. Se le loro somme sono uguali, allora$$ (n/3-p)p^3=n_2p^2+n_3p$$ così in particolare $p \mid n_3$. Da$n_3 \le n-4 \le 4p+1$ noi dobbiamo avere $n_3 \in \{p,2p,3p,4p\}$. Collegando ogni valore di$n_3$ e $n_2=n-4-n_3$ nell'equazione, troviamo che nessuno restituisce un valore intero per $n$.
- $a_2=2$. Poi$A=(p^4)(p^2)^{(n-4)/2}$ e $B=(p^3)^{m_1}p^{m_2}$. Se la loro somma è uguale, allora$$\frac{n-4}{2}p^2=(m_1-p)p^3+m_2p$$ così $p \mid m_2$, e simile a sopra otteniamo $m_2 \in \{p,2p,3p\}$. Ancora una volta, collegando ogni valore di$m_2$ e $m_1=n-m_2$ nell'equazione, troviamo che nessuno restituisce un valore intero per $n \le 4p+5$.