Tags » Factorization

The Factorization of Functors + Update

(Huge thanks to Jon Beardsley for this wonderful discussion.)

Let be a posetal category, $[n]$ be a finite chain category, and be an abelian category. Then let there be a functor such that… 193 more words

Mathematics

JClock VII

This alternative clock is not really readable by human. It calculates the first 144¹ primes, assigns 60 of them to every possible second, 60 to every possible minute and 24 to every possible hour. 613 more words

2015

fCAtorization

I came up with a cellular automaton for factoring numbers. Fairly ironheaded and I’m sure not novel but a fun exercise for me. Here’s the Golly rules file. 539 more words

Cellular Automata

Factoring large numbers with the continued fraction method

Recently I mentioned a general method for factoring a large number, not by searching explicitly for factors of the number, but searching instead for congruent squares. 605 more words

แยกตัวประกอบ หาร 3 ลงตัวหรือไม่ (ตอนจบ)

โอเค แล้วเราก็มาถึงตอนจบที่จะมาทดสอบเทคนิค และปรับเทคนิคให้มันแจ่มขึ้นได้มั้ย

ก่อนเริ่ม เราลองสรุปเทคนิคกันหน่อยครับ

3 หารค่าของเลขโดดในหลักใดๆ จะจัดรูปให้เศษเป็นเลขหลักได้นั้นเสมอ เช่น 200/3 จะเหลือเศษ 2, 7000/3 เหลือเศษ 7ดังนั้น การเอาเลขโดดมาบวกกัน ก็คือการลดทอนข้ามขั้นการหารยาว โดยการเอาเศษที่เหลือจากการหารมาบวกกัน แล้วค่อยทำการทดสอบว่าเศษที่เหลือ หาร 3 ลงตัวหรือไม่นั่นเอง

ผมลองมั่วสุ่มตัวเลขขึ้นมา

5683938584940695849308285759984942384757838849485782928484

หาร 3 ลงตัวมั้ย

ในชีวิตจริงเราคงจะไม่เจอปัญหาแบบนี้สำหรับคนทั่วไปอย่างเราๆหรอกครับ :D

แค่คิดก็ไม่อยากคิดแล้ว ตั้งหารยาว ไม่ต้องพูดถึง

ถ้าเจออย่างนี้ถึงจะใช้เทคนิคข้างต้น ก็คงไม่มีใครอยากบวกด้วยหรอก จริงมั้ยครับ

ถ้าเราพิจารณาเทคนิคการทดสอบจะเห็นว่า การบวกเลขแล้วหารด้วย 3 แล้วเก็บเฉพาะเศษไว้ เราสามารถคัดเลขที่มันหาร 3 ได้ลงตัว แล้วตัดทิ้งไปก่อน ไม่จำเป็นต้องบวกทั้งหมด คุณสมบัติการจัดหมู่ คุณสมบัติการสลับที่ การบวกได้นำมาใช้ในงานนี้โดยเฉพาะ ผมเรียกวิธีนี้ว่า Divide and Conquer คือแบ่งแล้วชนะ ตัวไหนไม่เกี่ยวตัดมันออก ไม่เอามาบวก โดยมีขั้นตอนดังต่อไปนี้

1. ตัดเลข 0 ออกไป เพราะ 0 บวกกับอะไรก็ได้เลขเท่าเดิม ไม่เปลี่ยนแปลง ไม่มีผล ไม่ทำให้เศษจากการหาร 3 เปลี่ยนไป
2. ตัดเลข 3,6,9 ออกไป

หลังจากตัดเลข 0,3,6,9 เราได้

56839385849406958493082857599849423847578388494857829284843.

3. ต่อไป ก็ตัดเลขซ้ำกัน 3 ตัว อย่างเช่น เลข 8 ซ้ำกัน 3 ตัวให้ตัดออก เพราะว่า 8+8+8 /3 ลงตัว (หลังจากข้อ 1, 2 เราเหลือ)

5885844584828575844284757888448578228484

เพื่อให้ดูง่ายเราเรียงเลขใหม่ให้เลขเหมือนกันอยู่ด้วยกัน

2222444 444 4444555 55557777888 888 888 888 888

จะเห็นว่าเพียงเท่านี้เราก็จะเหลือเลขโดดไม่เกิน 12 ตัว คือ 1,2,4,5,7,8 อย่างละ 2 ตัวอย่างมาก ตัวอย่างของเราเหลือ

2457

จะเห็นว่าถ้าจะบวกเลขก็บวกได้แล้วนะครับ แต่เรายังสามารถกำจัดได้อีก
4. กำจัดเลข 2 หลักที่เราเห็นว่ามันหาร 3 ลงตัวออกไป เช่น 24, 45, 48, 57, 75 อันนี้ต้องอาศัยการฝึกหน่อย มองเห็นมั้ยครับ โดยขั้นตอนนี้อาจจะเลือกเลข 2 หลักที่ไม่ติดกันก็ได้

24 57

ผมค่อนข้างมั่นใจ 99% ว่าถ้าทำถึง 3 ขั้นตอนข้างบนจะเหลือเลขโดดน้อยจำนวนที่บวกได้ และถ้าทำถึง 4 ขั้นตอน เราจะได้เลขเหลือเพียง 2-3 ตัวอย่างมาก

การทดสอบหากเป็นการทดสอบบนกระดาษ เราก็เขียนตัวเลข แล้วไล่กาทิ้งไปเรื่อยๆได้เลยครับ รวมๆแล้วไม่น่าใช้เวลาเกิน 1 นาทีสำหรับเลขยาวๆที่ยกตัวอย่างมา เห็นด้วยมั้ยครับว่าง่ายกว่าการบวกกันทั้งหมดเยอะเลย

สรุปได้ว่า 5683938584940695849308285759984942384757838849485782928484 หาร 3 ลงตัว

Math & Sci Around Us

แยกตัวประกอบ หาร 3 ลงตัวหรือไม่ (ตอนที่ 2)

ตอนที่แล้ว พูดถึงเทคนิคการทดสอบว่าเลขจำนวนเต็มใดๆหารด้วย 3 ลงตัวหรือไม่ ทำได้โดยนำเลขโดดในแต่ละหลักมาบวกกันทั้งหมด ซึ่งค่ามันจะน้อยลง นำผลลัพธ์ที่ได้มาหารด้วย 3 ถ้าหารได้ลงตัวแสดงว่าเลขตั้งต้นหารด้วย 3 ลงตัว แต่ถ้าไม่ก็จะเหลือเศษ

ตอนที่ 2 นี่เราจะมาดูกันว่าทำไมถึงใช้เทคนิคดังกล่าวได้

ถ้าเราให้เลขโดดของหลักที่ n ใดๆเป็น an ค่าของเลขโดดในหลักนี้จะมีค่า an * 10n , n = 0,1,2,… แทนด้วยเลขหลักหน่วย หลักสิบ ร้อย ตามลำดับ 9 more words

Math & Sci Around Us

แยกตัวประกอบ หาร 3 ลงตัวหรือไม่ (ตอนที่ 1)

เคยมั้ยครับ เวลาหาตัวประกอบของเลขจำนวนหนึ่งว่ามีตัวประกอบอะไรบ้าง เรามักจะทอนให้เลขน้อยลงโดยการทดสอบว่า

  1. หาร 2 ลงตัวมั้ย ซึ่งก็ไม่ยาก ดูว่ามันเป็นเลขคู่หรือเลขคี่ ถ้าเป็นเลขคู่ก็ทอนมันโดยการหาร 2 ซึ่งก็คงทำได้ในใจ
  2. หาร 5 ลงตัวมั้ย เช่นเดียวกัน ก็หาได้ไม่ยากเหมือนกัน โดยการดูว่าเลขตั้งต้นมันลงท้ายด้วย 0 หรือ 5  หรือเปล่า ถ้าใช่ ก็ทำการหารในใจได้อีกเช่นเดียวกัน
  3. หาร 4 หาร 8 หาร 6 ก็ใช้การหาร 2 ลดทอนลงไป

ทีนี้ก็ถึงเลขเจ้าปัญหาที่ไม่เป็นปัญหาเท่าไหร่นักถ้ารู้เทคนิค นั่นคือ เลข 3 หารลงตัว หรือเป็นตัวประกอบหรือไม่ ถ้าเลขไม่เยอะก็คงไม่ลำบากนัก เช่น 81 เราก็มองได้ไม่ยากใช่มั้ยว่าหาร 3 ลงตัว ได้ 27 นั่นเอง

แต่

ถ้าเลขที่ได้มาคือ 123,456,789,123,456,789 หละ เลข 2,5 หารไม่ได้ 4,6,8 ยิ่งไม่ต้องพูดถึง ก็หมายถึงทอนมันให้เล็กลงไม่ได้ด้วยตัวประกอบเล็กๆ ก็เหลือแต่ 3

ยุ่งหละสิ ถ้าจะมาตั้งหารก็คงใช้เวลาพอควร

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

1+2+3+4+5+6+7+8+9+1+2+3+4+5+6+7+8+9=90 บวกไม่ยากใช่มั้ยครับ ซึ่ง 90 หาร 3 ลงตัว ดังนั้น 123,456,789,123,456,789 หาร 3 ลงตัวครับ ถ้าเลขที่บวกแล้วยังเยอะอยู่ เช่นที่ได้มา 90 แล้วยังมองไม่ออก (สมมติครับ) เราก็เอาเลขโดดของเลขที่ได้มาบวกกันอีก แล้วทดสอบเหมือนเดิม เช่น 9+0 ได้ 9 หาร 3 ลงตัว ดังนั้น เลขตั้งต้นก็จะหาร 3 ลงตัวด้วยเช่นกัน

ไม่ยากเลยใช่มั้ยครับ

แต่ไม่รู้เคยสงสัยหรือเปล่าครับว่าทำไมถึงทดสอบด้วยวิธีนี้ได้ ถ้าสงสัย ก็ตามมาดูในตอนต่อไปครับ หลังจากที่เรารู้ที่มาของเทคนิคในตอนที่ 2 เราจะมาดูว่า เราจะทำอย่างไรให้สามารถทำให้การทดสอบทำได้เร็วขึ้นด้วยเทคนิคดังกล่าว มีหลากหลายวิธีกันเลยในตอนที่ 3 ตอนจบนะครับ โปรดติดตามได้ที่นี่ที่เดียว :D

Math & Sci Around Us