Prime Counting Function and Chebyshev Bounds

The distribution of primes plays a central role in number theory. The famous mathematician Gauss had conjectured that the number of primes between \(1\) and \(n\) is roughly \(n/\log n\). This estimation gets more and more accurate as \(n\to \infty\). We use \(\pi(n)\) to denote the number of primes between \(1\) and \(n\). So, mathematically, Gauss’s conjecture is equivalent to the claim

\[\lim_{n\to\infty}\frac{\pi(n)}{n/\log n}=1\]

Continue reading Prime Counting Function and Chebyshev Bounds

Multiplying Two Polynomials with Fast Fourier Transform

Polynomial multiplication is one of the most important problems in mathematics and computer science. It can be formally defined as follows:

You are given two polynomials roughly of equal size\[A(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}\]\[B(x)=b_0+b_1x+\dots+b_{n-1}x^{n-1}\]find a polynomial \[C(x)=c_0+c_1x+\dots+c_{2n-2}x^{2n-2}\] such that \(A(x)\cdot B(x)=C(x)\). At first, this may look like an easy problem, Continue reading Multiplying Two Polynomials with Fast Fourier Transform

No form of beauty is as flawless, as abstract, or as perennial as the mathematical beauty that derives from unassailable logical perfectness, for a mathematical proof is not earthly science, but a poetry written in logic.
[ –Adib Hasan 😛 ]

Generating All Subsets of Size k in Python


Suppose you are given a set \(S\) with \(n\) elements and you need to generate every subset of size \(k\) from it. For instance, if \(S=\{3,4,5\}\) and \(k=2\), then the answer would be \(\{3,4\}\), \(\{3,5\}\), \(\{4,5\}\). So, how would you do that in Python?

First of all, this is a really simple exercise. Stuff like this often comes up when someone writes a moderately large script. I wanna talk about this one in particular because it has a combinatorial solution. Continue reading Generating All Subsets of Size k in Python

Lie Detectors and the Story of Halting Turing Machines


Is it possible to design a machine that detects lies? Sure, people have already built devices called polygraphs that monitor blood pressure, respiration, pulse etc. to determine if a person is giving false information. However, that is not same as “detecting lies” because polygraphs merely measure physical effects of telling lies. On the top of that, they are hella inaccurate. I am talking about REAL lie detectors, ie. machines that can instantly validate the statements themselves. Can we actually make such machines? (*insert new startup idea*) Continue reading Lie Detectors and the Story of Halting Turing Machines

ভোরের কুয়াশাস্নাত রোদের আঁচল
লুকিয়ে রেখো আমার কিছু ব্যর্থতা।
অর্ধরাতের জন্য পুরোনো জৌলুশটুকু বড্ড প্রয়োজন।
আজ আমার মন ভাল নেই।


সেই দিনগুলো ছিল উচ্ছল,
ছিল পলাশীর মত উত্তাল,
ছিল আকাশের তেজী রোদ্দুর,
নগরীর বেপরোয়া কোলাহল।
সেখানে ঘড়ি মেনে আসে রাত্রি
যেমন জাহাজের কোন যাত্রী
মৃত ডাহুকের মত নিশ্চুপ
জোছনার ফুল ঝরে টুপ টুপ
বুকের পাঁজরে আহত আবেগ
প্রেমিকার চোখে ভাসে অভিযোগ।
যদি দিগন্ত বেয়ে চুপিসারে
কোন ভালবাসা এসে কড়া নাড়ে
তবে সঁপে দিও তাকে যৌবন,
দিও অপরাধমাখা চুম্বন
যেভাবে সকালের ফোটা পলাশে
বসন্তের রঙ মেশে সহাসে।



প্রতিটি ক্লান্ত দিনের শেষে
পরমকাঙ্ক্ষিত বিকেলের মত
তোমাকে আমার প্রয়োজন।

প্রতিটি প্রিয় ছুটির দিনে
আলস্যমাখা দিবানিদ্রার মতো
তোমাকে আমার প্রয়োজন।

একবার এসো না এই শহরে!
তোমাকে আমার বড্ড প্রয়োজন।

A Special Case of Zsigmondy’s Theorem

Theorem (Zsigsmondy): 

  1. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) for all positive integers \(k< n\) with the following exceptions:
    • \(n = 2\) and \(a+b\) is a power of two.
    • \(n=6, a=2, b=1\).
  2. For two coprime positive integers \(a\) and \(b\) and for any positive integer \(n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) for all positive integers \(k< n\) with the following exception:
    • \(n=3, a=2, b=1\).

This theorem is very helpful in solving many olympiad number theory problems. However, its use is often frowned upon, as this theorem is quite hard to prove using only elementary mathematics. (I am aware of the proof using Cyclotomic Polynomials, but that’s not “elementary enough” in my opinion.)

In olympiad mathematics, one can get away in most of the cases by just using this theorem for a fixed pair of \(n\) and \(k\). This modification allows us to provide a very simple proof using LTE. Here I’ll restate this particular case, and then prove the first part. The second part can be proven analogously.

Theorem (Zsigsmondy Special Case): 

  1. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n-b^n\) has a prime divisor that does not divide \(a^k-b^k\) with the following exception:
    • \(n = 2, k=1\) and \(a+b\) is a power of two.
  2. For two coprime positive integers \(a\) and \(b\) and any two positive integers \(n\) and \(k\) with \(k<n\), \(a^n+b^n\) has a prime divisor that does not divide \(a^k+b^k\) with the following exception:
    • \(n=3, k=1,a=2, b=1\).

Proof of 1:

Suppose \(a^n-b^n\) and \(a^k-b^k\) share same set of prime divisors. This implies \(a^n-b^n\) and \(a^{\gcd(n,k)}-b^{\gcd(n,k)}\) also share same set of prime divisors. Assuming \(A=a^{\gcd(n,k)}\) and \(B=b^{\gcd(n,k)}\), we could follow the rest of this argument and get to a contradiction. So, without loss of generality, we may assume \(k=1\).

Now we consider two cases:

Case 1: \(n\) is a power of \(2\).
If \(n=2\) and \(a+b\) is a power of two, we arrive at one of the listed exceptions. Now note that,
\(\begin{align*}&\gcd(a+b, a^2+b^2)\\
=&\gcd(a+b, (a+b)^2-a^2-b^2)\\
This implies both \(a+b\) and \(a^2+b^2\) can’t be powers of two unless \(a+b=2\implies a=b=1\). Hence at least one of them must have an odd prime divisor. Furthermore, this prime divisor does not divide \(a-b\) since \(\gcd(a-b, a^2+b^2)=\gcd(a-b,2)\) (following the previous steps). However, if \(n>2\), then \(a^2+b^2|a^n-b^n\), implying that odd prime will divide \(a^n-b^n\). This is a contradiction.

Case 2: \(n=2^md\) with \(d>1\) being odd.
Without loss of generality, we may assume \(n>1\) is odd, since \(a^d-b^d|a^n-b^n\) and it is sufficient to show that \(a^d-b^d\) has a prime divisor that does not divide \(a-b\).  From LTE, \(v_p(a-b)+v_p(n)=v_p(a^n-b^n)\) for each odd prime \(p|a-b\). Furthermore, \[\frac{a^n-b^n}{a-b}\equiv na^{n-1}\equiv 1\pmod 2\] implying \(v_2(a-b)=v_2(a^n-b^n)\). Therefore, we can conclude \[\frac{a^n-b^n}{a-b}=\prod_{p|\gcd(n,a-b)}p^{v_p(n)}\leq n\] which is impossible for \(n>1\). This raises another contradiction and we are done.

কীভাবে প্রোটিন তৈরি হয়?

আগামী কয়েকদিন আমি কিছু জীববিজ্ঞানের বিষয় নিয়ে পোস্ট করব। আমার আনুষ্ঠানিক পড়ার বিষয়ের সাথে এগুলোর খুব একটা সংযোগ নেই, যদিও অনানুষ্ঠানিক একাডেমিক কৌতূহল স্বতঃস্ফূর্তভাবেই ছিল। আমি মোটামুটি নিশ্চিত আগামী তিন মাসের মাঝে এসবের  বেশিরভাগই আমার মনে থাকবে না। তাই এগুলো লিখে রাখার চেষ্টা করা হল। সহজবোধ্যতার খাতিরে কিছু ক্ষেত্রে টপিকগুলো অনেকখানি সরলীকরণ করা হবে। এগুলো কারও কৌতূহল মেটাবার খোরাক হতে পারে, কিন্তু রেফারেন্স হিসেবে মোটেই ব্যবহার উপযোগী নয়। যদি কারও বিস্তারিত জানার ইচ্ছে থাকে, তবে এমাইটির কোর্স ৭.০১২ বা ৭.০১৬ অনলাইনে দেখতে পরামর্শ দেওয়া হল।

প্রোটিন এবং এমিনো এসিড

জীবন নিয়ে আলোচনা শুরু করতে হয় এমিনো এসিড দিয়ে। এগুলো কোষের অসংখ্য ফাংশনর জন্য অপরিহার্য। এমিনো এসিড হচ্ছে কিছু জৈবিক অণু যাদের মাঝে একটি এমিন গ্রুপ (\(-NH_2\)), একটি কার্বক্সিলিক এসিড গ্রুপ (\(-COOH\)) এবং একটি সাইড চেইন (\(-R\)) দেখতে পাওয়া যায়। যদিও প্রায় ৫০০ টির মত এমিনো এসিড এখন পর্যন্ত আবিষ্কৃত হয়েছে, এদের মাঝে মাত্র ২০ টিকে জীবের জেনেটিক কোডে পাওয়া যায়।

এমিনো এসিডের চার্ট। (ছবির সোর্স:

এমিনো এসিডের একটি বিশেষ বৈশিষ্ট্য হচ্ছে পাশাপাশি দুইটি এমিনো এসিডের একটির এমিন গ্রুপ এবং অন্যটির কার্বক্সিলিক গ্রুপ থেকে এক অণু পানি অপসারিত হয়ে এরা পরস্পরের সাথে যুক্ত হতে পারে। এমন বন্ধনকে জীববিজ্ঞানে বলা হয় পেপটাইড বন্ধন । উপযুক্ত পরিবেশে একের পর এক এমিনো এসিড পরস্পরের সাথে যুক্ত হয়ে বিশাল বড় এমিনো এসিডের শেকল তৈরি করতে পারে। এমন শেকলকে বলা হয় পলিপেপটাইড চেইন

পেপটাইড বন্ধন। (ছবির সোর্স:

প্রোটিন হচ্ছে এমন এক বা একাধিক পলিপেপটাইড চেইনের সমন্বয়ে গঠিত বিশাল এক জৈবিক অণু। কোন পলিপেপ্টাইড চেইনের যেকোনো অবস্থানে বিশটি এমিনো এসিডের যেকোনোটি বসতে পারে। তাই মাত্র \(30\) টি পলিপেপ্টাইড চেইনের ভিন্ন ভিন্ন কম্বিনেশন হতে পারে \(20^{30}\) টি! যেকোন অর্গানিজমের প্রোটিনে এর চেয়ে বড় পপিপেপ্টাইড চেইন অহরহই দেখা যায়। এজন্যই যেকোন অর্গানিজমে এত ভিন্ন ভিন্ন প্রোটিন পাওয়া সম্ভব। তবে মনে রাখতে হবে শুধু এমিনো এসিডের বৈচিত্র্য নয়, প্রোটিনের ত্রিমাত্রিক আকারও এর কার্যকারীতার পেছনে ভূমিকা পালন করে। এজন্যই অনেক প্রোটিন তাপ, pH প্রভৃতিতে সংবেদনশীল (sensitive) হয়ে থাকে। যেমন- তাপে অনেক প্রোটিনের পলিপেপ্টাইড চেইনগুলো বিমুক্ত হয়ে যায় এবং তাপ সরিয়ে নিলেও আবার সেগুলো পূর্বের অবস্থায় ফেরত আসে না। এজন্যই ডিম সেদ্ধ করলে জমাট বেঁধে যায়।

প্রতিটি প্রোটিন বানানোর রেসিপি লিখা থাকে জীবের ডিএনএ বা আরএনএতে। কিন্তু সব কোষে একই ডিএনএ থাকা সত্ত্বেও সব প্রোটিন সব কোষে তৈরি হয় না। তাই প্রোটিন বানানো বুঝতে হলে আমাদের ডিএনএ এবং আরএনএ সম্পর্কে কিছুটা জেনে নেওয়া প্রয়োজন।

ডিএনএ এবং আরএনএ আসলে কী

যেকোন অর্গানিজমকে আসলে কম্পিউটারের সাথে তুলনা করা যায়। কম্পিউটারে যখন কোন তথ্য সংরক্ষণ করে রাখার প্রয়োজন হয়, আমরা ব্যবহার করি হার্ডডিস্ক। তেমনি করে প্রতিটি জীবের সমস্ত জিনগত তথ্য প্রকৃতি সুরক্ষিত রাখে সেই জীবের ডিএনএতে। হার্ডডিস্কে তথ্য লিখে রাখা হয় 0 আর 1 দিয়ে। আর ডিএনএতে তথ্য লিখে রাখা হয় চারটি নাইট্রোজেনাস বেইস পেয়ার দিয়ে, যাদের নাম এডিনিন (A), থাইমিন (T), গুয়ানিন (G) এবং সাইটোসিন (C). খুব গুরুত্বপূর্ণ তথ্য না হলে আমরা সাধারণত গাদা গাদা ব্যাকআপ রাখি না, কিন্তু ডিএনএর সকল তথ্যের ব্যাকআপ রাখা হয় জীবের প্রতিটি কোষে।

ডিএনএর গঠন। (ছবির সোর্স:

ডিএনএর পূর্ণরূপ হল ডিঅক্সি রাইবোনিউক্লিয়িক এসিড। ডিএনএর তিনটি অংশ– নাইট্রোজেনাস বেইস, পাঁচ কার্বনের একটি বিশেষ চিনি (ডিঅক্সি রাইবোজ) এবং ফসফেট গ্রুপ। ডিএনএতে সাপের মতো দুইটি আঁকাবাঁকা সুতায় ফসফেট গ্রুপ আর চিনির ভিতের ওপর বেইসগুলো সারিবদ্ধভাবে সাজানো থাকে। দুইটি সুতার বিপরীত বেইসগুলো হাইড্রোজেন বন্ধনের কারণে পরস্পরের সাথে যুক্ত। ডিএনএর দুইটি সুতা কমপ্লিমেন্টারি, অর্থাৎ একে অন্যের ছাঁচের মত। এক সুতায় A-র বিপরীতে অন্য সুতায় সবসময় T, এবং C-এর বিপরীতে অন্য সুতায় সবসময় G বসে।

ডিঅক্সি রাইবোজের কার্বনগুলোকে জৈবযৌগের নামকরণের নিয়মে নাম্বার দেওয়া হলে ডিএনএর প্রত্যেকটি সুতার এক মাথায় 5′ বিশিষ্ট কার্বন এবং অন্য মাথায় 3′ বিশিষ্ট কার্বন পড়ে। এই অনুসারে  মাথা দুইটিকে 5′ মাথা এবং 3′ মাথা বলা হয়। তবে  দুইটি কমপ্লিমেন্টারি সুতার একই মাথা বিপরীত দিকে থাকে।

ডিএনএ ছাড়াও আরও এক রকমের নিউক্লিয়িক এসিড আছে, যার নাম রাইবোনিউক্লিয়িক এসিড। এতে ডিঅক্সি রাইবোজের পরিবর্তে চিনি হিসেবে থাকে রাইবোজ, এবং থাইমিনের (T) পরিবর্তে বসে ইউরাসিল (U). এই অল্প একটুখানি পরিবর্তনের জন্য ডিএনএ এবং আরএনএর চরিত্রে রাতদিন পার্থক্য হয়ে যায়। আরএনএর মোটেই ডিএনএর মত সুনির্দিষ্ট কোন গঠন নেই। এরা বিভিন্ন রকমের হতে পারে (যেমন- মেসেঞ্জার আরএনএ, ট্রান্সফার আরএনএ, রাইবোসোমাল আরএনএ প্রভৃতি) এবং কোষের ভিন্ন ভিন্ন কাজে এরা ব্যবহৃত হয়। আরএনএ ডিএনএর তুলনায় অনেক বেশি সক্রিয় হয় এবং স্থিতিশীলতাও অনেক কম। এজন্য বংশগত তথ্য সংরক্ষণে কোষ সাধারণত আরএনএ ব্যবহার করে না। তবে কিছু ক্ষেত্রে এই বৈশিষ্ট্যগুলো জীবের বেঁচে থাকার জন্য সহায়ক। যেমন- আরএনএ থাকার কারণে ফ্লু ভাইরাস খুব সহজে নিজের চেহারায় পরিবর্তন এনে আমাদের শরীরের প্রতিরক্ষা ব্যবস্থাকে বার বার ফাঁকি দিতে পারে।

ডিএনএ এবং জিন

ডিএনএ একটি জীবের বংশগত সকল তথ্য সংরক্ষণ করে। কিন্তু বেঁচে থাকার জন্য তথ্য শুধু সংরক্ষণ করে রাখাই যথেষ্ট নয়। এই তথ্য ব্যবহারও করতে পারা প্রয়োজন। সেটা কীভাবে করা যায়? উত্তরটা হচ্ছে প্রোটিন বানিয়ে!

একটা অর্গানিজমের সম্পূর্ণ ডিএনএ অনেক লম্বা। যেমন- মানুষের পূর্ণাঙ্গ ডিএনএর দৈর্ঘ্য প্রায় ছয় ফুট! এই সবটুকু ডিএনএতে কিন্তু প্রোটিন বানানোর রেসিপি লিখা থাকে না, বরং কিছু কিছু অংশে থাকে। এগুলোই হচ্ছে জিন (Gene). আরেকটু একাডেমিক ভাষায় জিন হচ্ছে ডিএনএর এমন কোন খন্ড যা ফাংশনাল কোন অণুর কোড ধারণ করে। একটি জিনের বেশ কয়েকটি অংশ:

  1. প্রোমোটার (Promoter)
  2. আন্ট্রান্সলেটেড রিজিয়ন (Untranslated Region or UTR)
  3. ওপেন রিডিং ফ্রেম
  4. টার্মিনেটর

জিনের স্ট্রাকচার। (ছবির সোর্স:

এছাড়া ট্রানস্ক্রিপশন ফ্যাক্টর নামের কিছু প্রোটিন কোন জিনের প্রকাশের (expression) জন্য অপরিহার্য। যখন কোষের কোন জিন থেকে প্রোটিন বানানোর প্রয়োজন হয়, অনেকগুলো ভিন্ন ভিন্ন  ট্রান্সক্রিপশন ফ্যাক্টর জিনটির প্রোমোটার অংশে যুক্ত হয়। সব ট্রানস্ক্রিপশন ফ্যাক্টর সব কোষে থাকে না। তাই সব জিন সব কোষে প্রকাশিত হয় না।

প্রোটিন সিন্থেসিস

প্রায় পঞ্চাশটির মত ট্রান্সক্রিপশন ফ্যাক্টর প্রোমোটার অংশে যুক্ত হলে আরএনএ পলিমারেজ (RNA Polymerase) নামের একটি এনজাইম ডিএনএ থেকে সেই জিনের কোড কপি করে মেসেঞ্জার আরএনএ তৈরি করা শুরু করে। তবে ডিএনএতে একটি বিশেষ সিকুয়েন্স পাওয়ার আগে এই কপি করা শুরু হয় না। এই স্থানটির নাম স্টার্ট কোডন (Start Codon). অধিকাংশ অর্গানিজমে এটি হচ্ছে ATG. প্রোমোটার এবং স্টার্ট কোডনের মাঝের অংশটি মেসেঞ্জার আরএনএতে কপি করা হয় না। একে বলে আনট্রান্সলেটেড রিজিয়ন বা ইউটিআর। আরএনএ পলিমারেজ স্টার্ট কোডন থেকে পরের বেইসগুলো একটির পর একটি করে মেসেঞ্জার আরএনএতে কপি করতে থাকে। পরবর্তীতে এনজাইমটি ডিএনএতে একটি বিশেষ স্থানে গেলে কপি করা সমাপ্ত হয়, এবং মেসেঞ্জার আরএনএটি মুক্ত হয়। এই স্থানটির নাম টার্মিনেটর। ইউটিআর এবং টার্মিনেটরের মধ্যবর্তী অংশটির নাম ওপেন রিডিং ফ্রেম।

ওপেন রিডিং ফ্রেমে কিছু স্থান থাকে যেগুলো প্রোটিনের কোন অংশের কোড করে না। এদের বলে ইন্ট্রন (Intron). বাকি অংশগুলোকে বলে এক্সন (Exon). সদ্য সৃষ্ট মেসেঞ্জার আরএনএ থেকে ইন্ট্রনগুলোকে কেটে বাদ দেওয়া হয়, এবং অবশিষ্ট অংশগুলোকে জোড়া লাগানো হয়। মধ্যবর্তী এক বা একাধিক এক্সনও বাদ যেতে পারে। এভাবে একই জিন থেকে কোষ একাধিক প্রোটিন তৈরি করতে পারে। এরপরে মেসেঞ্জার আরএনএগুলোকে বিকৃতির হাত থেকে রক্ষার জন্য 5′ মাথায় একটি ক্যাপ এবং 3′ মাথায় অনেকগুলো A দিয়ে তৈরি একটি লেজ জুড়ে দেওয়া হয়।

এরপর এই পরিপক্ক (mature) মেসেঞ্জার আরএনএগুলো কোষের নিউক্লিয়াস ছেড়ে বাইরে বেরিয়ে আসে। কোষের রাইবোজোম তখন সেই মেসেঞ্জার আরএনএর কোড পড়ে পর পর তিন বেইসের প্রতিটি কম্বিনেশনের  জন্য একটি নির্দিষ্ট এমিনো এসিড সংযুক্ত করে এমিনো এসিডের একটি শেকল  বা পলিপেপ্টাইড চেইন তৈরি করে। এই প্রক্রিয়াটির নাম ট্রান্সলেশন বা অনুবাদ।


এমিনো এসিড কোডন চার্ট। (ছবির সোর্স:

মেসেঞ্জার আরএনএতে কিছু বিশেষ তিন বেইসের কোড থাকে যারা পলিপেপ্টাইড চেইনের সূচনা ও সমাপ্তি নির্দেশ করে। সূচনা কোড পেলে রাইবোজোম পলিপেপ্টাইড চেইন তৈরি করা শুরু করে, এবং সমাপ্তি কোড পেলে পলিপেপ্টাইড চেইনটিকে রাইবোজোম মুক্ত করে দেয়। পরবর্তীতে এক বা একাধিক পলিপেপ্টাইড চেইনকে বিশেষভাবে ভাঁজ (folding) করে কাঙ্ক্ষিত প্রোটিনের একটি অণু তৈরি হয়। এই প্রোটিনকে প্লাজমা মেমব্রেন বা কোষের বাইরে পাঠানোর প্রয়োজন পড়লে বিভিন্ন পলিপেপ্টাইডের সিগনাল সিকুয়েন্স যুক্ত হয়। কোষে কিছু সিগনাল রিকগনিশন পার্টিকেল (এসআরপি) থাকে যারা এই বিশেষ বিশেষ সিগনাল সিকুয়েন্সের সাথে যুক্ত হয়ে ঠিক ঠিক স্থানে প্রোটিনকে প্রেরণ করতে সাহায্য করে।

এভাবেই তৈরি হয় একেকটি প্রোটিন!