128 — Euler Totient Advanced¶
Level 2-এ φ(n) "হাতে গুনে" বের করেছিলে; এবার সেই গোনাকে এক লাইনের সূত্রে নামাব — prime factorization থেকে সরাসরি। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — totient interview-তে কালেভদ্রে আসে, কিন্তু CP-তে multiplicative function-এর জগতে এটা ভিত্তি। 023-এর basic totient ঝালাই করা থাকলে এটা সহজ লাগবে।
Source¶
- Original source: CP-Algorithms — Euler's Totient Function
- Platform: CP-Algorithms — https://cp-algorithms.com/algebra/phi-function.html
- Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
- Difficulty: Medium
- Pattern: multiplicative phi
- Basic idea inherited from: 023 (Basic Euler Totient)
1. Problem in simple words¶
একটা ধনাত্মক integer n দেওয়া আছে। বের করতে হবে φ(n) (Euler's totient) — মানে 1 থেকে n-এর মধ্যে কতগুলো সংখ্যা n-এর সাথে coprime (gcd = 1)।
উদাহরণ: φ(9) = 6, কারণ 1, 2, 4, 5, 7, 8 — এই 6টা সংখ্যা 9-এর সাথে coprime (3, 6, 9 নয়, কারণ ওদের সাথে 9-এর সাধারণ গুণনীয়ক 3)।
Level 2-এ আমরা প্রতিটা সংখ্যার gcd চেক করে গুনেছিলাম (O(n))। এবার লক্ষ্য — prime factorization থেকে এক সূত্রে φ(n), অনেক দ্রুত। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু φ-এর সূত্রটা modular গণিতের (Euler's theorem) মূল চাবিগুলোর একটা।
2. What is the math idea?¶
মূল idea — φ একটা multiplicative function, আর তাই prime factorization থেকে এক সূত্রে বের হয়। n-এর factorization যদি হয় p1^e1 · p2^e2 · ... · pk^ek, তবে:
মানে n দিয়ে শুরু করে প্রতিটা distinct prime p-এর জন্য (1 − 1/p) দিয়ে গুণ — exponent কত তাতে কিছু আসে যায় না, শুধু কোন কোন prime আছে সেটাই গুরুত্বপূর্ণ। আর "multiplicative" মানে: gcd(a, b) = 1 হলে φ(a·b) = φ(a)·φ(b)। এই level CP-leaning হলেও সূত্রটা চমৎকার সরল — প্রতিটা prime স্বাধীনভাবে নিজের ভাগ কাটে।
3. Which basic idea does this inherit from?¶
সরাসরি 023 (Basic Euler Totient)-এর উপর। 023-তে আমরা φ(n)-এর সংজ্ঞা শিখেছিলাম আর gcd চেক করে গুনেছিলাম — O(n) পদ্ধতি। 128 সেই সংজ্ঞাকে রেখে গোনার বদলে prime factorization-এর সূত্র ব্যবহার করে, যা অনেক দ্রুত (O(√n))।
পেছনে আরও দাঁড়িয়ে আছে Level 1-এর prime factorization (trial division)। আর এর উপরে দাঁড়াবে 129 (Mobius) — μ-ও একটা multiplicative function, তাই 128-এর "multiplicative" চিন্তাটা 129-এর ভিত্তি। README-র recommended order-এ তাই 128 → 129 পরপর।
4. Real-life analogy¶
ভাবো একটা ক্লাসে n জন ছাত্র, সবাইকে 1 থেকে n নম্বর দেওয়া। তুমি এমন ছাত্রদের গুনতে চাও যাদের নম্বর n-এর সাথে coprime — যেন তারা "n-এর কোনো গুণনীয়ক-দলের সদস্য নয়"।
ধরো n = 12 = 2² · 3। দুটো "নিষিদ্ধ দল":
- 2-এর গুণিতকরা (2, 4, 6, 8, 10, 12) — অর্ধেক ছাত্র বাদ → বাকি
12·(1 − 1/2) = 6 - বাকিদের থেকে আবার 3-এর গুণিতকরা বাদ → আরও এক-তৃতীয়াংশ যায় →
6·(1 − 1/3) = 4
প্রতিটা prime একটা করে "ছাঁকনি" — 2 অর্ধেক ছাঁকে, 3 এক-তৃতীয়াংশ ছাঁকে, আর তারা স্বাধীনভাবে কাজ করে (coprime বলে ওভারল্যাপ হিসাব মিলে যায়)। শেষে যারা টিকে থাকে, তারাই φ(n) = 4 জন (1, 5, 7, 11)।
5. Visual explanation¶
φ(36)-এর সূত্র, ধাপে ধাপে — 36 = 2² · 3²:
n = 36, factorization: 2² · 3²
distinct prime: শুধু 2 আর 3 (exponent গুরুত্বহীন)
result = 36
2 পেলাম: result = 36 − 36/2 = 36·(1/2) = 18 [2-এর গুণিতক ছাঁকা]
3 পেলাম: result = 18 − 18/3 = 18·(2/3) = 12 [3-এর গুণিতক ছাঁকা]
φ(36) = 12 ✓
multiplicative দিয়ে cross-check:
36 = 4 × 9, gcd(4, 9) = 1
φ(4) = 2 (1, 3 coprime), φ(9) = 6 (1,2,4,5,7,8)
φ(36) = φ(4)·φ(9) = 2·6 = 12 ✓ — দুই পথ একই উত্তর
লক্ষ করো — সূত্রে result − result/p লেখা হলো result·(1 − 1/p)-এরই integer রূপ (ভাঙা ভগ্নাংশ এড়াতে)। আর multiplicative property দিয়ে আলাদা করেও মিলিয়ে দেখা গেল।
6. Example input and output¶
input n -> φ(n) কেন
----------------------------------------------------------------
1 -> 1 (1 নিজে coprime ধরা হয়; convention)
9 -> 6 1,2,4,5,7,8
36 -> 12 36·(1/2)·(2/3)
10 -> 4 1,3,7,9
7 -> 6 prime p -> φ(p) = p − 1
12 -> 4 1,5,7,11
100 -> 40 100·(1/2)·(4/5)
1 -> 1 edge case
খেয়াল করো: prime p হলে φ(p) = p − 1 (1 থেকে p−1 সবাই coprime)। আর prime power p^e হলে φ(p^e) = p^e − p^(e−1) (যেমন φ(9) = 9 − 3 = 6)। edge case φ(1) = 1 (convention — 1 নিজের সাথে coprime ধরা হয়)।
7. Brute force thinking¶
023-এর সরল পদ্ধতি — 1 থেকে n-এর প্রতিটা সংখ্যার সাথে n-এর gcd চেক করা, gcd 1 হলে গুনে নাও:
from math import gcd
def phi_brute(n):
count = 0
for i in range(1, n + 1):
if gcd(i, n) == 1:
count += 1
return count
ছোট n-এ (যেমন 36) এটা নিখুঁত — সরাসরি সংজ্ঞা থেকে গুনছে। আমাদের সূত্রের উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। শুরুর জন্য একদম পরিষ্কার।
8. Why brute force may be slow¶
loop ঘোরে ঠিক n বার, আর প্রতিবার একটা gcd (নিজেই O(log n))। তাই মোট O(n log n)-এর কাছাকাছি।
n ছোট (36): 36 বার gcd — তাৎক্ষণিক
n = 10⁶: 10⁶ বার gcd — সেকেন্ড খানেক
n = 10¹²: 10¹² বার — অসম্ভব!
সূত্র (factorization): O(√n) — n = 10¹²-এও মাত্র ~10⁶ ধাপ
বড় n-এ brute force অচল। অথচ prime factorization trial division-এ O(√n)-এ হয়ে যায় (√(10¹²) = 10⁶), আর তার পর শুধু কয়েকটা গুণ — তাই সূত্র বিশাল দ্রুত।
9. Better thinking¶
মূল insight — φ(n) গুনতে হয় না, prime factorization থেকে হিসাব করা যায়। ধাপ:
1. result = n দিয়ে শুরু
2. p = 2 থেকে √n পর্যন্ত প্রতিটা সম্ভাব্য prime p-এর জন্য:
যদি p | n:
n থেকে p-এর সব ভাগ সরিয়ে দাও (while n % p == 0: n //= p)
result -= result // p (অর্থাৎ result *= (1 − 1/p))
3. লুপ শেষে যদি n > 1 থাকে, সেটা একটা বড় prime factor — তার জন্যও:
result -= result // n
4. result-ই φ(মূল n)
কেন result -= result // p কাজ করে: এটা ঠিক result · (1 − 1/p)-এর integer রূপ, আর যেহেতু এই বিন্দুতে result সবসময় p-এর গুণিতক (n-এর factor বলে), ভাগটা নিঃশেষ হয়। প্রতিটা distinct prime একবারই এই কাটা প্রয়োগ করে — তাই exponent গুরুত্বহীন।
10. Thinking tweak¶
আসল "আহা" মুহূর্ত: φ multiplicative — তাই প্রতিটা prime নিজের ভাগটা স্বাধীনভাবে কাটে, exponent কত তাতে কিছুই যায় আসে না।
brute force প্রতিটা সংখ্যা আলাদা যাচাই করছিল; tweak হলো — গোটা সংখ্যাকে prime-এ ভেঙে প্রতিটা distinct prime-এর জন্য মাত্র একবার (1 − 1/p) গুণ করো। O(n) গোনা থেকে O(√n) factorization-এ নেমে এল। আর multiplicative হওয়াতেই এই ভাঙা-জোড়া বৈধ — φ(p^e) = p^e − p^(e−1), আর coprime অংশগুলো গুণ হয়।
11. Step-by-step dry run¶
phi(36) — সূত্র দিয়ে:
| step | p | n (অবশিষ্ট) | p | n? | result (শুরুতে 36) | | --- | --- | --- | --- | --- | | শুরু | — | 36 | — | result = 36 | | 1 | 2 | 36 | হ্যাঁ (36%2=0) | n থেকে 2 সরাও: 36→18→9; result = 36 − 36//2 = 18 | | 2 | 3 | 9 | হ্যাঁ (9%3=0) | n থেকে 3 সরাও: 9→3→1; result = 18 − 18//3 = 12 | | শেষ | — | 1 | n = 1, তাই n > 1 শর্ত মিথ্যা | result = 12 |
φ(36) = 12 ✓। লক্ষ করো — 2 আর 3 প্রতিটা একবারই কাটল (exponent 2 হলেও), আর n অবশিষ্ট হিসেবে 1-এ নেমে গেল বলে শেষ n > 1 ধাপ লাগল না।
আরেকটা: phi(10) — 10 = 2 · 5:
| step | p | n অবশিষ্ট | result |
|---|---|---|---|
| শুরু | — | 10 | 10 |
| 1 | 2 | 10 → 5 | 10 − 10//2 = 5 |
| লুপ শেষ | — | 5 | 5 > 1, তাই result = 5 − 5//5 = 4 |
φ(10) = 4 ✓ (এখানে 5 বড় prime হিসেবে শেষ ধাপে কাটল)।
12. Python solution¶
def phi(n):
"""Euler's totient φ(n) — prime factorization-এর সূত্রে, O(√n)।"""
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0: # p-এর সব ভাগ সরাও
n //= p
result -= result // p # result *= (1 − 1/p)
p += 1
if n > 1: # অবশিষ্ট বড় prime factor
result -= result // n
return result
def phi_multiplicative(a, b):
"""coprime a, b হলে φ(a·b) = φ(a)·φ(b) — property যাচাইয়ের জন্য।"""
from math import gcd
assert gcd(a, b) == 1
return phi(a) * phi(b)
# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd
def phi_brute(n):
return sum(1 for i in range(1, n + 1) if gcd(i, n) == 1)
# সূত্র vs brute force — 1..300 সব মেলাও
for n in range(1, 301):
assert phi(n) == phi_brute(n), f"φ({n}) ভুল: {phi(n)} != {phi_brute(n)}"
# কিছু known মান
assert phi(1) == 1
assert phi(9) == 6
assert phi(36) == 12
assert phi(10) == 4
assert phi(7) == 6 # prime -> p − 1
assert phi(100) == 40
# prime power: φ(p^e) = p^e − p^(e−1)
assert phi(8) == 8 - 4 # 2³
assert phi(27) == 27 - 9 # 3³
# multiplicative property: gcd=1 হলে φ(ab) = φ(a)φ(b)
assert phi(36) == phi_multiplicative(4, 9)
assert phi(100) == phi_multiplicative(4, 25)
assert phi(35) == phi(5) * phi(7)
# বড় সংখ্যা — দ্রুত
assert phi(1000000) == 400000
print(phi(36)) # 12
print(phi(100)) # 40
print(phi(1000000)) # 400000
print("সব test pass!")
13. Line-by-line explanation¶
result-কে n দিয়ে শুরু করছি (তারপর প্রতিটা prime-এর জন্য কমাব)। p 2 থেকে √n পর্যন্ত ঘোরাই — √n-এর বড় কোনো prime factor বড়জোর একটাই থাকতে পারে, সেটা পরে আলাদা সামলাব।
p যদি n-এর গুণনীয়ক হয় — প্রথমে n থেকে p-এর সব ঘাত সরিয়ে দিই (যাতে p আর বিবেচিত না হয়), তারপর result থেকে result // p বিয়োগ। এটাই result · (1 − 1/p)-এর integer রূপ।
লুপ শেষে n যদি 1-এর বড় থাকে, সেটা একটা বড় prime factor (√(মূল n)-এর চেয়ে বড়) — তার জন্যও একবার (1 − 1/n) কাটা প্রয়োগ। যেমন φ(10)-তে 5।
multiplicative property সরাসরি — coprime হলে φ(a·b) = φ(a)·φ(b)। assert নিশ্চিত করে আমরা সত্যিই coprime জোড়া দিচ্ছি।
বাকি test অংশে 1 থেকে 300 পর্যন্ত সূত্র আর brute force মিলিয়ে দেখা হয়, prime/prime-power/multiplicative সব ক্ষেত্রে যাচাই হয়। সব ঠিক থাকলে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
phi(36) → 12 (36·½·⅔), phi(100) → 40 (100·½·⅘), phi(1000000) → 400000 (10⁶ = 2⁶·5⁶, তাই 10⁶·½·⅘ = 400000) — আর এই বড় সংখ্যাটাও তাৎক্ষণিক, কারণ trial division O(√n)। তার আগে 1..300-এর সব মান brute force-এর সাথে মিলেছে, সব assert pass — তাই সব test pass!।
15. Time complexity¶
O(√n) — trial division-এ p 2 থেকে √n পর্যন্ত ঘোরে। প্রতিটা division/বিয়োগ O(1) (Python-এর বড় সংখ্যায় সামান্য বেশি, কিন্তু সাধারণ মাপে O(1) ধরি)। তাই n = 10¹²-এও মাত্র ~10⁶ ধাপ — brute force-এর O(n log n)-এর তুলনায় বিশাল লাফ। (একাধিক n-এর φ একসাথে চাইলে sieve-ভিত্তিক O(n log log n) আরও ভালো, যা 137-এ আসবে।)
16. Space complexity¶
O(1) — কোনো array লাগছে না, শুধু গুটিকয় variable (result, p, n)। একটামাত্র সংখ্যার φ বের করতে এটাই যথেষ্ট। (একসাথে অনেক সংখ্যার φ চাইলে sieve-এ O(n) array লাগবে — আলাদা বিষয়।)
17. Common mistakes¶
- প্রতিটা distinct prime-এর বদলে প্রতিটা ঘাতে কাটা —
(1 − 1/p)প্রতিটা distinct prime-এর জন্য মাত্র একবার; exponent যত-ই হোক। তাই p পেলে আগে তার সব ঘাত n থেকে সরিয়ে দাও। - অবশিষ্ট বড় prime ভুলে যাওয়া — লুপ √n পর্যন্ত; n যদি শেষে 1-এর বড় থাকে, সেটা বড় prime, তার
result -= result // nলাগবেই (যেমন φ(10)-এর 5)। - float দিয়ে
result * (1 − 1/p)— ভগ্নাংশে round-off ভুল। সবসময় integer-এresult -= result // pকরো। - φ(1) ভুল ধরা — convention অনুযায়ী φ(1) = 1; সূত্র এমনিতেই এটা দেয় (লুপ চলে না, n = 1), তাই আলাদা করে কিছু না করলেও ঠিক।
- n modify করার পর মূল n দরকার হলে গুলিয়ে ফেলা — এখানে result আগে n দিয়ে set করা হয়েছে; তারপর n ভাঙা হচ্ছে — order ঠিক রাখো।
18. Harder problems that inherit this idea¶
- CSES — Counting Coprime Pairs / Common Divisors (https://cses.fi/problemset/) — φ আর divisor sum-এর প্রয়োগ।
- Codeforces — Euler's theorem ভিত্তিক modular exponentiation problems (https://codeforces.com/problemset) — বড় ঘাত কমাতে
a^φ(m) ≡ 1 (mod m)ব্যবহার। - 129 (Mobius Function Intro) — এই repo-রই পরের ধাপ; μ-ও multiplicative, একই factorization-চিন্তায় বসে; আর 130-এ Euler's theorem inverse-এ ফেরে।
19. Pattern learned¶
Multiplicative phi via prime factorization — φ(n) = n · ∏(1 − 1/p) distinct prime p-দের উপর; integer-এ result -= result // p। বড় শিক্ষা: multiplicative function-এ গোটা সংখ্যার উত্তর তার prime-অংশগুলোর উত্তরের গুণফল — তাই গোনার বদলে ভেঙে হিসাব করো। এই চিন্তাটাই μ, divisor function সব জায়গায় ফিরবে।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "φ(n) = n·∏(1 − 1/p) distinct prime-এর উপর; code-এ result -= result // p; φ multiplicative, prime p-তে φ = p−1, p^e-তে p^e − p^(e−1)।" Signal: "n-এর সাথে coprime কতগুলো" বা Euler's theorem-এ ঘাত কমানো — দেখলেই φ মনে পড়বে।
পরের ধাপ → 129 — Mobius Function Intro (আরেক multiplicative ভাই, inclusion-exclusion encode)। ভিত্তি → 023 (Basic Euler Totient); সঙ্গী → 130 — Modular Inverse Advanced।
ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-এর ছক → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" এমন দাবি করা হয়নি — এই level CP-leaning, interview-optional।