025 — Sum of Divisors¶
024-এ exponent দিয়ে divisor গুনলে — এবার ঠিক সেই factorization থেকে divisor-দের যোগফল বের করব। মজার ব্যাপার, formula-টা প্রায় একই কাঠামোর, শুধু "কয় রকম" এর জায়গায় "সব power যোগ করলে কত"। ধীরে পড়ো — geometric series (
1 + p + p² + ...) কীভাবে ঢুকে পড়ে, সেটাই এই note-এর মূল সুর।
Source¶
- Original source: Classic exercise (harder variant: CSES — Sum of Divisors)
- Platform: CSES — https://cses.fi/problemset/task/1082
- Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- Difficulty: Medium
- Pattern: exponent formula — σ(n) = ∏ (1 + p + ... + p^e)
- Basic idea inherited from: 024 — Number of Divisors
1. Problem in simple words¶
একটা ধনাত্মক integer n দেওয়া আছে। বের করতে হবে n-এর সব divisor-এর যোগফল (sum of divisors, σ(n) দিয়ে লেখা) — মানে 1 থেকে n পর্যন্ত যত সংখ্যা n-কে নিঃশেষে ভাগ করে, তাদের সবার যোগফল।
উদাহরণ: 12-এর divisor 1, 2, 3, 4, 6, 12 — এদের যোগফল 1+2+3+4+6+12 = 28। তাই σ(12) = 28।
n নিজেও নিজের একটা divisor, তাই যোগফলে n থাকে। (কখনো কখনো "proper divisor sum" মানে n বাদ দিয়ে যোগফল চাওয়া হয় — সেটা পেতে শুধু σ(n) − n; কিন্তু এখানে আমরা n সহ পুরো যোগফল গুনছি।)
2. What is the math idea?¶
মূল idea 024-এর product formula-রই ভাই, factorization থেকে। n = p₁^e₁ · p₂^e₂ · ... হলে:
মানে প্রতিটা prime-এর জন্য তার সব power-এর যোগফল (1 থেকে p^e পর্যন্ত — একটা geometric series), তারপর সেই যোগফলগুলো সব গুণ করো।
কেন? 024-এ দেখেছি প্রতিটা divisor হলো p₁^a · p₂^b · ... রূপের (প্রতিটা prime থেকে একটা power বাছা)। সব divisor যোগ করা মানে এই গুণফলের সব combination যোগ করা — যা বীজগণিতে ঠিক ওই বন্ধনীগুলোর গুণফলের সমান (distributive law খুললে প্রতিটা পদ এক-একটা divisor)। "কয় রকম" এর জায়গায় "সব মিলিয়ে কত" — তাই (e+1) এর বদলে series-যোগফল।
3. Which basic idea does this inherit from?¶
এটা সরাসরি 024 (Number of Divisors)-এর উপর দাঁড়িয়ে, আর তার পেছনে 016 (Prime Factorization)। কাঠামো হুবহু এক — factorize করি, প্রতিটা prime-এর exponent পাই, তারপর একটা product বানাই।
একমাত্র পার্থক্য: 024-এ প্রতিটা prime থেকে গুণফলে যোগ হতো (e + 1) (পছন্দের সংখ্যা); এখানে যোগ হয় (1 + p + p² + ... + p^e) (power-গুলোর যোগফল)। তাই 024 ভালো বুঝে থাকলে এটা প্রায় এক পা — শুধু "গোনা" থেকে "যোগ করা"-য় বদল। আটকালে 024-এ ফিরে যাও।
4. Real-life analogy¶
ফিরে যাই 024-এর সেই পিৎজা-র দোকানে, কিন্তু এবার প্রশ্ন বদলেছে। আগে জিজ্ঞেস করেছিলাম "কত রকম পিৎজা সম্ভব"; এখন জিজ্ঞেস করছি "সব সম্ভাব্য পিৎজার দাম যোগ করলে কত"।
ধরো cheese-এর দাম power অনুযায়ী 1, 2, 4 টাকা (0,1,2 চামচ), olive-এর 1, 3 টাকা (0,1 চামচ)। প্রতিটা পিৎজার দাম = তার cheese-দাম × olive-দাম। সব পিৎজার দাম যোগ করতে গেলে দেখা যায় সেটা ঠিক (1+2+4) × (1+3) = 7 × 4 = 28 — কারণ বন্ধনী খুললে প্রতিটা পদ এক-একটা পিৎজার দাম।
ঠিক একইভাবে σ(n)-এ প্রতিটা prime-এর "দামের তালিকা" হলো তার power-গুলো (1, p, p², ...), আর সব divisor-এর যোগফল = সেই তালিকাগুলোর যোগফলের গুণফল।
5. Visual explanation¶
প্রথমে n = 12-এর divisor হাতে যোগ করি:
এবার formula কীভাবে একই 28 দেয় (প্রতি prime-এ power-যোগফল, তারপর গুণ):
12 = 2^2 · 3^1
2-এর power-যোগফল: 1 + 2 + 4 = 7 (2^0 + 2^1 + 2^2)
3-এর power-যোগফল: 1 + 3 = 4 (3^0 + 3^1)
σ(12) = 7 × 4 = 28 ✓
বন্ধনী খুললে প্রতিটা পদ = এক-একটা divisor:
(1+2+4)(1+3) = 1·1 + 2·1 + 4·1 + 1·3 + 2·3 + 4·3
= 1 + 2 + 4 + 3 + 6 + 12 = 28
6. Example input and output¶
n -> σ(n) factorization / হিসাব
--------------------------------------------------
1 -> 1 শুধু 1
2 -> 3 1 + 2
6 -> 12 1+2+3+6 = (1+2)(1+3)
12 -> 28 (1+2+4)(1+3)
16 -> 31 2^4 -> 1+2+4+8+16
28 -> 56 1+2+4+7+14+28 (perfect number: σ = 2n!)
37 -> 38 prime -> 1 + 37
360 -> 1170 2^3·3^2·5 -> 15·13·6
দুটো জিনিস খেয়াল করো: prime p-এর σ = p + 1 (37 → 38)। আর 28 একটা perfect number — তার proper divisor-দের (নিজে বাদে) যোগফল ঠিক নিজে (1+2+4+7+14 = 28), মানে σ(28) = 2×28 = 56।
7. Brute force thinking¶
formula মাথায় না এলে, সবচেয়ে সরল — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা দিয়ে n ভাগ করে দেখি, ভাগ গেলে সেটা যোগফলে যোগ করি:
def sum_divisors_brute(n):
total = 0
for d in range(1, n + 1):
if n % d == 0:
total += d # divisor পেলে যোগফলে যোগ
return total
একদম সংজ্ঞা: 1..n-এর প্রতিটা d-র জন্য n % d == 0 হলে divisor, total-এ যোগ করি। সরল, ঠিক উত্তর। (চালাক brute force: √n পর্যন্ত খুঁজে প্রতিবার d আর n // d দুটোই যোগ — 012/024-এর জোড়ার কৌশল, O(√n)। কিন্তু এখানে factorization-formula পথ দেখব।)
8. Why brute force may be slow¶
সরল loop ঠিক n বার ঘোরে। ছোট n-এ ঠিক আছে, বিশাল n-এ অসম্ভব:
n = 10^6 -> 10^6 বার (ঠিক আছে)
n = 10^9 -> 10^9 বার (ধীর)
n = 10^12 -> 10^12 বার (অসম্ভব — TLE)
√n / formula -> n=10^12 হলেও ~10^6 ধাপ (এক লহমায়)
মূল সমস্যা 024-এর মতোই: 1..n পুরোটা ঘোরা। divisor-রা √n-এর এপারে জোড়ায় বসে, আর factorization √n-এই শেষ — তাই formula পথে কাজ √n-এ নেমে আসে, n যত বড়ই হোক।
9. Better thinking¶
মূল insight — divisor যোগ করতে প্রতিটা divisor খুঁজতে হয় না; factorization জানলে প্রতিটা prime-এর power-যোগফল বের করে সেগুলো গুণ করলেই σ।
factorize করার সময়ই প্রতিটা prime-এর exponent গুনি, আর সাথে সাথে তার power-যোগফল (1 + p + p² + ... + p^e) হিসাব করে মূল গুণফলে গুণ করি:
def sum_divisors(n):
total = 1
p = 2
while p * p <= n:
if n % p == 0:
power_sum, pw = 1, 1
while n % p == 0:
n //= p
pw *= p
power_sum += pw # 1 + p + p^2 + ...
total *= power_sum
p += 1
if n > 1: # বাকি n নিজেই prime (exponent 1)
total *= (1 + n) # 1 + p
return total
মূল চালাকি: power-যোগফলটা loop-এর ভেতরেই গড়ে তুলি — pw রাখে current power (p, p², ...), আর power_sum-এ যোগ করতে থাকি। আলাদা করে geometric series formula মনে রাখার দরকার নেই, যোগ করতে করতেই হয়ে যায়।
10. Thinking tweak¶
আসল "আহা!" মুহূর্ত: σ হলো 024-এরই formula, শুধু প্রতিটা prime-এর অবদান "(e+1) রকম পছন্দ" থেকে বদলে "তার সব power-এর যোগফল" হয়ে গেছে।
মূল মোচড়টা distributive law-এ: (1+p+p²)(1+q) খুললে প্রতিটা পদ ঠিক এক-একটা divisor — তাই বন্ধনীগুলোর গুণফলই পুরো যোগফল। গোনা (count) আর যোগ (sum) — দুটোই একই "প্রতি prime-এ একটা মান, তারপর গুণ" কাঠামোয় বসে, শুধু ভেতরের মানটা আলাদা। এই "একই কাঠামো, ভেতরটা বদলাও" দৃষ্টিভঙ্গি মাথায় রাখো — divisor product, even-divisor sum ইত্যাদিও এভাবে বেরোয়।
11. Step-by-step dry run¶
চলো sum_divisors(12) ধীরে চালাই। শুরুতে total = 1, n = 12:
p = 2-এর ভেতরের while ধাপে ধাপে:
| ভেতরের ধাপ | n হয় | pw (×p) | power_sum (+pw) |
|---|---|---|---|
| শুরু | 12 | 1 | 1 |
| 1 | 6 | 2 | 1 + 2 = 3 |
| 2 | 3 | 4 | 3 + 4 = 7 |
2 শেষ — total *= 7 → total = 7। বাইরের loop: p = 3-এ 3·3 > 3 (এখন n = 3), loop শেষ।
Loop-এর পরে n = 3 > 1, তাই বাকি 3 একটা prime: total *= (1 + 3) → 7 × 4 = 28।
σ(12) = 28 — section 5-এর হাতে-গোনা 1+2+3+4+6+12-এর সাথে হুবহু মিলল। power_sum 7 = 1+2+4, ঠিক 2-এর সব power-এর যোগ।
12. Python solution¶
def sum_divisors(n):
"""n-এর সব divisor-এর যোগফল σ(n) = ∏ (1 + p + ... + p^e)।"""
if n <= 0:
return 0
total = 1
p = 2
while p * p <= n:
if n % p == 0:
power_sum, pw = 1, 1
while n % p == 0: # 1 + p + p^2 + ... গড়ি
n //= p
pw *= p
power_sum += pw
total *= power_sum
p += 1
if n > 1: # বাকি n নিজেই prime (exponent 1)
total *= (1 + n)
return total
def sum_divisors_brute(n):
"""সংজ্ঞা ধরে: 1..n-এ divisor যোগ — formula verify করতে।"""
return sum(d for d in range(1, n + 1) if n % d == 0)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sum_divisors(1) == 1
assert sum_divisors(2) == 3
assert sum_divisors(6) == 12 # perfect number: σ = 2n
assert sum_divisors(12) == 28
assert sum_divisors(16) == 31 # 1+2+4+8+16
assert sum_divisors(28) == 56 # perfect number
assert sum_divisors(37) == 38 # prime -> 1 + p
assert sum_divisors(360) == 1170 # 15·13·6
assert sum_divisors(7919) == 7920 # বড় prime -> 1 + p
# formula আর brute force ছোট range-এ মিলছে কি না
for m in range(1, 200):
assert sum_divisors(m) == sum_divisors_brute(m)
print(sum_divisors(12)) # 28
print(sum_divisors(28)) # 56
print(sum_divisors(360)) # 1170
print("সব test pass!")
13. Line-by-line explanation¶
total শুরুতে 1 (গুণফলের neutral মান)। √n পর্যন্ত প্রতিটা সম্ভাব্য prime p দেখি (factorization-এর মতো)।
p যদি n-কে ভাগ করে, তার power-যোগফল গড়ি। power_sum শুরুতে 1 (= p⁰), pw রাখে current power। প্রতিবার p দিয়ে ভাগ হলে pw *= p (পরের power), আর power_sum += pw — তাই গড়ে ওঠে 1 + p + p² + ...।
এই prime-এর পুরো অবদান (power-যোগফল) মূল গুণফলে গুণ।
Loop শেষে n যদি এখনো 1-এর বেশি হয়, সেটা n-এর বড় prime factor (exponent 1), তাই তার power-যোগফল 1 + n দিয়ে গুণ। (যেমন n = 14 = 2×7: loop-এ 2 → total = 3, তারপর 7 এই লাইনে total = 3×8 = 24 = 1+2+7+14 ✓)
sum_divisors_brute সংজ্ঞা ধরে যোগ করে; for m in range(1, 200) loop দুই version মিলিয়ে formula যাচাই করে। সব ঠিক থাকলে শেষে সব test pass!।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন: σ(12) = 28 (section 11-এর dry run)। দ্বিতীয়: σ(28) = 56 — 28 perfect number, তাই σ = 2×28। তৃতীয়: σ(360) = 1170 — 360 = 2³·3²·5 → (1+2+4+8)(1+3+9)(1+5) = 15·13·6 = 1170। তার আগে সব assert, এমনকি 1..199 জুড়ে formula-vs-brute মিল — সব চুপচাপ pass, তাই শেষে সব test pass!।
15. Time complexity¶
O(√n) — মূল loop p চলে 2 থেকে √n পর্যন্ত (factorization-এর খরচ); ভেতরের while-গুলো মিলিয়েও মোট কাজ O(√n)-এই থাকে। তাই n = 10¹² হলেও √n = 10⁶ — এক লহমায় শেষ। সরল brute force-এর O(n)-এর তুলনায় বিশাল উন্নতি।
16. Space complexity¶
O(1) — শুধু total, p, power_sum, pw, আর পরিবর্তিত n — গুটিকয় variable। divisor-দের কোনো list বানাচ্ছি না, যোগফল চলতে চলতে হিসাব হয়। input ছাড়া আলাদা জায়গা প্রায় শূন্য।
17. Common mistakes¶
total0 থেকে শুরু করা — এটা গুণফল, তাই neutral মান 1 থেকে শুরু; 0 থেকে শুরু করলে উত্তর সবসময় 0।- power-যোগফল ভুল গড়া —
1 + p + ... + p^eচাই, কিন্তুpwশুরু 1 আরpower_sumশুরু 1 না রাখলে p⁰ পদটা বাদ পড়ে। ক্রম খেয়াল করো: আগেpw *= p, তারপরpower_sum += pw। - শেষের
if n > 1ভুলে যাওয়া — n-এর বড় prime factor (যেমন 14-এর 7, বা 7919) এই লাইন ছাড়া যোগফলে আসে না, σ কম হয়। - proper divisor sum-এর সাথে গুলিয়ে ফেলা — এখানে σ-তে n নিজেও আছে; "নিজে বাদে" চাইলে আলাদাভাবে σ(n) − n নিতে হবে।
- divisor list বানিয়ে যোগ করা — শুধু যোগফল চাইলে list বানানোর দরকার নেই; power-যোগফলের গুণফলই যথেষ্ট, memory বাঁচে।
18. Harder problems that inherit this idea¶
- CSES — Sum of Divisors (https://cses.fi/problemset/task/1082) — 1 থেকে n পর্যন্ত সব সংখ্যার σ-এর যোগফল, modular arithmetic-এ; এই formula + Level 2 মিলিয়ে।
- CSES — Divisor Analysis (https://cses.fi/problemset/task/2182) — divisor count, sum, product একসাথে modular-এ; এই note-এর সরাসরি বড় ভাই।
- Project Euler 21 — Amicable numbers (https://projecteuler.net/problem=21) — proper divisor sum (σ(n) − n) দিয়ে amicable জোড়া খোঁজা; common pattern।
19. Pattern learned¶
Divisor sum via exponents — σ(n) = ∏ (1 + p + ... + p^e)। মূল reusable টুকরো: factorization + প্রতি prime-এ power-যোগফল গুণ; শেষে if n > 1 হলে × (1 + n)। আর বড় শিক্ষা: count আর sum একই "প্রতি prime-এ একটা মান → গুণ" কাঠামোয় বসে, শুধু ভেতরের মান বদলায় (distributive law-এর জোরে)।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "divisor যোগফল = factorize করো, প্রতি prime-এ (1 + p + ... + p^e) গুণ করো (total = power_sum), শেষে n>1 হলে × (1+n)। 'সব গুণনীয়কের যোগফল' দেখলেই এই formula — 024-এরই ভাই, count-এর (e+1) এর জায়গায় power-যোগফল।"*
পরের ধাপ → Level 1 শেষ! এবার ../README.md-এ ফিরে বাকি problem ঝালিয়ে Level 2 (modular arithmetic)-এর দিকে। শিকড় → 024 — Number of Divisors।
ফিরে দেখা: এই 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" লেখা হয়েছে।