รากพิเศษจำนวนไม่ จำกัด ?

Question

คุณอาจ:
ลดจำนวนโดยหารด้วยจำนวนตัวประกอบเฉพาะนับจำนวนคูณ
ทำซ้ำกับผลลัพธ์เท่าที่คุณต้องการ

มีกำลังสองจำนวนไม่ จำกัด ที่สามารถลดลงถึงรากของมันได้หรือไม่?

ตัวอย่าง:
4 และ 16 ลดเป็นรูทในขั้นตอนเดียว
1600 ลดเป็น 40 ใน 2 ขั้นตอน

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

Answer 1

ผลลัพธ์บางส่วน:

วิธีแก้ปัญหาใด ๆ จะถูกกำหนดโดยตัวเลขอย่างเต็มที่ $n$ปัจจัยสำคัญของมัน อันที่จริงสมมติ$s$ เป็นวิธีแก้ปัญหาด้วย $n$ ปัจจัยสำคัญเริ่มต้นด้วยกำลังสอง $s^2$ ซึ่งมี $2n$ปัจจัยสำคัญ ตามคำจำกัดความของวิธีแก้ปัญหาเราสามารถแบ่งออกได้$s^2$ โดย $2n$. ถ้า$2n$ มี $k$ ปัจจัยสำคัญแล้ว $\frac{s^2}{2n}$ มี $n'=2n-k$ปัจจัยสำคัญ อีกครั้งเราอาจหารด้วย$n'$ และผลลัพธ์จะมี $n''=2n-k-k'$ ปัจจัยสำคัญที่ $k'$ คือจำนวนปัจจัยสำคัญของ $n'$และอื่น ๆ โปรดทราบว่าเราใช้เพียงจำนวนปัจจัยเฉพาะและสิ่งนี้ผ่านการสลายตัวของ$k,k',...$กำหนดว่าปัจจัยเหล่านี้คืออะไร ดังนั้นงานที่เทียบเท่ากับงานที่กำหนดคือ: ค้นหาตัวเลข$n$ เริ่มต้นที่ $2n$ และลบจำนวนปัจจัยสำคัญซ้ำ ๆ ในที่สุดเราก็โดน $n$. หากไม่มีสิ่งอื่นสิ่งนี้จะง่ายกว่ามากในการสำรวจด้วยคอมพิวเตอร์และดูเหมือนว่าจะมีโซลูชันมากมาย (~ 1500 สำหรับช่องสี่เหลี่ยมที่มีปัจจัยเฉพาะมากถึง 10,000 ตัว)

Answer 2

คำตอบบางส่วน:

สำหรับรูทที่น้อยกว่า 1 ล้านฉันพบช่องสี่เหลี่ยมต่อไปนี้ที่ใช้งานได้: $2^2, 4^2, 40^2, 80^2, 756^2, 1512^2, 42120^2, 130560^2$. ไม่ชัดเจนว่าลำดับนี้จะดำเนินต่อไปอย่างไม่มีกำหนดหรือไม่ กำลังสองต่อไปนี้มาถึงที่ 2:$2^2, 4^2, 80^2, 1008^2$.

Answer 3

อาร์กิวเมนต์น่าจะเป็น:

ใช้การลดลงของ Paul Panzer กับปัญหาต่อไปนี้:

สำหรับจำนวนเต็มบวก$n$, กำหนด $f(n)$ เป็น $n$ ลบจำนวนปัจจัยเฉพาะของ $n$เมื่อนับด้วยหลายหลาก มีมากมายเหลือหลาย$n$ ดังนั้น $n$ อยู่ในลำดับ $2n,f(2n),f(f(2n)),\dots$เหรอ?

กำหนด$\Omega(n)$ เป็นจำนวนปัจจัยสำคัญของ $n$นับด้วยความหลายหลาก เป็นที่ทราบกันดีว่าลำดับเฉลี่ยของ$\Omega(n)$ คือ $\log \log n$(ดูที่นี่ ) ดังนั้นการคาดเดาที่สมเหตุสมผลก็คือลำดับเริ่มต้นที่$2n$ ไม่ควรมีอคติเกี่ยวกับตัวเลขใด ๆ $n$ ซึ่งรวมถึงเนื่องจากควรใช้เวลาโดยเฉลี่ย $n/\log \log n$ การทำซ้ำของ $f$ เพื่อเข้าใกล้ $n$. เป็นผลให้เราควรคาดหวัง$n$ จะอยู่ในลำดับที่มีความน่าจะเป็นเกี่ยวกับ $1/\log \log n$และ $$\sum \frac{1}{\log \log n}$$แตกต่าง ดังนั้นควรมีจำนวนมากอย่างไม่สิ้นสุด$N$ ซึ่ง $N$ สามารถเข้าถึงได้จาก $N^2$.