Euler's Totient or Phi Function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর  সহমৌলিক (relative prime). অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন সাধারন উৎপাদক (common divisor) নেই, আরেকটু সহজ করে বলতে গেলেঃ 1 থেকে N এর মাঝে, যাদের সাথে N এর GCD = 1. উদাহরন :
15 সংখ্যাটি বিবেচনা করি,
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এর মধ্যে থেকে 15 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে মার্ক করিঃ
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
এই সংখ্যাগুলিকে বাদ দিবো, কেননা 15 এর গুননীয়ক ঃ 3 এবং 5. কাজেই, এদের গুনিতক (3, 5, 6, 9, 10, 12, 15) এগুলো বাদ যাবে।
তাহলে অবশিষ্ট থাকে 8 টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
সুতরাং, φ( 15 ) = 8.
এখন চিন্তা করি, মৌলিক সংখ্যার জন্য phi এর মান কত হবে?
খেয়াল করলে দেখবো যে, আসলে কোন মৌলিক সংখ্যার সাথে তার আগের সকল সংখ্যাই সহমৌলিক, অর্থাৎ এদের মাঝে ১ ছাড়া আর কোন গুননীয়ক নেই। অর্থাৎ, φ(প্রাইম) = প্রাইম - ১।
7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1, 2, 3, 4, 5, 6, 7
so, φ(7) = 7-1 = 6.
so, φ(prime) = prime-1

মৌলিক সংখ্যার ক্ষেত্রে কাজটা অনেক সহজ হলেও অন্যান্য ক্ষেত্রে কিছুটা জটিল। এজন্য আমাদের একটি Theorem জানতে হবে। সেটি হলঃ
φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime

এর জন্য, আমাদের i এবং j, উভয়কেই সহমৌলিক হতে হবে। এখন খেয়াল করি, আমরা যদি, i এবং j কে এমনভাবে নিয়ে আসতে পারি, যে তারা উভয়েই প্রাইম হবে, অর্থাৎ যেকোন সংখ্যাকে আমরা প্রাইম এর ফ্যাক্টরে নিয়ে আসতে যদি পারি, তাহলে আমাদের জন্য φ(prime) = prime-1 দিয়ে প্রতি প্রাইম ফ্যাক্টর এর phi বের করা খুবি সহজ, এবং সেখান থেকে φ( i*j ) = φ( i ) * φ( j ) এই ফর্মুলার মাধ্যমে আমরা প্রাইম ফ্যাক্টর থেকে প্রাপ্ত phi এর মান গুন করে দিলেই মূল সংখ্যার phi এর মান পেয়ে যাবো। উদাহরনঃ

φ( 30 ) = φ( 2 ) * φ( 3 ) * φ( 5 )
now, φ( 2 ) = 1, φ( 3 ) = 2, φ( 5 ) = 4.
so, φ( 30 ) = 1 * 2 * 4 = 8
অর্থাৎ 1 থেকে 30 এর মাঝে, 30 এর সাথে সহমৌলিক 8 টি সংখ্যা আছে।
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
এগুলো হলঃ 1, 7, 11, 13, 17, 19, 23, 29 (Total 8 numbers).

এখন ধরা যাক, আমরা 4-এর φ ফাংশনের মান বের করতে চাই। আমরা এখন পর্যন্ত যা জানি, তা অনুযায়ী,
 φ(4) = φ(2)*φ(2) = 1*1 = 1.
কিন্তু ,
GCD(1,4) = 1, রিলেটিভলি প্রাইম
GCD(2,4) = 2
GCD(3,4) = 1, রিলেটিভলি প্রাইম
GCD(4,4) = 4
অর্থাৎ, φ(4) = 2
এটি কিন্তু আমাদের ফর্মুলা অনুযায়ী মিলেনি। তাহলে আমরা এখান থেকে একটি জিনিস খেয়াল করতে পারি যে, যখন আমাদের প্রাইম ফ্যাক্টরের ঘাত (power) ১ হবে, কেবলমাত্র তখনি আমরা আমাদের উপোরক্ত ফর্মুলা ব্যবহার করতে পারবো। তাহলে এরকম ক্ষেত্রে আমাদের ফর্মুলার একটু পরিবর্তন আসবে এভাবে ঃ
φ( n^k ) = n^k – n^k-1 , when n is prime and k != 1.
তাহলে আমরা এতক্ষনের আলোচনা থেকে ৩ টি গুরুত্বপূর্ণ ব্যাপার দেখলাম। এগুলি হলঃ 

1. φ( n ) = n - 1, when n is prime and power is 1.
2. φ( n^k ) = n^k – n^k-1 ,when n is prime and k != 1.
3. φ( i*j ) = φ( i ) * φ( j ), when i and j is relatively prime.

অ্যালগরিদম (Algorithm)

আমরা 1 থেকে N পর্যন্ত লুপ চালায়ে ব্রূট ফোর্স অ্যালগরিদম লিখতে পারি এভাবেঃ

কিন্তু এটি বড় বড় সংখ্যার জন্য রান করতে অনেক সময় নিবে, কাজেই এটি তেমন ভালো এপ্রোচ না আমাদের জন্য।
এবার আমরা একটু অন্যভাবে প্রোগ্রাম করবো।
৩৬ = (২*২)*(৩*৩)
φ(৩৬) এর সর্বোচ্চ মান হতে পারে ৩৬। কাজেই আমরা ইনিশিয়ালি, result = 36 লিখে রাখবো।
এর মৌলিক গুণনীয়ক আছে দুইটিঃ ২ এবং ৩। এখন,
১ থেকে ৩৬-এর মধ্যে ২-এর গুণনীয়ক কয়টি আছে?  উত্তরঃ ৩৬/২ = ১৮ টি।
তাহলে, আমরা লিখবো result = result - 18 = 36 - 18 = 18.
এখন আমরা ৩৬ কে ২ দিয়ে যতবার ভাগ করা যায়, করে ফেলবো। এক্ষেত্রে ২ বার ভাগ করার পরে আমরা পাবো ৯।
এখন ১ থেকে ১৮ এর মাঝে ৩ এর গুণনীয়ক আছে , ১৮/৩ = ৬ টি।
তাহলে আমরা লিখবো result = result - 6 = 18 - 6 = 12.
সুতরাং, φ(৩৬) = ১২।
এরপরে আমরা আবার ৯ কে ৩ দিয়ে ভাগ করতে থাকবো। যদি আমাদের n এর মান ১ হয়ে যায়, তাহলে আমাদের আর কিছু করার দরকার নাই। কিন্তু যদি ১ না হয়, তাহলে আমরা result = result - result/n করবো, কেননা, ১ যেহেতু হয়নি, কাজেই, n আসলে প্রাইম নাম্বার ছিল। আর আমরা আগেই জানি, প্রাইম এর জন্য φ(prime) = prime-1

এতক্ষন আমরা যেসব phi জেনারেট করলাম, তার সবই সিম্পল কুয়েরির ক্ষেত্রে ভালো এবং দ্রুত আউটপুট দিবে, কিন্তু, আমাদের যদি কুয়েরির মান অনেক হয়, তাহলে বারবার phi ফাংশন কল করলে আমাদের প্রোগ্রাম TLE দিবে। এজন্য আমাদের আরও এফিশিয়েন্ট অ্যালগরিদম দরকার, যার মাধ্যমে আমরা সহজে অনেকগুলি phi এর মান আগে থেকে জেনারেট করে এরপরে কুয়েরির অ্যান্সার করবো। ঠিক সীভ (sieve of eratosthenes) যেভাবে জেনারেট করতাম, সেভাবে জেনারেট করবো। সকলের জন্য পরামর্শ রইল নিজে কোডটি লিখার। চেষ্টা করার পরে না পারলে এরপরে নিচের কোড দেখে শিখে নেয়া যাবে।

ফাইনালি, একটি সুন্দর জিনিস দেখা যাক।
"For any integer n, the sum of the totient(phi) values of each of its divisors equals n".
এখন দেখা যাকঃ
n = summation of φ( x ) ; where x are the divisors of n.
যেমন, 30 এর divisor =
1 x 30
2 x 15
3 x 10
5 x 6
so,  30 = φ( 1 )+φ( 2 )+φ( 3 )+φ( 5 )+φ( 6 )+φ( 10 )+φ( 15 )+φ( 30 ) = 1+1+2+4+2+4+8+8 = 30
অর্থাত, যেকোন সংখ্যার সকল divisor এর phi এর মানের যোগফল, ঐ সংখ্যার সমান হবে।

Practice Problems

• phi-phi-phi (medium)
• Monk and ETF (hard)