129 — Mobius Function Intro

এই note-এ আমরা একটা মজার function-এর সাথে পরিচিত হব — μ (Mobius), যেটা আসলে inclusion-exclusion-এর গোটা যোগ-বিয়োগের নাচকে একটা ছোট function-এ ভরে রাখে। মনে করিয়ে দিই: এই Level 10 competitive programming-ঘেঁষা, interview-এর জন্য optional — Mobius interview-তে আসেই না, কিন্তু CP-তে coprime-গোনা আর divisor-sum problem-এ এটা প্রায় জাদুর কাঠি। 128 (totient) আর 044 (inclusion-exclusion) ঝালাই থাকলে এটা সহজ লাগবে।

Source

• Original source: Wikipedia — Möbius function
• Platform: Wikipedia — https://en.wikipedia.org/wiki/M%C3%B6bius_function
• Topic: Math-based programming fundamentals → Level 10: Advanced Number Theory
• Difficulty: Hard
• Pattern: IE encoding (inclusion-exclusion encoding)
• Basic idea inherited from: 044 (Inclusion-Exclusion), 128 (Euler Totient Advanced)

1. Problem in simple words

একটা ধনাত্মক integer n দেওয়া আছে। বের করতে হবে μ(n) (Mobius function), যার মান শুধু তিনটার একটা — 1, −1, বা 0 — নিয়ম এই:

μ(n) =  1        যদি n = 1
μ(n) =  (−1)^k   যদি n হয় k-টা ভিন্ন prime-এর গুণফল (square-free, কোনো prime² ভাগ করে না)
μ(n) =  0        যদি কোনো prime-এর বর্গ (p²) n-কে ভাগ করে

উদাহরণ: μ(6) = μ(2·3) = (−1)² = 1; μ(30) = μ(2·3·5) = (−1)³ = −1; μ(12) = 0 (কারণ 4 = 2² ভাগ করে)।

পাশাপাশি প্রায়ই দরকার হয় 1 থেকে N-এর সব μ একসাথে — তখন একটা sieve দিয়ে O(N log log N)-এ পুরো array বানানো যায়। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু μ সংখ্যাতত্ত্বের সবচেয়ে কেতাদুরস্ত খেলনাগুলোর একটা।

2. What is the math idea?

মূল idea — inclusion-exclusion-এর sign-গুলোকে একটা function-এ encode করা। 044-তে দেখেছিলে "2 বা 3 বা 5 দিয়ে ভাগ যায় এমন কতগুলো" গুনতে যোগ-বিয়োগের নাচ: একটা set যোগ, জোড়া-overlap বিয়োগ, তিন-overlap আবার যোগ... । μ ঠিক সেই sign-প্যাটার্নটাই ধরে রাখে:

• 1টা prime → sign −1 (বিয়োগ)
• 2টা prime → sign +1 (যোগ)
• 3টা prime → sign −1
• কোনো prime বর্গ থাকলে → 0 (এই পদ একদম বাদ)

আর μ multiplicative (128-এর φ-এর মতো): gcd(a, b) = 1 হলে μ(a·b) = μ(a)·μ(b)। এই level CP-leaning হলেও মূল সুর সরল — μ হলো "কয়টা distinct prime, জোড় না বিজোড়, আর কোনো বর্গ আছে কি না" — এই তিন প্রশ্নের একলাইন উত্তর।

3. Which basic idea does this inherit from?

দুটো শিকড়:

• 044 (Inclusion-Exclusion) — μ আসলে IE-র sign-choreography। "ঠিক gcd = 1 কতগুলো জোড়া" বা "square-free কতগুলো" গুনতে IE-র যে যোগ-বিয়োগ লাগে, μ সেগুলো এক sum-এ গুছিয়ে দেয়: ∑ μ(d) · (d-এর গুণিতক গোনা)।
• 128 (Euler Totient Advanced) — μ-ও φ-এর মতো multiplicative, একই prime-factorization-চিন্তায় বসে। φ "কতগুলো coprime" গোনে; μ "কীভাবে coprime-গোনাকে এক সূত্রে আনা যায়" তার চাবি (Mobius inversion)।

তাই README-র recommended order-এ 128 → 129 পরপর — দুটোই multiplicative function-এর জগৎ।

4. Real-life analogy

ভাবো তুমি একটা ঘরে ঢুকছ যেখানে সুইচ আছে, আর প্রতিটা distinct prime একটা করে সুইচ টেপে — প্রতিটা চাপ আলো on→off→on উল্টে দেয় (টগল)।

• কোনো prime নেই (n = 1) → আলো জ্বলছে → μ = +1
• 1টা prime → একবার টগল → অন্ধকার → μ = −1
• 2টা prime → দুবার টগল → আবার আলো → μ = +1
• 3টা prime → আবার অন্ধকার → μ = −1

আর একটা বিশেষ নিয়ম: যদি কোনো prime দুবার আসে (মানে p² ভাগ করে), সুইচটা পুড়ে যায় — পুরো ঘর চিরতরে অন্ধকার, μ = 0। তাই μ দুই জিনিস বলে দেয়: (ক) আলো জ্বলছে না নিভছে (distinct prime জোড় না বিজোড়), আর (খ) সুইচ পুড়ে গেছে কি না (square আছে কি না)।

5. Visual explanation

μ-এর table, 1 থেকে 12 — সাথে কারণ:

n  | factorization | distinct primes (k) | square আছে? | μ(n)
---+---------------+---------------------+-------------+------
 1 | —             | 0                   | না          |  +1   (convention)
 2 | 2             | 1                   | না          |  −1   (−1)¹
 3 | 3             | 1                   | না          |  −1
 4 | 2²            | —                   | হ্যাঁ (2²)   |   0
 5 | 5             | 1                   | না          |  −1
 6 | 2·3           | 2                   | না          |  +1   (−1)²
 7 | 7             | 1                   | না          |  −1
 8 | 2³            | —                   | হ্যাঁ (2²)   |   0
 9 | 3²            | —                   | হ্যাঁ (3²)   |   0
10 | 2·5           | 2                   | না          |  +1
11 | 11            | 1                   | না          |  −1
12 | 2²·3          | —                   | হ্যাঁ (2²)   |   0

μ : 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0

লক্ষ করো — যেই কোনো বর্গ (4, 8, 9, 12) ভাগ করে, μ সঙ্গে সঙ্গে 0; বাকিদের জন্য শুধু distinct prime গুনে জোড়-বিজোড় দিয়ে ±1।

6. Example input and output

input n  ->  μ(n)        কেন
----------------------------------------------------------------
   1     ->   1          convention
   2     ->  -1          1টা prime
   6     ->   1          2টা prime (2·3)
  30     ->  -1          3টা prime (2·3·5)
   4     ->   0          2² ভাগ করে
  12     ->   0          2² ভাগ করে
  35     ->   1          5·7, 2টা prime
 210     ->   1          2·3·5·7, 4টা prime -> (−1)⁴
  17     ->  -1          prime

খেয়াল করো: square-free (কোনো বর্গ ভাগ করে না) হলে μ = (−1)^(distinct prime সংখ্যা); নাহলে 0। আর μ(1) = 1 (convention, কারণ 1-এর কোনো prime নেই, (−1)⁰ = 1)। 210 = 2·3·5·7 — চারটা prime, তাই (−1)⁴ = +1।

7. Brute force thinking

সরাসরি সংজ্ঞা থেকে — একটা সংখ্যাকে prime-এ factorize করে দেখি কোনো prime দুবার আসে কি না, আর কয়টা distinct prime:

def mobius_one(n):
    if n == 1:
        return 1
    cnt = 0                      # distinct prime গোনা
    p = 2
    while p * p <= n:
        if n % p == 0:
            n //= p
            cnt += 1
            if n % p == 0:       # p আবার ভাগ করল -> p² আছে
                return 0
        p += 1
    if n > 1:                    # অবশিষ্ট বড় prime
        cnt += 1
    return -1 if cnt % 2 else 1

একটা সংখ্যার জন্য এটা নিখুঁত — trial division করে square ধরা পড়লেই 0, নাহলে distinct prime গুনে ±1। শুরুর জন্য পরিষ্কার।

8. Why brute force may be slow

একটা সংখ্যার জন্য এটা O(√n) — ঠিক আছে। সমস্যা হয় যখন 1 থেকে N-এর সব μ চাই (CP-তে এটাই বেশি দরকার): প্রতিটা সংখ্যায় আলাদা factorization মানে মোট O(N√N)।

একটা μ(n):              O(√n) — ঠিক আছে
1..N সব μ, একে একে:     N × O(√N) = O(N^1.5) — N=10⁶ হলে 10⁹ ধাপ, ধীর
sieve দিয়ে সব μ:        O(N log log N) — N=10⁶ মুহূর্তে

বহুবার μ লাগলে প্রতিবার factorize করা অপচয়। sieve একবারে পুরো array বানিয়ে দেয়, তারপর প্রতিটা lookup O(1)।

9. Better thinking

মূল insight — sieve দিয়ে একবারে 1 থেকে N-এর সব μ বানিয়ে ফেলা। Eratosthenes-এর ছাঁকনির মতো, কিন্তু প্রতিটা prime দিয়ে কাটার সময় sign উল্টাই আর square ধরা পড়লে 0 বসাই:

1. mu[i] = 1 সবার জন্য শুরু
2. প্রতিটা prime p-এর জন্য (যেটা এখনো mark হয়নি):
     p-এর প্রতিটা গুণিতক j-এর mu[j]-এর sign উল্টাও (× −1)  [একটা prime যোগ হলো]
     p²-এর প্রতিটা গুণিতক j-এর mu[j] = 0 বসাও              [square আছে]

এভাবে প্রতিটা সংখ্যা তার distinct prime অনুযায়ী ±1 পায়, আর কোনো square থাকলে 0। একটামাত্র সংখ্যা চাইলে অবশ্য section 7-এর factorization (O(√n)) যথেষ্ট — দুটো পথই আমরা রাখব আর মিলিয়ে দেখব।

10. Thinking tweak

আসল "আহা" মুহূর্ত: μ আসলে inclusion-exclusion-এর sign — তাই "জোড় না বিজোড় distinct prime" আর "square আছে কি না", এই দুটো প্রশ্নের উত্তরই পুরো μ।

brute force প্রতিবার পুরো factorization করছিল; tweak হলো — sieve-এ প্রতিটা prime একবারই তার গুণিতকদের sign উল্টে দিক, আর p²-এর গুণিতকদের 0 করে দিক। তখন O(√n) প্রতি-সংখ্যা থেকে O(log log N) amortized প্রতি-সংখ্যায় নেমে আসে। আর বড় ছবি: μ পেলে IE-র গোটা যোগ-বিয়োগ এক sum ∑ μ(d)·f(d)-এ গুটিয়ে যায়।

11. Step-by-step dry run

sieve দিয়ে mu[1..6] বানানো — শুরুতে সবার mu = 1, is_prime ধরে এগোই:

ধাপ	কী হলো	mu array (index 1..6)
শুরু	সব mu = 1	[_, 1, 1, 1, 1, 1, 1]
p = 2 (prime)	2-এর গুণিতক (2,4,6) sign উল্টাও	[_, 1, −1, 1, −1, 1, −1]
p = 2	4-এর গুণিতক (4) → mu = 0	[_, 1, −1, 1, 0, 1, −1]
p = 3 (prime)	3-এর গুণিতক (3,6) sign উল্টাও	[_, 1, −1, −1, 0, 1, 1]
p = 3	9-এর গুণিতক (>6, নেই)	[_, 1, −1, −1, 0, 1, 1]
p = 5 (prime)	5-এর গুণিতক (5) sign উল্টাও	[_, 1, −1, −1, 0, −1, 1]

চূড়ান্ত mu[1..6] = [1, −1, −1, 0, −1, 1]। মিলিয়ে দেখো section 5-এর table-এর সাথে — হুবহু। লক্ষ করো 6 প্রথমে 2-এর হাতে −1 হলো, তারপর 3-এর হাতে আবার উল্টে +1 (দুটো distinct prime, তাই +1)।

12. Python solution

def mobius_one(n):
    """একটা সংখ্যার μ(n) — trial division, O(√n)।"""
    if n == 1:
        return 1
    cnt = 0
    p = 2
    while p * p <= n:
        if n % p == 0:
            n //= p
            cnt += 1
            if n % p == 0:          # p আবার ভাগ করল -> square
                return 0
        p += 1
    if n > 1:
        cnt += 1                    # অবশিষ্ট বড় prime
    return -1 if cnt % 2 else 1


def mobius_sieve(N):
    """1..N সব μ একসাথে — O(N log log N)। mu[0] অব্যবহৃত।"""
    mu = [1] * (N + 1)
    is_comp = [False] * (N + 1)
    for p in range(2, N + 1):
        if not is_comp[p]:                       # p prime
            for j in range(p, N + 1, p):
                if j > p:
                    is_comp[j] = True
                mu[j] *= -1                      # একটা prime যোগ -> sign উল্টাও
            p2 = p * p
            for j in range(p2, N + 1, p2):
                mu[j] = 0                         # p² ভাগ করে -> 0
    return mu


# --- ছোট test গুলো (সব pass করা উচিত) ---
EXPECTED = [None, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]  # μ(1..12)

# এক-সংখ্যা version যাচাই
for n in range(1, 13):
    assert mobius_one(n) == EXPECTED[n], f"mobius_one({n}) ভুল"

# কিছু বড় মান
assert mobius_one(30) == -1       # 2·3·5
assert mobius_one(210) == 1       # 2·3·5·7
assert mobius_one(35) == 1        # 5·7
assert mobius_one(49) == 0        # 7²

# sieve version — এক-সংখ্যা version-এর সাথে 1..500 মেলাও
mu = mobius_sieve(500)
for n in range(1, 501):
    assert mu[n] == mobius_one(n), f"sieve বনাম one অমিল at {n}"

# multiplicative property: gcd=1 হলে μ(ab) = μ(a)μ(b)
from math import gcd
for a in range(1, 30):
    for b in range(1, 30):
        if gcd(a, b) == 1:
            assert mobius_one(a * b) == mobius_one(a) * mobius_one(b)

# জানা যোগফল: ∑_{d|n} μ(d) = [n == 1]  (Mobius-এর সংজ্ঞাগত ধর্ম)
def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]
for n in range(1, 30):
    s = sum(mobius_one(d) for d in divisors(n))
    assert s == (1 if n == 1 else 0), f"∑μ(d) ভুল at {n}"

print(mobius_one(6))              # 1
print(mobius_one(30))             # -1
print(mobius_sieve(12)[1:])      # [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
print("সব test pass!")

13. Line-by-line explanation

def mobius_one(n):
    if n == 1:
        return 1
    cnt = 0
    p = 2
    while p * p <= n:
        if n % p == 0:
            n //= p
            cnt += 1
            if n % p == 0:
                return 0

trial division — p পেলে একবার ভাগ করে distinct prime গোনা (cnt) বাড়াই, তারপর সঙ্গে সঙ্গে দেখি p আবার ভাগ করে কি না; করলে p² আছে, সোজা return 0।

    if n > 1:
        cnt += 1
    return -1 if cnt % 2 else 1

লুপ শেষে অবশিষ্ট n > 1 হলে সেটা একটা বড় prime — cnt বাড়াই। শেষে distinct prime সংখ্যা জোড় হলে +1, বিজোড় হলে −1।

def mobius_sieve(N):
    mu = [1] * (N + 1)
    ...
    for p in range(2, N + 1):
        if not is_comp[p]:
            for j in range(p, N + 1, p):
                if j > p: is_comp[j] = True
                mu[j] *= -1
            for j in range(p*p, N + 1, p*p):
                mu[j] = 0

প্রতিটা prime p-এর জন্য — তার সব গুণিতকের sign উল্টাই (একটা distinct prime যোগ হলো), আর গুণিতকদের composite হিসেবে mark করি। তারপর p²-এর সব গুণিতকের mu = 0 (square ভাগ করে)। এভাবে প্রতিটা সংখ্যা সঠিক ±1 বা 0 পায়।

বাকি test অংশে দুই version (one বনাম sieve) 1..500 মেলানো হয়, multiplicative property আর বিখ্যাত ∑_{d|n} μ(d) = [n=1] ধর্মও যাচাই হয়। সব ঠিক থাকলে সব test pass!।

14. Output walkthrough

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

1
-1
[1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
সব test pass!

mobius_one(6) → 1 (2·3, দুই prime)। mobius_one(30) → −1 (2·3·5, তিন prime)। mobius_sieve(12)[1:] → পুরো μ(1..12) array, যা section 5-এর table-এর সাথে হুবহু। তার আগে দুই version-এর মিল, multiplicative, আর divisor-sum সব assert pass — তাই সব test pass!।

15. Time complexity

mobius_one: O(√n) এক সংখ্যার জন্য (trial division)। mobius_sieve: O(N log log N) পুরো 1..N-এর জন্য — Eratosthenes-এর মতোই, প্রতিটা prime তার গুণিতকদের একবার ছোঁয়। তাই বহুবার μ লাগলে sieve বানিয়ে নাও (একবার O(N log log N), তারপর প্রতিটা lookup O(1)); শুধু একটা μ চাইলে O(√n) যথেষ্ট।

16. Space complexity

mobius_one: O(1) — শুধু কয়েকটা variable। mobius_sieve: O(N) — mu array আর is_comp array, দুটোই N+1 আকারের। CP-তে N যদি 10⁶-10⁷ হয়, এই array memory-তে রাখা যায়; তার বেশি হলে segmented বা per-query factorization ভাবতে হয়।

17. Common mistakes

1. square check ভুলে যাওয়া — কোনো prime দুবার এলে μ = 0; এই চেক বাদ দিলে square-যুক্ত সংখ্যায় ভুল ±1। mobius_one-এ n % p == 0 দ্বিতীয়বার, sieve-এ p²-লুপ — এটাই square ধরে।
2. distinct prime নয়, মোট prime গোনা — sign নির্ভর করে distinct prime সংখ্যার উপর (square-free হলে তো মোট = distinct, আর square থাকলে μ এমনিতেই 0)।
3. μ(1) ভুল ধরা — μ(1) = 1 (convention)। কোড আলাদা করে এটা handle না করলে ভুল হতে পারে।
4. sieve-এ sign আর zero-এর order গুলিয়ে ফেলা — আগে সব গুণিতকের sign উল্টাও, তারপর p²-গুণিতকদের 0; উল্টো করলে 0-গুলোও sign খেয়ে ফেলবে। (এখানে 0-লুপ পরে চলে, তাই নিরাপদ।)
5. বহুবার per-query factorize করা — অনেকবার μ লাগলে sieve বানাও; প্রতিবার O(√n) করা বড় N-এ ধীর।

18. Harder problems that inherit this idea

• CSES — Counting Coprime Pairs (https://cses.fi/problemset/task/2417) — সরাসরি ∑ μ(d) · (d-এর গুণিতক জোড়া) দিয়ে coprime জোড়া গোনা।
• Codeforces — square-free / gcd-sum / Mobius inversion problems (https://codeforces.com/problemset) — μ দিয়ে IE-র যোগ-বিয়োগ এক sum-এ নামানো।
• 128 (Euler Totient) আর 044 (Inclusion-Exclusion) — এই repo-রই ভিত্তি; μ আর φ একসাথে Mobius inversion-এ মেলে।

19. Pattern learned

Inclusion-exclusion encoding via Mobius — μ(n) = (−1)^(distinct prime) যদি square-free, নাহলে 0; আর "ঠিক gcd = 1 / square-free কতগুলো" গোনা = ∑ μ(d) · (সহজ গোনা). বড় শিক্ষা: IE-র গোটা যোগ-বিয়োগের choreography একটা ±1/0 function-এ encode করা যায় — তখন জটিল গোনা একটা sum-এ গুটিয়ে আসে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "μ(n): square থাকলে 0, নাহলে (−1)^(distinct prime); μ(1) = 1; multiplicative; বহুবার লাগলে sieve, একবার হলে √n factorize। কাজে লাগে IE-কে এক sum ∑ μ(d)·f(d)-তে নামাতে।" Signal: "coprime জোড়া গোনা" বা "square-free গোনা" বা Mobius inversion — দেখলেই μ মনে পড়বে।

পরের ধাপ → 130 — Modular Inverse Advanced (ext-gcd দিয়ে general inverse)। ভিত্তি → 128 — Euler Totient Advanced, 044 (Inclusion-Exclusion)।

ফিরে দেখা: এই 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।