ปริศนาเศษเสี้ยว
นี่คือปริศนาที่มีทั้งคอมพิวเตอร์ปริศนาแท็กและไม่มีคอมพิวเตอร์แท็ก
เรามีรายการเศษส่วนห้าส่วนต่อไปนี้:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
เริ่มต้นด้วยจำนวนเต็ม $x$เราดำเนินการดังต่อไปนี้: ในแต่ละขั้นตอนคูณ $x$ ตามเศษส่วนแรก (จากซ้ายไปขวา) ในรายการด้านบนที่ให้ผลลัพธ์จำนวนเต็ม
หากไม่มีเศษส่วนดังกล่าวในรายการขั้นตอนจะสิ้นสุดลงและค่าของ $x$ คือผลลัพธ์สุดท้าย
ตัวอย่าง: เริ่มต้นด้วย $x = 2$
ขั้นตอนแรก: คูณด้วย $21/2$, ซึ่งจะช่วยให้ $21$.
ขั้นตอนที่สอง: คูณด้วย $5/7$, ซึ่งจะช่วยให้ $15$.
ขั้นตอนที่สาม: คูณด้วย $11/5$, ซึ่งจะช่วยให้ $33$.
ขั้นตอนที่สี่: คูณด้วย $1/11$, ซึ่งจะช่วยให้ $3$.
เราเห็นว่า $x = 3$ เป็นผลลัพธ์สุดท้ายเป็นการคูณ $3$ โดยเศษส่วนใด ๆ จากห้าเศษส่วนจะให้ผลลัพธ์ที่ไม่ใช่จำนวนเต็ม
คำถาม: ถ้าเราเริ่มต้นด้วย $x = 2^{1234567}$แล้วสามหลักสุดท้ายของผลลัพธ์สุดท้ายจะเป็นอย่างไร?
สังเกต:
นี่เป็นที่รู้จักกันดีในระดับหนึ่งและฉันตั้งใจที่จะไม่เอ่ยชื่อเพราะมันควรจะง่ายพอที่จะไม่จำเป็นต้องมีความรู้เพิ่มเติมในการแก้ปัญหานี้
แน่นอนคุณสามารถระบุชื่อในคำตอบของคุณได้!
คำตอบ
เราสังเกตว่า
เศษส่วนเพียงตัวเดียวมีตัวส่วนเป็น 2
เนื่องจากเรามี x = 2 ^ 1234567 เราสามารถลองเสียบเข้าไปได้เราจะใช้การแยกตัวประกอบเฉพาะของตัวเลขเพื่อทำให้สิ่งต่างๆง่ายขึ้น
ก่อนอื่นเราคูณด้วย 21/2 ได้ 2 ^ 1234566 * 3 * 7 เนื่องจากเศษส่วนทั้งหมดก่อน 21/2 มีตัวประกอบเฉพาะอื่นที่ไม่ใช่ 2, 3 หรือ 7 เราจึงรู้ว่าฟังก์ชันจะคูณด้วย 21/2 ต่อไป จนไม่เหลือปัจจัย 2 สิ่งนี้ทำให้เรามี 3 ^ 1234567 * 7 ^ 1234567
ต่อไป,
เราคูณด้วย 5/7 เนื่องจากเศษส่วนแรกในรายการมีตัวส่วนเป็น 5 เราจึงรู้ว่าเมื่อใดก็ตามที่เราคูณด้วย 5/7 เราจะคูณด้วย 11/7 เป็นหลัก เราคูณและได้ 3 ^ 1234567 * 7 ^ 1234566 * 11 30/77 คือเศษส่วนต่อไปที่จะคูณด้วย เราลงท้ายด้วย 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565 การคูณด้วย 11/5 ทำให้เราได้ 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11
เราสังเกตเห็นว่า
เนื่องจากเรามี 7s จำนวนมากเราจะคูณด้วย 30/77 และ 11/5 ไปเรื่อย ๆ จนกว่าเราจะหมด 7 วินาที เราตระหนักดีว่าทุกครั้งที่จำนวน 7 ลดลง 1 วินาทีจำนวน 2 เพิ่มขึ้น 1 และจำนวน 3 เพิ่มขึ้น 1 เราเพิ่มจำนวนตัวประกอบของ 2 และ 3 โดย 1234565 และลบปัจจัยทั้งหมดของ 7 เพื่อให้ได้ 2 ^ 1234566 * 3 ^ 2469133 * 11 เราคูณด้วย 1/11 เพื่อลบตัวประกอบของ 11 และได้ 2 ^ 1234566 * 3 ^ 2469133
สิ่งนี้ทำให้เราอยู่ที่เดียวกับจุดเริ่มต้นยกเว้น
เรามีปัจจัย 3 จำนวนมากและจำนวนของปัจจัย 2 ลดลง 1
เนื่องจากไม่มีตัวส่วนใดที่มีปัจจัย 3
เราจะทำสิ่งเดียวกันกับที่ผ่านมาเพียงจำนวนครั้งที่น้อยลง การกำจัด 2s ทั้งหมดทำให้เราได้ 3 ^ 3703699 * 7 ^ 1234566 เราคูณด้วย 5/7 และ 11/5 เพื่อให้ได้ 3 ^ 3703699 * 7 ^ 1234565 * 11 เราบวกกลับของ 2 และ 3 และลบพลังทั้งหมดของ 7 และหนึ่งยกกำลัง 11 เพื่อให้ได้ 2 ^ 1234565 * 3 ^ 4938264
เราสังเกตเห็นว่า
ครั้งแรกที่พลังของ 3 เพิ่มขึ้น (1234567 + 1234566) และครั้งนี้พลังของ 3 เพิ่มขึ้น (1234566 + 1234565) ซึ่งหมายความว่าสำหรับยกกำลัง 2 มันจะเพิ่มพลัง 3 คูณ (2x-1) ซึ่งหมายความว่าพลังของ 3 จะเป็น$\sum_{i=1}^{1234567} 2i-1$ เราสามารถใช้คุณสมบัติการสรุปเพื่อให้ได้ $2*\sum_{i=1}^{1234567} i - 1234567$. เรารู้ว่าผลรวมของครั้งแรก$n$ จำนวนเต็มบวกคือ $\frac{n*(n+1)}{2}$ดังนั้น $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$ดังนั้น $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
เราเห็นว่า
คำตอบสุดท้ายคือ 3 ^ 1524155677489 และเนื่องจาก 3 หลักสุดท้ายของ 3 ^ x ซ้ำทุก ๆ 100 ครั้งเราต้องใช้กำลังของ 3 (mod 100) ซึ่งก็คือ 89
ซึ่งหมายความว่าเราต้องหา 3 หลักสุดท้ายของ
3 ^ 89.
เรารู้ว่า 3 หลักสุดท้ายของ
3 ^ 10 คือ 049,
ซึ่งหมายถึง 3 หลักสุดท้ายของ
3 ^ 20 เป็นเพียง 3 หลักสุดท้ายของ 49 ^ 2 หรือ 401
ซึ่งหมายถึง 3 หลักสุดท้ายของ
3 ^ 40 เป็นเพียง 3 หลักสุดท้ายของ 401 ^ 2 หรือ 801
ซึ่งหมายถึง 3 หลักสุดท้ายของ
3 ^ 80 เป็นเพียง 3 หลักสุดท้ายของ 801 ^ 2 หรือ 601
ซึ่งหมายถึง 3 หลักสุดท้ายของ
3 ^ 89 เป็นเพียง 3 หลักสุดท้ายของ 601 * (3 หลักสุดท้ายของ 3 ^ 9)
เรารู้ว่า 3 หลักสุดท้ายของ
3 ^ 9 เป็นเพียง 683 ซึ่งหมายถึง 3 หลักสุดท้ายของ 3 ^ 89 คือ 3 หลักสุดท้ายของ 601 * 683 ซึ่งก็คือ 483
ซึ่งหมายความว่าคำตอบสุดท้ายของเราคือ
483.
ข้อจำกัดความรับผิดชอบ: การคำนวณของฉันค่อนข้างยุ่งและการคำนวณผิดเพียงครั้งเดียวอาจทำให้คำตอบทั้งหมดผิด แต่วิธีแก้ปัญหาทั่วไปก็ยังคงถูกต้อง
ฉันไม่อยากถูกมองว่าเป็นคนหัวสูง แต่มีคุณค่าในการพิสูจน์ / คำนวณบางสิ่งในเชิงเศรษฐกิจ ลองทำครึ่งหลัง (คำนวณเลขสามหลักสุดท้ายของเลขจำนวนเต็มสูงมาก) ของการพิสูจน์ให้ถูกต้อง อันดับแรกเราได้มา$3^{100}\equiv 1 \mod 1000$ (โดยไม่ต้องใช้ออยเลอร์ $\phi$):
เริ่มจาก $3^5 = 243$ ลองยกกำลังห้าอีกสองครั้ง: เนื่องจากเราต้องการเพียงสามหลักสุดท้ายจึงค่อนข้างง่ายโดยใช้ทฤษฎีบททวินามเพราะเห็นได้ง่ายว่าคำที่สามและคำที่ตามมาทั้งหมดหารด้วย 1,000 จึงสามารถละเว้นได้ $3^{25} \equiv (240+3)^5 \equiv 243 + 5\times 81\times 240 + 10\times 27\times 240^2 + ... \equiv 443 \mod 1000$ $3^{125} \equiv (440+3)^5 \equiv 243 + 5\times 81\times 440 \equiv 443 \mod 1000$
นั่นคือค่าเดียวกันในทั้งสองกรณี เนื่องจาก 3 และ 1,000 เป็นสิ่งที่ค่อนข้างสำคัญเราจึงสรุปได้$3^{100} \equiv 1 \mod 1000$
ด้วยการจัดตั้งขึ้นทำให้เราพบวิธีการคำนวณที่ไม่เจ็บปวด
$3^{89}$. โดยสิ่งที่เราเพิ่งแสดงให้เห็นว่าเรามี$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. ตอนนี้มันเป็นเรื่องง่ายที่จะคาดเดาว่าผกผันของ$3$ โมดูโล $1000$ คือ $-333$นั่นคือของ $9$ คือ $-111$. ดังนั้น:$3^{89}\equiv 3^{-11} \equiv 333\times 111^5 \equiv 333\times \left ( 1 + 5 \times 110 \right ) \equiv 333 \times 551 \equiv 333 + 650 + 500 \equiv 483 \mod 1000$