Google Treasure Hunt 2008 Question 4 (prime)

ตอนจบของการล่าสมบัติ คือการหาจำนวนเฉพาะที่น้อยที่สุดที่เป็นผลรวมของจำนวนเฉพาะที่ต่อเนื่องกันตามจำนวนที่ระบุเท่ากัน โดยของผมได้ 15, 31, 127, 515 จำนวน จะบอกว่าเห็นแว๊บแรก มองเห็นว่ามันคือ 2^4-1, 2^5-1, 2^7-1, 2^9+3 ทำให้อดคิดไม่ได้ว่ามันเกี่ยวอะไรกันหรือเปล่า จริง ๆ ไม่ได้เกี่ยวอะไร (มั๊ง)

แต่ข้อนี้ผมทำได้ช้ามาก ๆ เพราะตอนแรกอ่านโจทย์ไม่ละเอียดเอง ไม่ทันสังเกตว่ามันต้องการแค่จำนวนเฉพาะที่ต่อเนื่องกัน ผมนึกว่าจำนวนเฉพาะใด ๆ ก็ได้มาบวกกัน ทำให้โจทย์ยากขึ้นเยอะมาก ซึ่งจริง ๆ เขียนโค้ดจนได้โค้ดที่พร้อมรันแล้ว ซึ่งประเมินแล้วว่ารันนานแน่ ๆ เพราะซับซ้อนมาก ขนาด list ที่ใช้ก็ใหญ่มาก ต้องเก็บข้อมูลเป็น bit เพื่อลดขนาดข้อมูลกันเลยทีเดียว อัพโหลดโค้ด และ text file ที่เก็บจำนวนเฉพาะที่คำนวณไว้แล้ว 6 แสนตัวไปไว้เครื่อง server Linux 64bit ram 8GB รันไปได้หน่อยนึง กะว่าคงต้องรอสักอาทิตย์จึงจะเห็นผล จนแว๊บเห็นคุณ @macroart tweet บอกว่าเขียนบล็อกเรื่องนี้ไปแล้ว เลยเข้าไปอ่านดูถึงรู้ว่าพลาดไปแล้ว

สรุปว่าเขียนใหม่ครับ เหลือโค้ดไว้ใช้เฉพาะตัวโหลด prime ใน file มาเป็น list ที่เหลือเขียนใหม่เลย ลองแบบยังไม่อ่านแนวทางของคุณ @macroart แต่สุดท้ายได้แนวคิดคล้าย ๆ กัน คือผมมองเป็นบล็อก เหมือนรถไฟ 4 ขบวนค่อยวิ่งออกจากต้นทาง โดยตอนแรกหาผลรวมเท่าจำนวนที่ระบุของแต่ละขบวนก่อน แล้วค่อย ๆ ขยับรถไฟไปทีละหน่อย โดยลบเลขตัวน้อยท้ายขบวนออก บวกด้วยตัวถัดไปที่อยู่หัวขบวน ค่อย ๆ เทียบค่าทีละคู่ ดังนั้นคู่ที่ 1 กับ 2 จะเริ่มวิ่งก่อน จนกว่าจะได้ผลรวมเท่ากัน ค่อยเทียบกับขบวนที่ 3 และเมื่อทั้ง 3 ขบวนมีผลรวมเท่ากัน ค่อยไปเทียบกับขบวนที่ 4 จนกว่าจะเท่ากันหมด

รอบแรกมีบั๊กนิดหน่อย เพราะการอ้างตำแหน่ง list หัวขบวนผิด พอแก้แล้วก็รันไม่กี่วินาทีก็ได้คำตอบ ช้ากว่าของ @macroart เพราะรถไฟของแกมีการเร่งเครื่องได้ด้วยถ้าผลรวมต่างกันมาก ๆ ตรงนี้ไม่ได้คิด

ผลลัพธ์ที่ได้คือ

ANSWER = 7448179
[41266, 21229, 5870, 1441] [7448179, 7448179, 7448179, 7448179]
0 : 496459 496471 496477 496481 496487 496493 496499 496511 496549 496579 496583 496609 496631 496669 496681
1 : 240073 240089 240101 240109 240113 240131 240139 240151 240169 240173 240197 240203 240209 240257 240259 240263 240271 240283 240287 240319 240341 240347 240349 240353 240371 240379 240421 240433 240437 240473 240479
2 : 57973 57977 57991 58013 58027 58031 58043 58049 58057 58061 58067 58073 58099 58109 58111 58129 58147 58151 58153 58169 58171 58189 58193 58199 58207 58211 58217 58229 58231 58237 58243 58271 58309 58313 58321 58337 58363 58367 58369 58379 58391 58393 58403 58411 58417 58427 58439 58441 58451 58453 58477 58481 58511 58537 58543 58549 58567 58573 58579 58601 58603 58613 58631 58657 58661 58679 58687 58693 58699 58711 58727 58733 58741 58757 58763 58771 58787 58789 58831 58889 58897 58901 58907 58909 58913 58921 58937 58943 58963 58967 58979 58991 58997 59009 59011 59021 59023 59029 59051 59053 59063 59069 59077 59083 59093 59107 59113 59119 59123 59141 59149 59159 59167 59183 59197 59207 59209 59219 59221 59233 59239 59243 59263 59273 59281 59333 59341
3 : 12041 12043 12049 12071 12073 12097 12101 12107 12109 12113 12119 12143 12149 12157 12161 12163 12197 12203 12211 12227 12239 12241 12251 12253 12263 12269 12277 12281 12289 12301 12323 12329 12343 12347 12373 12377 12379 12391 12401 12409 12413 12421 12433 12437 12451 12457 12473 12479 12487 12491 12497 12503 12511 12517 12527 12539 12541 12547 12553 12569 12577 12583 12589 12601 12611 12613 12619 12637 12641 12647 12653 12659 12671 12689 12697 12703 12713 12721 12739 12743 12757 12763 12781 12791 12799 12809 12821 12823 12829 12841 12853 12889 12893 12899 12907 12911 12917 12919 12923 12941 12953 12959 12967 12973 12979 12983 13001 13003 13007 13009 13033 13037 13043 13049 13063 13093 13099 13103 13109 13121 13127 13147 13151 13159 13163 13171 13177 13183 13187 13217 13219 13229 13241 13249 13259 13267 13291 13297 13309 13313 13327 13331 13337 13339 13367 13381 13397 13399 13411 13417 13421 13441 13451 13457 13463 13469 13477 13487 13499 13513 13523 13537 13553 13567 13577 13591 13597 13613 13619 13627 13633 13649 13669 13679 13681 13687 13691 13693 13697 13709 13711 13721 13723 13729 13751 13757 13759 13763 13781 13789 13799 13807 13829 13831 13841 13859 13873 13877 13879 13883 13901 13903 13907 13913 13921 13931 13933 13963 13967 13997 13999 14009 14011 14029 14033 14051 14057 14071 14081 14083 14087 14107 14143 14149 14153 14159 14173 14177 14197 14207 14221 14243 14249 14251 14281 14293 14303 14321 14323 14327 14341 14347 14369 14387 14389 14401 14407 14411 14419 14423 14431 14437 14447 14449 14461 14479 14489 14503 14519 14533 14537 14543 14549 14551 14557 14561 14563 14591 14593 14621 14627 14629 14633 14639 14653 14657 14669 14683 14699 14713 14717 14723 14731 14737 14741 14747 14753 14759 14767 14771 14779 14783 14797 14813 14821 14827 14831 14843 14851 14867 14869 14879 14887 14891 14897 14923 14929 14939 14947 14951 14957 14969 14983 15013 15017 15031 15053 15061 15073 15077 15083 15091 15101 15107 15121 15131 15137 15139 15149 15161 15173 15187 15193 15199 15217 15227 15233 15241 15259 15263 15269 15271 15277 15287 15289 15299 15307 15313 15319 15329 15331 15349 15359 15361 15373 15377 15383 15391 15401 15413 15427 15439 15443 15451 15461 15467 15473 15493 15497 15511 15527 15541 15551 15559 15569 15581 15583 15601 15607 15619 15629 15641 15643 15647 15649 15661 15667 15671 15679 15683 15727 15731 15733 15737 15739 15749 15761 15767 15773 15787 15791 15797 15803 15809 15817 15823 15859 15877 15881 15887 15889 15901 15907 15913 15919 15923 15937 15959 15971 15973 15991 16001 16007 16033 16057 16061 16063 16067 16069 16073 16087 16091 16097 16103 16111 16127 16139 16141 16183 16187 16189 16193 16217 16223 16229 16231 16249 16253 16267 16273 16301 16319 16333 16339 16349 16361 16363 16369 16381 16411 16417 16421 16427 16433 16447 16451 16453 16477 16481 16487 16493 16519 16529 16547 16553 16561 16567 16573 16603 16607 16619 16631 16633 16649 16651 16657 16661 16673 16691 16693 16699 16703 16729 16741 16747 16759 16763 16787 16811 16823 16829 16831 16843 16871 16879 16883 16889 16901 16903 16921 16927 16931 16937 16943 16963
done.

real	0m21.637s
user	0m16.273s
sys	0m0.328s

7448179 คือจำนวนเฉพาะที่เล็กที่สุด ที่เป็นผลบวกของจำนวนเฉพาะที่ต่อเนื่องกันจำนวน 15, 31, 127 และ 515 จำนวน

ยังไม่เฉลยโค้ดนะครับ ขออุบไว้ก่อน เดี๋ยวไม่สนุก

สรุปว่าได้คำตอบครบทั้ง 4 ข้อแล้ว นอนหลับสนิทซักที เก็บภาพนี้ไว้เป็นที่ระลึก