Visualization Ideas — Modular Arithmetic¶
এই level-এর মূল ছবি একটাই — ঘড়ি। বাকি সব visualization সেই ঘড়িরই রকমফের: কাঁটার লাফ, ঘড়ির উপর গুণের নাচ, binary সিঁড়ি। খাতায় একটা mod-7 ঘড়ি এঁকে রাখো — পুরো level ওটার উপরেই চলবে।
প্রতি concept-এর visualization idea¶
1. Mod = ঘড়ি, number line ভাঁজ করা¶
দুটো ছবি পাশাপাশি আঁকো: (ক) 0 থেকে 20-এর number line, প্রতি 5 ঘরে কাঁচি-দাগ; (খ) 5-ঘরের একটা ঘড়ি। line-এর টুকরোগুলো ঘড়ির গায়ে পেঁচিয়ে দেখাও — 7, 12, 17 সবাই ঘড়ির 2-ঘরে নামে। Animation idea: number line-টা spiral হয়ে ঘড়ির উপর গুটিয়ে যাচ্ছে, একই ঘরে নামা সংখ্যারা একই রঙ পাচ্ছে।
2. Modular addition = কাঁটার লাফ¶
mod-7 ঘড়িতে (5 + 4) % 7: কাঁটা 5-এ আছে, 4 ঘর সামনে লাফাও — 6, 0, 1, 2 — নামল 2-তে। Subtraction = পেছনে লাফ। Negative result-এর ভয়টাও এখানে কাটে: পেছনে হেঁটে ঘড়িতে যেখানেই নামো, ঘরের নাম্বার কখনো negative না।
3. Multiplication table on the clock = নাচের ছক¶
mod-7 এ 3-এর গুণের সারি লেখো: 3, 6, 2, 5, 1, 4, 0 — সব ঘর ছুঁয়েছে (gcd(3,7)=1 বলে)! পাশে mod-6 এ 2-এর সারি: 2, 4, 0, 2, 4, 0 — মোটে 3টা ঘরে আটকে। ছবিটাই বলে দেয় কেন coprime হলে inverse আছে (1 ছোঁয়া যায়) আর নাহলে নেই।
4. Fast power = binary সিঁড়ি¶
Exponent-এর binary রূপটা সিঁড়ির মতো আঁকো — প্রতি ধাপে a square হচ্ছে (a → a² → a⁴ → a⁸), আর যে ধাপের bit 1, সেখান থেকে result-এর ঝুড়িতে একটা করে জিনিস পড়ছে। নিচে worked example আছে।
5. Cyclicity = ঘড়ির উপর পায়ের ছাপ¶
mod-10 ঘড়িতে 2-এর power-গুলোর পায়ের ছাপ আঁকো: 2 → 4 → 8 → 6 → 2 → ... — চারটা ঘরে একটা চক্রাকার নাচ। 3-এর জন্য: 3 → 9 → 7 → 1 → 3 — আরেকটা চক্র। প্রতিটা base-এর নিজস্ব নাচের ছক — এটাই cyclicity।
6. Inverse = জোড়া খোঁজার খেলা¶
mod-7 এর 1-6 কে dot হিসেবে আঁকো; যাদের গুণফল ≡ 1, তাদের লাইন দিয়ে জোড়ো: 1↔1, 2↔4, 3↔5, 6↔6। প্রতিটা সংখ্যার ঠিক একজন জোড়া — inverse-এর অস্তিত্ব চোখে দেখা। mod-6 এ একই ছবি আঁকলে 2, 3, 4 জোড়াহীন একা — gcd ≠ 1 দের কেউ নেই।
7. nCr pipeline = কারখানার তিনটা ঘর¶
তিন ঘরের flow-ছবি: [fact[] বানাও O(N)] → [inv_fact[] পেছন থেকে O(N)] → [প্রতিটা query: 3টা lookup + 2টা গুণ, O(1)]। পাশে লেখো: "একবার কারখানা, হাজার query free" — sieve-এর সেই precompute দর্শনই।
8. Hash = আঙুলের ছাপ মেশিন¶
বাঁ দিকে লম্বা লম্বা string ঢুকছে, ডান দিকে ছোট্ট সংখ্যা বেরোচ্ছে — মাঝে (h*B + ch) % M লেখা মেশিন। নিচে ছোট করে: দুটো ভিন্ন string-এর তীর কালেভদ্রে একই সংখ্যায় গিয়ে মিশছে — collision, লাল রঙে।
Worked ASCII example 1: mod-12 ঘড়িতে যোগ¶
"9টা বাজে, 5 ঘণ্টা পরে?" (9 + 5) % 12 = 14 % 12 = 2
11 0 1
10 2
9 * 3 * = শুরু (9)
8 4 কাঁটা 5 ঘর এগোয়:
7 6 5 9 -> 10 -> 11 -> 0 -> 1 -> 2 নামল 2-তে ✓
"9টা থেকে 11 ঘণ্টা পেছনে?" (9 - 11) % 12 -> Python: 10
কাঁটা পেছনে: 9 -> 8 -> ... -> 0 -> 11 -> 10 ঘড়ি negative চেনে না!
((9 − 11) % 12 + 12) % 12 = 10 — safe রূপটা ঘড়ির এই ছবিরই code-রূপ।
Worked ASCII example 2: fast power-এর binary সিঁড়ি (3^13 % 7)¶
13 = 1101₂ (নিচ থেকে পড়ো — last bit আগে)
bit a-এর মান (square হতে হতে) bit=1? -> result-এ গুণ
--- ------------------------- ----------------------
1 3¹ ≡ 3 হ্যাঁ -> result = 3
0 3² ≡ 9 ≡ 2 না
1 3⁴ ≡ 2² ≡ 4 হ্যাঁ -> result = 3×4 ≡ 5
1 3⁸ ≡ 4² ≡ 2 হ্যাঁ -> result = 5×2 ≡ 3
উত্তর: 3¹³ ≡ 3 (mod 7) মোটে 4 ধাপ — 13 ধাপ না!
সিঁড়ির প্রতিটা ধাপে a square হয়, কিন্তু result-এ শুধু "1-bit ধাপ" থেকেই জিনিস পড়ে।
Worked ASCII example 3: 7-এর last digit cycle¶
7¹ 7² 7³ 7⁴ | 7⁵ 7⁶ 7⁷ 7⁸ | ...
7 49 343 2401| ...
last: 7 9 3 1 | 7 9 3 1 | -> cycle: [7, 9, 3, 1], length 4
7^222 -> 222 % 4 = 2 -> cycle-এর ঘর 2 -> last digit 9
ঘড়ি-রূপে (mod 10): 7 -> 9
0 ^ \
9 1 | v
8 2 পায়ের ছাপ: 1 <- 3
7 3 7 -> 9 -> 3 -> 1 -> আবার 7
6 4
5
সাবধান-ঘর: exponent % 4 == 0 হলে (যেমন 7⁸) cycle-এর শেষ ঘর পড়ো — উত্তর 1, প্রথম ঘরের 7 না।
নিজে practice করার নিয়ম¶
- একটা mod-7 ঘড়ি খাতার প্রথম পাতায় এঁকে রাখো; প্রতিটা problem-এ অন্তত একবার কাঁটা ঘোরাও
pow(2, 10, 9)হাতে binary সিঁড়ি দিয়ে করো (10 = 1010₂), তারপর Python-এ মিলিয়ে নাও- mod-5 আর mod-8 এ 3-এর গুণের সারি লিখে দেখো — কোনটায় 1 আসে, কোনটায় না, আর কেন (gcd!)
- nCr pipeline-এর তিন-ঘরের flow-ছবিটা নিজে এঁকে প্রতিটা ঘরের complexity লেখো — Level 3-এ ঢোকার টিকিট এটাই