ฝึกวิเคราะห์ algorithm ด้วยตะแกรงร่อน Palindrome (2)

จากโจทย์คราวก่อน ฝึกวิเคราะห์ algorithm ด้วยตะแกรงร่อน Palindrome (1) ผมตั้งเป็นแบบคำถามปลายเปิดว่า

หากจะสร้างเลขพาลินโดรมที่มีค่ามากที่สุดจากเลขไม่เกินสี่หลักจำนวนสองชุดคูณกัน จะมี algorithm แบบไหน ที่คูณกันน้อยครั้งที่สุด 

เพื่อให้เห็นตัวเลขได้ถนัด จำนวนครั้งที่คูณกัน ผมขอใส่ log ฐาน 10 จะได้ไม่ดูรุงรัง แล้วเรียกตัวเลขที่ได้ว่า ความอืด

กรณีนี้ ถ้าทำแบบหักโหม (brute force) ก็แค่จับคู่พบกันหมด ตั้งแต่ 1 ถึง 9999 คูณกันเองแบบพบกันหมด ค่าความอืดทางทฤษฎีกรณีนี้ จะอยู่ประมาณ 8.0 

ลองมาดูว่า ผมแก้ปัญหาอย่างไร

ตรงนี้ออกตัวไว้ก่อนว่า อาจไม่ใช่วิธีดีที่สุด และผมยังรอวิธีดีที่สุดนั้นอยู่จากคุณผู้อ่้าน อยากเห็น ให้เป็นบุญตา

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

 

ผมเริ่มจากการทึกทัก (ตั้ง assumption) ก่อน

ผมทึกทักว่า เลข palindrome ที่เกิดขึ้น ควรจะขึ้นต้นด้วย 9 และลงท้ายด้วย 9 เพื่อจะได้แน่ใจว่า มันโตที่สุดจริง

 

ผมหักล้างข้อทึกทักอย่างไร ?

ข้อทึกทัก อาจไม่จริง จึงต้องหักล้างก่อน

คือตัวเลขเยอะที่สุด อาจไม่ได้ขึ้นต้นด้วย 9 ก็ได้

หักล้างแบบดีที่สุด คือพิสูจน์อย่างไม่มีข้อสงสัย

แบบที่ดีรองลงมา (เกรดต่ำ) คือ อนุมานว่าน่าจะเป็นทำนองนี้

ในกรณีนี้ ผมหักล้างแบบเกรดต่ำ เพราะใช้วิธีอนุมาน

ข้อหักล้างผมคือ เลข palindrome ที่เกิดขึ้น น่าจะอยู่ในโซน  9x  xxx xx9 เมื่อ x เป็นตัวเลขอะไรก็ได้ เพราะในโซนนั้น ไม่น่าจะมีเลข prime number มาก

เอ๊ะ prime number มาเกี่ยวอะไร ?

เรารู้ว่า prime number จะไม่สามารถแยก factor ได้

เรามองหา palindrome ที่เกิดจากผลคูณ ดังนั้น เท่ากับว่า เรากำลังหลีกหนี prime number

ในเมื่อ prime number ไม่น่าจะมีมาก (ดูพิสูจน์ข้างล่าง ซึ่งระบุว่า จะมี prime number ปนมาเพียง 5 %)

ดังนั้น ค่าตั้งแต่ 90 000 000 ถึง 99 999 999 จึงน่าจะมี palindrome ที่แยกตัวประกอบได้มากเหลือเฟือในช่วงดังกล่าวจริง

หรืออาจพูดอีกอย่างว่า ผมเชื่อมั่นว่า ต้องมีเลข palindrome ที่มีค่าระหว่าง 90 000 009 ถึง 99 999 999 อยู่ ที่เกิดจากผลคูณของเลขสองตัว ค่อนข้างแน่

ข้อพิสูจน์ว่า prime number ไม่น่าจะมีมากในช่วง 90 000 009 - 99 999 999

ใน prime number theorem จาก wiki ให้ข้อมูลว่า จำนวน prime number ที่น้อยกว่า x ใด ๆ จะมีจำนวนประมาณ x/ln(x) ตัว

ดังนั้น จำนวน prime number ระหว่าง 90000009 ถึง 99999999 ควรจะมีราว ๆ 99999999/ln(99999999)-90000009/ln(90000009) หรือ 514761 ตัว หรือคิดเป็นความเป็นไปได้เพียง 5.1 % ที่หยิบตัวเลขใดตัวเลขหนึ่งมา แล้วเจอว่า เอ๊ะ ตัวนี้เป็น prime นะ แยกตัวประกอบไม่ได้

ในช่วง ระหว่าง 90000009 ถึง 99999999  ผมลองนับ (โดยการสังเกต) ได้ข้อสรุปว่าต้องมี palindrome 1000 ตัว ดังนั้น โอกาสที่จะดวงกุด มีแต่เลข prime ทั้ง 1000 ตัว มีความเป็นไปได้เพียง 0.0513 ยกกำลัง 1000 ซึ่งน้อยมั่กๆ  เป็นศูนย์ไปซะเถอะ !

เพราะถ้าดวงกุด มีแต่เลข prime number หมดในช่วงดังกล่าว ผลพลอยได้ของความล้มเหลวกรณีนี้คือ การค้นพบสูตรในการ generate prime number ซึ่งสำคัญกว่าโจทย์ข้อนี้หลายขุม

ดังนั้น ข้อทึกทัก จึงน่าจะเป็นจริงแบบ ฟันธง (โดยใช้แนวคิดทางสถิติ) แม้จะไม่สามารถพิสูจน์อย่างเป็นทางการได้ก็ตาม

 

นำข้อทึกทักไปใช้อย่างไร ?

เพื่อความเร้าใจ เก็บไปเฉลยต่อตอนหน้าครับ