Number Theory - Part 2 (Code + Source)

Euler Totient : 

Source : Link1 Link2

Code : 

For 20 Digit Number - 

Extended Euclidean Algorithm : 

Source : Link1 Link2

Code : 

Linear Diophantine Equation : 

Source : Link1 Link2

Code : 

PIE : 

 See this blog...!

Number Theory - Part I (Code + Source)

Sieve Of Eratosthenes:

Source: Link

Code:

Bitwise Sieve:

Code:

যখন প্রাইম নাম্বার  ১০^৮ পর্যন্ত বের করতে হবে তখন এটা ব্যবহার করব।

Segmented Sieve:

Code:

Prime Factorization:

Source: Link

Code:

Divisor:

Code:

আমরা Divisor নিয়ে আরো কিছু মজার বিষয় জানতে পারবো এই Link টায়।

Big Mod:

Source: Link

Code:

Primality Test: 

Source : Link1 Link2 Link3

Code : 

Modular Arithmetic ( Big MOD + Modular Multiplicative Inverse)

Modular Arithmetic কি  সেটা জানার জন্য এই লিঙ্কে দেখে আসি।
আলোচনার শুরুতে কিছু জিনিস ক্লিয়ার করা উচিত...
১) "%" এই চিহ্ন দিয়ে সি,সি++,জাভা সহ বেশিরভাগ ল্যাংগুয়েজে ভাগশেষ অপারেটর বুঝায়।
উদাঃ
          5 % 2 = 1
          5 % (-2) =  1
          (-5) % 2 = -1
          (-5) % (-2) = -1
এই গুলো code লিখে নিজে নিজে চেক করে নিই।
২) "mod" ও ভাগশেষই প্রকাশ করে কিন্তু একটু সমস্যা আছে , সমস্যাটা হল যদি  X mod m করি এবং m>0 তাহলে এর result কখনই 0 $\le$ m$\le \; m-1$ এর বাইরে কোনো মান হবে না।
উদাঃ
        5 mod 2 = 1
       (-5) mod 2 = 1 (not -1)
অতএব, mod 2 = {0 , 1}
             mod 3 = {0 , 1 , 2} 
             mod n = {0 , 1 , 2 , ... , n-1}
 ৩) a ≡ b (mod m)
     উদাঃ
             5 ≡ 2 (mod 3)
             5 mod 3 = 2  and  2 mod 3 = 2

 এখানে চিত্রে সংখ্যারেখা দিয়ে দেখানো হল। -2, 2, 5 এদের জন্য (mod 3) এর মান 2 ।
৪) a ≡ b (mod m)  হলে আমরা ab ≡ 1 (mod m) ... কেন?? এর উত্তর পাবার জন্য নিজে ট্রাই করি ওই সংখ্যারেখার মাধ্যমে...
 5*2 ≡ 1 (mod 3) , এখানে আমরা আরেকটা কথা বলে রাখি , 5 হল  (2 mod 3) এর Modular Multiplicative Inverse। এর ব্যাখ্যা নিচে দেওয়া আছে আপাতত মনে রাখি।
৫) X mod m = R হলে , X = q*m + R ; এখানে ,  q যেকোনো একটি সংখ্যা।
উদাঃ 
        5 mod 2 = 1
        5 = 2*2 + 1 ; where , q = 2, m = 2 and R = 1.
এখন আমাদের কাজ হবে কোনো সংখ্যা দিলেই অইটা mod দিয়ে কেটে ছোট করে দেওয়া। :P
এখন তোমার অনেক পাজি একটা ছোট ভাই আছে। সে একদিন বলল- "ভাইয়া, তুমি নাকি বড় কোনো সংখ্যাকে  কেটে ছোট করতে পার?" তুমি কিঞ্চিত হাসি দিয়ে বললা- "হ্যা,পারি।(মনে মনে ভাবতেছো আমি করবো নাকি রে পাগলা এটা তো আমার কম্পিউটার করে দিবে...মুহা হা হা...)" তারপর তোমাকে সে 2^50 mod 4 বের করে দিতে বলল।  এখন তোমার মুখ শুকিয়ে গেল...এতো বড়টা ছোট করবো কেম্নে?(-_-)
এখানেই আসবে Big MOD এর concept । :D
আমি এই বেপারে কিছুই বলবো না কারণ এর উপর শাফায়েত ভাই যা লিখছে তারপর এর উপর কিছু বলার থাকে না।
এখানেই লিঙ্ক দেওয়া হল। এরপর আরেকটা জিনিস থেকে যায় তা হচ্ছে যদি সংখ্যা power অথবা গুণ আকারে না থেকে ডিরেক্ট 10^18 এর চাইতে বড় দেয় তখন কিভাবে mod করবো। এটার solutionও এই লিঙ্কে আছে। :D 
আমার আর কোনো কাজ নাই শুধু লিঙ্ক দিয়ে বেড়াইতেছি। (-_-)
একটা কাজ পাইছি !! Modular Multiplicative Inverse নিয়ে বকবক করতে পারবো... :P
আগে দেখে নিই এটা কেনো লাগবে। - এটা লাগবে মূলত তুমি যখন a/b mod m বের করতে যাবা।
কারণ, a*b mod m এর জন্য সূত্র আছে(শাফায়েত ভাই এর ব্লগে দেখ) কিন্তু a/b এর জন্য তেমন কোনো সূত্র নাই।
তুমি যখন Combination করতে গিয়ে n! / ((n-r)! * r!) এর মান বের করতে যাবা তখন সমস্যায় পরবা। n এর মান ছোট হইলে সমস্যা নাই কিন্তু প্রব্লেম গুলাতে n এর মান ছোট দেয় না, বরং অনেক বড় মান দিয়ে সেটা m (কোন একটা সংখ্যা) দিয়ে mod করতে বলা হয়। যেহেতু a/b mod m এর জন্য কোনো সূত্র নাই তাই তোমাকে একটা পথ খুজে বের করতে হবে এইটা করার জন্য। এর জন্য তোমার জানা লাগবে Fermat's little theorem নামে একটা theorem . এই theorem অনুযায়ী ,
যদি p একটি প্রাইম নাম্বার, a যেকোন integer হয় এবং a যদি p দিয়ে বিভাজ্য না হয়, তাহলে লিখা যায়,

a^(p-1) ≡ 1 (mod p)

 উদাঃ
          2^(17-1) ≡ 1 (mod 17)
    or,  2^16 ≡ 1 (mod 17) --- (1)
Now, 2^50 = 2^(16 * 3 + 2) [ 50 = 16 * 3 +2 , উপরের ৫ নং থেকে প্রাপ্ত ]
                  = (2^16)^3 * 2^2

         ≡ (1)^3 * 4 (mod 17)  [From eqn (1) ]

 so,2^50 ≡ 4 (mod 17)

 সুতরাং, উক্ত theorem টা ১০০ ভাগ খাটি। :D

আমরা a^(p-1) ≡ 1 (mod p) 

 =  a * a^(p-2) ≡ 1 (mod p)  , ও লিখতে পারি ।

এখন দেখ এই  সমীকরণটি উপরের ৪ নং এর সমীকরণের সাথে মিলে। অর্থাৎ, আমরা বলতে পারি, a এর

 Modular Multiplicative Inverse হচ্ছে a^(p-2)। 

এখনই হয়ত অনেকে বুঝে গেছে বাকি কি কাজ করতে হবে। যারা বুঝি নাই তারা একটু খেয়াল করি উক্ত সমীকরণটি ,
যদি আমাকে (a/b)%m বের করতে বলে, আমাকে (b mod m) এর Modular Multiplicative Inverse বের 

করতে হবে। অর্থাৎ , BigMOD(b, m-2, m) ফাংশনটি কল করলেই খেলা শেষ। :D

এই ফাংশন আমাকে যা রিটার্ন করবে, তাই হচ্ছে Modular Multiplicative Inverse of (b mod m)।

উক্ত ধারণার উপর প্রব্লেমঃ

374 - Big Mod 

10127 - Ones 

1067 - Combinations  

1054 - Efficient Pseudo Code

DCP-23: Another Bigmod Problem

Number Theory Problem Links

N.B. I will add more useful links. Keep an eye on this page.
GCD & LCM:

1. 11417 - GCD 
2.  11388 - GCD LCM

Prime Number:

1. 516 - Prime Land
2. 160 - Factors and Factorials 
3. 583 - Prime Factors
4. 10392 - Factoring Large Numbers
5. 10200 - Prime Time
6. 10140 - Prime Distance
7. 914 - Jumping Champion
8. 897 - Anagrammatic Primes
9. 524 - Prime Ring Problem
10. 406 - Prime Cuts
11. 884 - Factorial Factors
12. 10780 - Again Prime? No Time.

Goldbach's Conjecture Theorem:

1. 686 - Goldbach's Conjecture (II) 

Modular Arithmetic:

1. 374 - Big Mod 
2. DCP-23: Another Bigmod Problem 
3. 1054 - Efficient Pseudo Code 

 CRT:

1. A. Cutting Figure 
2. B. Remainders Game 
3. E. Congruence Equation 

Factorial: 

1. DCP-519: Dealing with factorial factors 

Permutation & Combination: 

1. DCP-59: Permutation 
2. 1067 - Combinations  
3. 1102 - Problem Makes Problem 
4. 1419 - Necklace 

 Probability:

1. A. Little Pony and Expected Maximum
2. A. Die Roll 
3. 1079 - Just another Robbery