พลังที่เล็กที่สุดของไพรม์ซึ่งการแยกตัวประกอบไม่มีผลรวมของปัจจัยที่แตกต่างกัน

Question

ปัญหา

กำหนดให้เป็นนายก $p$ค้นหาที่เล็กที่สุด $n$ เช่นการแยกตัวประกอบที่ไม่ได้เรียงลำดับของ $p^n$ มีจำนวนปัจจัยเท่ากัน

การแยกตัวประกอบแบบไม่เรียงลำดับคือการแยกตัวประกอบที่ลำดับของปัจจัยไม่เกี่ยวข้องและไม่รวมปัจจัยเล็กน้อย $1$. สังเกตว่า$n\gt 1$ สำหรับทุกช่วงเวลา $p$ เนื่องจากจำนวนเฉพาะมีการแยกตัวประกอบที่ไม่เรียงลำดับเพียงตัวเดียว

ตัวอย่าง

นายก $p=2$. มันเป็นเรื่องเล็กน้อยที่$n=2$ สำหรับ $p=2$ เพราะ $2+2=2\cdot 2$. นั่นคือการแยกตัวประกอบแบบไม่เรียงลำดับของ$2^2$ คือ $4$ และ $2\cdot 2$และทั้งสองมีปัจจัยรวมเดียวกัน $4 = 2+2$.

นายก $p=3$. แต่,$n=2$ ไม่ใช่ทางออกสำหรับ $p=3$ เพราะ $9\ne 3+3$. ไม่ใช่$n=3$ เพราะ $27\ne 3+9 \ne 3+3+3$. ไม่ใช่$n=4$ เพราะ $81\ne 27 + 3\ne 9 + 9\ne 9 + 3 + 3\ne 3 + 3 + 3 + 3$. ในที่สุดเราก็พบว่า$n=12$ เป็นปัจจัยที่เล็กที่สุดที่เหมาะสมเนื่องจากมีผลรวมของปัจจัยที่ซ้ำกันดังต่อไปนี้:

$$\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}$$

สังเกตว่าถ้า $p^{n}$ หรือตัวเลขใด ๆ โดยทั่วไปตรงตามคุณสมบัตินี้แล้วผลคูณทั้งหมดของจำนวนนั้นก็เป็นไปตามนั้นด้วย

วิธีการแก้?

นายก $p\in\mathbb P$. ปล่อย$a(k)$ มีขนาดเล็กที่สุด $n_k$ ได้รับ $k$วันสำคัญ$p_k$. เรามี:

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

เป็นไปได้ไหมที่จะค้นหาและพิสูจน์สูตรสำหรับลำดับนี้

ฉันสังเกตว่าสิ่งต่อไปนี้ดูเหมือนจะค้างอยู่: $a(1)=2,a(2)=12,a(k)=4p_k+6,k\ge 3$.

นี่เป็นเพราะการแยกตัวประกอบที่ไม่เรียงลำดับดังต่อไปนี้:

$$\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}$$

สังเกตว่าช่วงเวลา $p_k\ge 5$ ทำตามรูปแบบต่อไปนี้:

$$ (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) $$

สิ่งนี้ทำให้เรามีขอบเขตบน $a(k)\le 4p_k+6$ เนื่องจากรูปแบบมีไว้สำหรับจำนวนธรรมชาติทั้งหมด

ความเท่าเทียมกันได้รับการพิสูจน์ทางคำนวณสำหรับช่วงเวลาเล็ก ๆ (ดังที่คุณเห็นด้านบน)

เราพิสูจน์ได้หรือไม่ว่าความเท่าเทียมกันนั้นมีอยู่เสมอ? คือเราพิสูจน์ได้$a(k)\ge 4p_k+6, k\ge 3$ เหรอ?

นั่นคือมันถูกทิ้งไว้เพื่อพิสูจน์ว่าการแยกตัวประกอบของตัวเลขในรูปแบบไม่เรียงลำดับทั้งหมด

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

มีผลรวมของปัจจัยที่แตกต่างกันสำหรับทุกช่วงเวลา $p\ge 5$.

กล่าวอีกนัยหนึ่งเราจำเป็นต้องพิสูจน์สิ่งนั้น $\text{A001055}$$(p^{4p+5})$ $=$ $\text{A069016}$$(p^{4p+5})$.

หรืออาจจะมีนายก $p$นั่นคือตัวอย่างตอบโต้? ได้แก่$p_k : a(k)\lt 4p_k+6$ เหรอ?

Answer 1

หมายเหตุ:วิธีแก้ปัญหาของฉันค่อนข้างยาวและมีหลายกรณีดังนั้นข้อผิดพลาดบางอย่างจึงหลีกเลี่ยงไม่ได้ โปรดแจ้งให้เราทราบหากมีสิ่งใดที่ต้องการคำอธิบาย

---

ปล่อย $n$ เป็นตัวเลขที่น้อยที่สุด $p^n$มีการแยกตัวประกอบที่ไม่เรียงลำดับสองตัวโดยมีผลรวมเท่ากัน เราจะถือว่า$n \le 4p+5$ และได้รับความขัดแย้ง

แสดงโดย $A=(p^{a_1})^{n_1}\dots (p^{a_k})^{n_k}$ และ $B=(p^{b_1})^{m_1}\dots(p^{b_l})^{m_l}$ การแยกตัวประกอบที่ไม่เรียงลำดับทั้งสองด้วย $a_1 > \dots > a_k$ และ $b_1 > \dots > b_l$. สมมติว่าไม่มีการสูญเสียทั่วไป$A$ มีอำนาจสูงกว่าของ $p$นั่นคือสิ่งนั้น $a_1 \ge b_1$.

การสังเกต 1: $\{a_1,\dots,a_k\} \cap \{b_1,\dots,b_l\}=\emptyset$.

เพราะถ้า $a_i=b_j$ สำหรับบางคน $i,j$จากนั้นเราก็ลบได้ $p^{a_i}$ จากการแยกตัวประกอบทั้งสองเพื่อให้ได้ตัวประกอบที่ไม่เรียงลำดับสองตัวที่มีผลรวมเท่ากันสำหรับ $p^{n-a_i}$, ขัดแย้งกับความน้อยที่สุดของ $n$.

การสังเกต 2: $a_1 \le 5$.

สิ่งนี้มาจากการพิจารณาสมการ $$\begin{equation}\label{eqn1} b_1m_1+\dots+b_lm_l=n \qquad (1)\end{equation}$$ และ $$ \begin{equation} m_1p^{b_1}+\dots+m_lp^{b_l}=n_1p^{a_1}+\dots+n_kp^{a_k}\qquad (2)\end{equation}$$ หากคุณแก้ค่า LHS สูงสุดของ (2) ที่กำหนด (1) (และด้วย $m_j \in \mathbb{R}$ แทน) จากนั้นบรรลุสูงสุดที่ $m_1=n/b_1$ และ $m_j=0$ เพื่อทุกสิ่ง $j \ge 2$โดยที่ค่าสูงสุดคือ $\frac{n}{b_1}p^{b_1}$. ในทางกลับกัน RHS ของ (2) ให้ขอบเขตล่างของ$p^{a_1}$ดังนั้นเราจึงต้องมี $$ \frac{n}{b_1} p^{b_1} \ge p^{a_1} \iff n \ge b_1 p^{a_1-b_1} .$$ ตั้งแต่ $n \le 4p+5 \le p^2$ สำหรับ $p \ge 5$เรามีสิ่งนั้น $$ a_1-b_1=2, b_1=1 \qquad \text{or} \qquad a_1-b_1=1, b_1 \le 4$$ และในทั้งสองกรณี $a_1 \le 5$.

ตอนนี้เราพิจารณาคดีต่างๆ $a_1 \in \{2,3,4,5\}$กับ $a_1=4$ เป็นสิ่งที่ยากที่สุด

1. ถ้า $a_1=2$แล้ว $b_1=1$ และเราได้ตัวประกอบสองตัว $(p^2)^{n/2}$ และ $p^n$. พวกเขามีผลรวมของปัจจัยไม่เท่ากัน$p>2$.

2. ถ้า $a_1=3$จากนั้นเรามีตัวเลือกดังต่อไปนี้:

   • $a_2=2$, $b_1=1$. เราได้รับสองปัจจัย$(p^3)^{n_1}(p^2)^{n_2}$ และ $p^n$. พวกเขามีผลรวมไม่เท่ากันตั้งแต่นั้นมา$$np \le (4p+5)p < p^3$$ สำหรับ $p \ge 5$.
   • $a_2=1$, $b_1=2$. เราได้รับสองปัจจัย$(p^3)^{n_1}p^{n_2}$ และ $(p^2)^{n/2}$. ตั้งแต่$$\frac{n}{2}p^2 \le \frac{4p+5}{2}p^2 < 3p^3$$ สำหรับ $p \ge 5$เรามีสิ่งนั้น $n_1 \in \{1,2\}$. ค่าใดค่าหนึ่งไม่ได้นำไปสู่ผลรวมที่เท่ากัน
   • $b_1=2$, $b_2=1$. เราได้รับสองปัจจัย$(p^3)^{n/3}$ และ $(p^2)^{m_1}p^{m_2}$. แล้ว$$ m_1 p^2+m_2p \le \frac{n}{2}p^2 < \frac{n}{3}p^3. $$
   • $b_1=2$. เราได้รับ$(p^3)^{n/3}$ และ $(p^2)^{n/2}$ซึ่งผลรวมไม่เท่ากัน
   • $b_1=1$. เราได้รับ$(p^3)^{n/3}$ และ $p^n$ซึ่งผลรวมไม่เท่ากัน

3. ถ้า $a_1=5$แล้ว $b_1=4$ตามที่เราได้โต้แย้งไว้ข้างต้น ในแนวเดียวกันเราจะเห็นว่า$$ m_1p^4+\dots +m_l p^{b_l} < 2p^5 $$ สำหรับตัวเลือกทั้งหมดของ $m_1,\dots,m_l$ดังนั้น $n_1=1$และ $$ m_1p^4+\dots +m_l p^{b_l} \ge p^5 $$ เมื่อ $m_1 \ge p$. ดังนั้นเราจึงมีสิ่งนั้น$$ 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}).$$ โดยเฉพาะอย่างยิ่งโดยนัยนี้ $n \in \{4p, \dots, 4p+5\}$. การตรวจสอบเพิ่มเติมบางอย่างแสดงให้เห็นว่าสำหรับสิ่งนั้น$n$ไม่มีการแยกตัวประกอบของ $p^{n-5}$ มีผลรวมของปัจจัยเดียวกับการแยกตัวประกอบของ $p^{n-4p}$.

4. ถ้า $a_1=4$แล้ว $b_1=3$ จากอาร์กิวเมนต์ในการสังเกตการณ์ 2 โดยใช้อาร์กิวเมนต์เดียวกับในกรณีข้างต้นเราสรุปได้ว่า $n_1=1$ และ $m_1 \ge p$. ดังนั้นเราจึงมี$$ 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}).$$ ยังคงต้องพิจารณาตัวเลือกต่อไปนี้สำหรับ $a_2,\dots,a_k$:

   • $a_2=1$. แล้วถ้า$A=(p^4)p^{n-4}$ และ $B=(p^3)^{m_1}(p^2)^{m_2}$ มีผลรวมเท่ากันเราต้องมี $$ (n-4)p=(m_1-p)p^3+m_2p^2 \ge \frac{n}{2} p^2,$$ ซึ่งเป็นเท็จสำหรับ $p \ge 5$ และ $n \le 4p+5$.
   • $a_2=2$, $a_3=1$. แล้ว$A=(p^4)(p^2)^{n_2}p^{n_3}$ และ $B=(p^3)^{n/3}$. หากผลรวมของพวกเขาเท่ากันแล้ว$$ (n/3-p)p^3=n_2p^2+n_3p$$ โดยเฉพาะอย่างยิ่ง $p \mid n_3$. ตั้งแต่$n_3 \le n-4 \le 4p+1$ เราต้องมี $n_3 \in \{p,2p,3p,4p\}$. การเสียบแต่ละค่าของ$n_3$ และ $n_2=n-4-n_3$ ในสมการเราพบว่าไม่มีใครให้ค่าจำนวนเต็มสำหรับ $n$.
   • $a_2=2$. แล้ว$A=(p^4)(p^2)^{(n-4)/2}$ และ $B=(p^3)^{m_1}p^{m_2}$. ถ้าผลรวมเท่ากันแล้ว$$\frac{n-4}{2}p^2=(m_1-p)p^3+m_2p$$ ดังนั้น $p \mid m_2$และคล้ายกับด้านบนที่เราได้รับ $m_2 \in \{p,2p,3p\}$. อีกครั้งเสียบแต่ละค่าของ$m_2$ และ $m_1=n-m_2$ ในสมการเราพบว่าไม่มีใครให้ค่าจำนวนเต็มสำหรับ $n \le 4p+5$.