023 — Euler Phi Basic

021-এ coprime বুঝেছ, 016-এ prime factorization। এবার দুটো মিলিয়ে একটা সুন্দর জিনিস: Euler's phi — একটা সংখ্যা n-এর সাথে কয়টা সংখ্যা coprime, তা গোনা। হাতে গুনলে অনেক সময়, কিন্তু factorization জানলে একটা চমৎকার formula আছে। ধীরে পড়ো — n × ∏(1 − 1/p) কেন কাজ করে, সেটাই গল্পের প্রাণ।

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 1: Divisibility, Prime, GCD, LCM
• Difficulty: Medium
• Pattern: totient formula — φ(n) = n · ∏(1 − 1/p)
• Basic idea inherited from: 016 — Prime Factorization; 021 — Coprime Check

1. Problem in simple words

একটা ধনাত্মক integer n দেওয়া আছে। বের করতে হবে φ(n) (Euler's phi, বা totient) — মানে 1 থেকে n পর্যন্ত কয়টা সংখ্যা n-এর সাথে coprime (gcd 1)।

উদাহরণ: φ(12) বের করতে 1..12-এর মধ্যে দেখি কারা 12-এর সাথে coprime — শুধু 1, 5, 7, 11 (বাকিরা 2 বা 3 share করে)। তাই φ(12) = 4।

কয়েকটা চেনা মান: φ(1) = 1 (শুধু 1 নিজে), আর p prime হলে φ(p) = p − 1 (1 থেকে p−1 সবাই p-র সাথে coprime, কারণ p-র একমাত্র factor সে নিজে)।

2. What is the math idea?

মূল idea হলো factorization থেকে আসা একটা product formula। n-এর distinct prime গুলো p₁, p₂, ... হলে:

φ(n) = n · (1 − 1/p₁) · (1 − 1/p₂) · ...

মানে n নাও, তারপর প্রতিটা distinct prime p-র জন্য (1 − 1/p) দিয়ে গুণ করো।

কেন? 1..n-এর মধ্যে অর্ধেক সংখ্যা 2-এর গুণিতক — তারা 2 share করে, তাই বাদ; টিকে থাকে × (1 − 1/2) ভাগ। সেই টিকে থাকাদের এক-তৃতীয়াংশ 3-এর গুণিতক — বাদ, টিকে × (1 − 1/3)। প্রতিটা prime ক্রমে "কিছু অংশ কেটে দেয়" — sieve-এর crossing-out-এরই ভগ্নাংশ-রূপ। শুধু distinct prime লাগে (একই prime-এর power বারবার নয়)।

3. Which basic idea does this inherit from?

এটা দুটো আগের idea-র উপর দাঁড়িয়ে:

• 016 (Prime Factorization) — φ-র formula চালাতে আগে n-এর distinct prime গুলো জানা চাই। আমরা ছোট prime দিয়ে n-কে "খোসা ছাড়িয়ে" সেই prime গুলো বের করি (016-এর কৌশল), শুধু এবার power গোনার বদলে প্রতিটা distinct prime একবার ব্যবহার করি।
• 021 (Coprime Check) — φ-র সংজ্ঞাটাই "coprime কয়টা"; gcd == 1-এর ধারণা না থাকলে φ-ই মানে রাখে না। (Brute force version-এ আমরা সরাসরি 021-এর coprime check প্রতিটা সংখ্যায় চালাব।)

তাই আটকালে: formula-তে আটকালে 016-এ ফিরে factorization ঝালাও; "coprime মানে কী"-তে আটকালে 021।

4. Real-life analogy

ভাবো 12 জনের একটা দল, আর তুমি জোড়ায় নাচ আয়োজন করবে — কিন্তু শর্ত: একজন partner-এর সাথে নাচতে গেলে তাদের "ছন্দ" মিলতে হবে, মানে তারা coprime হতে হবে। তুমি গুনতে চাও — 12 নম্বরের সাথে কতজন (1..12) ছন্দ মেলায়।

হাতে গুনতে গেলে সবাইকে একে একে যাচাই করতে হয় (1 মেলে, 2 মেলে না কারণ দুজনেই 2-এর ঘরে, ...)। কিন্তু একটা শর্টকাট আছে: 12-এর "বাধা" শুধু তার prime উপাদান 2 আর 3। প্রথমে 2-এর ঘরের অর্ধেককে বাদ দাও, তারপর বাকিদের থেকে 3-এর ঘরেরদের বাদ দাও — যা টিকে থাকে, তারাই ছন্দ মেলায়। সেই "ভাগে ভাগে বাদ দেওয়া"-ই phi-র formula।

5. Visual explanation

প্রথমে হাতে-গোনা — 1..12-এর মধ্যে কারা 12-এর সাথে coprime:

n = 12, distinct prime: 2, 3

 1  2  3  4  5  6  7  8  9 10 11 12
 ✓  ✗  ✗  ✗  ✓  ✗  ✓  ✗  ✗  ✗  ✓  ✗
 |              |        |        |
coprime:        1     5  7     11   ->  φ(12) = 4
(✗ = 2 বা 3 share করে)

এবার formula কীভাবে একই 4 দেয়:

12 = 2^2 · 3^1   ->  distinct prime { 2, 3 }

φ(12) = 12 · (1 − 1/2) · (1 − 1/3)
      = 12 ·   1/2     ·   2/3
      = 12 · (1/3)
      = 4     ✓   (হাতে-গোনার সাথে মিলল)

6. Example input and output

   n   ->  φ(n)   কেন
-----------------------------------
   1   ->   1     শুধু 1 নিজে
   2   ->   1     শুধু 1 (prime, p−1 = 1)
   9   ->   6     1,2,4,5,7,8 (3 আর 6 বাদ)
  10   ->   4     1,3,7,9
  12   ->   4     1,5,7,11
  13   ->  12     prime -> p−1 = 12
  36   ->  12     36 = 2^2·3^2 -> 36·1/2·2/3 = 12
  100  ->  40     100 = 2^2·5^2 -> 100·1/2·4/5 = 40

দুটো জিনিস খেয়াল করো: p prime হলে φ(p) = p − 1 (13 → 12)। আর একই distinct prime থাকলে power যত-ই হোক formula-তে prime একবারই বসে — 12 (2²·3) আর 36 (2²·3²) দুটোরই distinct prime {2,3}, কিন্তু φ আলাদা কারণ সামনে n আলাদা (12 vs 36)।

7. Brute force thinking

φ-র সংজ্ঞা সরাসরি ধরে — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা ঘুরে দেখি কে n-এর সাথে coprime, গুনি:

def phi_brute(n):
    from math import gcd
    count = 0
    for k in range(1, n + 1):
        if gcd(k, n) == 1:        # 021-এর coprime check
            count += 1
    return count

এটা একদম সংজ্ঞা: 1..n-এর প্রতিটা k-র জন্য gcd(k, n) == 1 হলে count বাড়াই। 021-এর coprime check-ই এখানে n বার চালানো হচ্ছে। সরল, ঠিক উত্তর, আর formula-র উত্তর verify করার জন্য চমৎকার।

8. Why brute force may be slow

এই loop ঠিক n বার ঘোরে, প্রতিবার একটা gcd (O(log n))। তাই খরচ O(n log n)।

n = 1,000        -> ~1,000 gcd       (চোখের নিমেষে)
n = 1,000,000    -> ~10^6 gcd        (ঠিক আছে, সেকেন্ড খানেক)
n = 10^12        -> ~10^12 gcd       (অসম্ভব — TLE)

মূল সমস্যা: n বিশাল হলে 1..n ঘোরা অসম্ভব। অথচ formula-তে আমরা শুধু n-এর prime factor গুলো খুঁজি (O(√n) সময়), তারপর গুটিকয় গুণ — n যত বড়ই হোক, কাজ √n-এই সীমাবদ্ধ। সেটাই দ্রুত পথ।

9. Better thinking

মূল insight — φ গুনতে 1..n ঘোরার দরকার নেই; n-এর distinct prime জানলে formula-তেই উত্তর।

φ(n) = n · ∏(1 − 1/p)। বাস্তবে float এড়াতে আমরা ভগ্নাংশ ব্যবহার না করে integer-এ লিখি: প্রতিটা distinct prime p পেলে result থেকে result // p বিয়োগ করি — কারণ result × (1 − 1/p) = result − result/p:

def phi(n):
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:        # এই prime-কে নিঃশেষে ছাড়াই
                n //= p
            result -= result // p    # result × (1 − 1/p), integer-এ
        p += 1
    if n > 1:                        # বাকি যা, সে নিজেই বড় prime
        result -= result // n
    return result

মূল চালাকি দুটো: (1) প্রতিটা distinct prime একবারই result কমায় (ভেতরের while দিয়ে power সব ছেঁটে ফেলি); (2) শেষের if n > 1 — n-এর সবচেয়ে বড় prime factor (যদি সে √n-এর চেয়ে বড় হয়) ধরার জন্য।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: result × (1 − 1/p) মানে আসলে result − result/p — তাই float ছাড়াই, শুধু integer বিয়োগ দিয়ে phi হিসাব হয়।

আর দ্বিতীয় মোচড়: formula-তে distinct prime লাগে, power নয়। তাই 8 = 2³ হলেও φ-তে 2 একবারই বসে — φ(8) = 8 × (1 − 1/2) = 4, তিনবার নয়। এই "power উপেক্ষা করো, distinct prime নাও" আর "ভগ্নাংশকে বিয়োগে বদলাও" — এই দুই tweak মাথায় গেঁথে নাও।

11. Step-by-step dry run

চলো phi(12) ধীরে চালাই। শুরুতে result = 12, n = 12:

p	n % p == 0?	ভেতরের while: n হয়	result বদল	result
2	হ্যাঁ	12→6→3	12 − 12//2 = 12 − 6	6
3	3·3 > 3, loop শেষ	—	—	6

Loop-এর পরে n = 3 > 1, তাই শেষ ধাপ: result -= result // n → 6 − 6//3 = 6 − 2 = 4।

φ(12) = 4 — section 5-এর হাতে-গোনা 1,5,7,11-এর সাথে হুবহু মিলল। লক্ষ করো 2-এর power (2²) থাকলেও result একবারই কমেছে, কারণ ভেতরের while সব 2 নিঃশেষ করেছে আগেই।

12. Python solution

def phi(n):
    """1..n-এর মধ্যে কয়টা সংখ্যা n-এর সাথে coprime — Euler totient।"""
    if n <= 0:
        return 0
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:         # distinct prime: power সব ছাঁটো
                n //= p
            result -= result // p     # result × (1 − 1/p)
        p += 1
    if n > 1:                         # বাকি n নিজেই একটা বড় prime
        result -= result // n
    return result


def phi_brute(n):
    """সংজ্ঞা ধরে: 1..n-এ coprime গোনা — formula verify করতে।"""
    from math import gcd
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert phi(1) == 1
assert phi(2) == 1
assert phi(9) == 6
assert phi(10) == 4
assert phi(12) == 4
assert phi(13) == 12          # prime -> p−1
assert phi(36) == 12
assert phi(100) == 40
assert phi(7919) == 7918      # বড় prime -> p−1

# formula আর brute force ছোট range-এ মিলছে কি না
for m in range(1, 50):
    assert phi(m) == phi_brute(m)

print(phi(12))    # 4
print(phi(13))    # 12
print(phi(100))   # 40
print("সব test pass!")

13. Line-by-line explanation

    result = n
    p = 2
    while p * p <= n:

result শুরুতে n (formula-র সামনের n)। তারপর √n পর্যন্ত প্রতিটা সম্ভাব্য prime p দেখি — কারণ n-এর কোনো prime factor √n-এর এপারে অবশ্যই থাকে (বড়জোর একটা ছাড়া)।

        if n % p == 0:
            while n % p == 0:
                n //= p

p যদি n-কে ভাগ করে, সে একটা prime factor। ভেতরের while দিয়ে p-কে নিঃশেষে ছাড়াই (n থেকে সব p সরিয়ে দিই) — যাতে প্রতিটা distinct prime একবারই গোনা হয়।

            result -= result // p

এটাই formula-র হৃদয়: result × (1 − 1/p)-কে integer-এ লেখা। float এড়িয়ে শুধু বিয়োগ।

    if n > 1:
        result -= result // n

Loop শেষে n যদি এখনো 1-এর বেশি হয়, সেটা n-এর সবচেয়ে বড় prime factor (√n-এর চেয়ে বড়, তাই loop ধরেনি)। তাকেও একবার গুণে নিই। (যেমন n = 14 = 2×7: loop-এ 2 ধরা পড়ে, n হয়ে যায় 7, তারপর 7 এই লাইনে।)

phi_brute সংজ্ঞা ধরে গোনে; নিচের for m in range(1, 50) loop দুই version মিলিয়ে formula-র correctness যাচাই করে। সব ঠিক থাকলে শেষে সব test pass!।

14. Output walkthrough

চালালে যা ছাপবে:

4
12
40
সব test pass!

প্রথম লাইন: φ(12) = 4 (section 11-এর dry run)। দ্বিতীয়: φ(13) = 12 (prime, তাই p−1)। তৃতীয়: φ(100) = 40 (100 = 2²·5² → 100·1/2·4/5 = 40)। তার আগে সব assert, এমনকি 1..49 জুড়ে formula-vs-brute মিল — সব চুপচাপ pass করেছে, তাই শেষে সব test pass!।

15. Time complexity

O(√n) — মূল loop p চলে 2 থেকে √n পর্যন্ত (এটাই factorization-এর খরচ)। ভেতরের while-গুলো মিলিয়েও মোট কাজ O(√n)-এই থাকে (n বারবার ভাগ হয়ে দ্রুত ছোট হয়)। তাই n = 10¹² হলেও √n = 10⁶ — এক লহমায় শেষ। brute force-এর O(n log n)-এর তুলনায় বিশাল উন্নতি।

16. Space complexity

O(1) — শুধু result, p, আর পরিবর্তিত n — গুটিকয় variable। কোনো list, array বা sieve বানাচ্ছি না (এটা single-n basic version)। (অনেকগুলো n একসাথে লাগলে sieve দিয়ে O(n) জায়গায় সব φ precompute করা যায় — Level 2-র গল্প।)

17. Common mistakes

1. distinct prime-এর বদলে power গোনা — 8 = 2³-এ 2 একবারই formula-তে বসে; ভেতরের while দিয়ে power ছেঁটে না ফেললে result বারবার কমে ভুল হবে।
2. শেষের if n > 1 ভুলে যাওয়া — n-এর বড় prime factor (যেমন 14-এর 7, বা 7919) এই লাইন ছাড়া ধরা পড়ে না, φ ভুল আসে।
3. float ব্যবহার করা — result * (1 - 1/p) সরাসরি float-এ করলে rounding ভুল; integer বিয়োগ result -= result // p নিরাপদ।
4. n ≤ 0 বা n = 1 ভুলে যাওয়া — φ(1) = 1 (loop চলে না, result থাকে 1 — ঠিক); n ≤ 0 আমরা 0 ধরি।
5. prime-এর জন্য φ(p) = p ভাবা — সঠিক হলো p − 1 (p নিজে p-র সাথে coprime নয়)।

18. Harder problems that inherit this idea

• CP-Algorithms — Euler's totient function (https://cp-algorithms.com/algebra/phi-function.html) — sieve দিয়ে 1..n সব φ একসাথে, আর Euler's theorem-এ প্রয়োগ; এই formula-র পরের ধাপ।
• Project Euler 69 — Totient maximum (https://projecteuler.net/problem=69) — φ-র ধর্ম কাজে লাগিয়ে optimization; common pattern।
• Level 2 — Fermat/Euler theorem আর modular exponentiation — সেখানে φ প্রধান চরিত্র (a^φ(n) ≡ 1 mod n); এই note-টাই তার ভিত্তি।

19. Pattern learned

Totient via prime factorization — φ(n) = n · ∏(1 − 1/p), integer-এ result -= result // p প্রতি distinct prime-এ; শেষে if n > 1। মূল reusable টুকরো: factorization + product formula, আর "ভগ্নাংশকে বিয়োগে বদলানো"। φ পরে modular গণিতের কেন্দ্রে আসবে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "φ(n) = n নাও, প্রতিটা distinct prime p-তে result -= result // p, শেষে n>1 হলে আরেকবার। 'n-এর সাথে কয়টা coprime' দেখলেই phi মনে করব — O(√n), আর Level 2-তে Euler theorem এখান থেকেই।"

পরের ধাপ → 024 — Number of Divisors (factorization থেকে আরেকটা formula)। শিকড় → 016 — Prime Factorization, 021 — Coprime Check।

ফিরে দেখা: এই 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" দাবি করা হয়নি — বরং "common interview pattern" লেখা হয়েছে।