Euler's Totient or phi function φ(n)

phi ফাংশন কি?

phi ফাংশন একটি arithmetic function যেটি count করে একটি সংখ্যা N এর সমান বা ছোট কতটি ধনাত্মক সংখ্যা আছে যেগুলো N এর relative prime. অর্থাৎ 1 থেকে শুরু করে N পর্যন্ত মোট কতটি সংখ্যা আছে যেগুলোর সাথে N এর 1 বাদে অন্য কোন common divisor নেই, আরেকটু সহজ করে বলতে গেলে যাদের সাথে N এর GCD = 1. উদাহরন দিলেই ব্যাপারটা আরও পরিষ্কার হবে।

8(eight) সংখ্যাটিকে ধরি, এর সমান ও ছোট ধনাত্মক সংখ্যাগুলো হল,
1 2 3 4 5 6 7 8
এর মধ্যে থেকে 8 এর সাথে common divisor আছে এমন সংখ্যাগুলোকে বাদ দেই,
1 2 3 4 5 6 7 8
তাহলে 4 টি সংখ্যা অবশিষ্ট থাকে 1 3 5 7. অর্থাৎ φ(8) = 4.

আবার 15 সংখ্যাটি বিবেচনা করি,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
অবশিষ্ট থাকে 8 টি সংখ্যা – 1, 2, 4, 7, 8, 11, 13, 14
অর্থাৎ φ(15) = 8.

এখন চিন্তা করি prime number এর ক্ষেত্রে phi function এর চেহারা কেমন হবে। উত্তরটা খুব সহজ। কোন একটি সংখ্যা prime এর মানেই হল সংখ্যাটির 1 বাদে অন্য কোন divisor নেই যেটি সংখ্যাটি থেকে ছোট।
সুতরাং φ(prime) = prime-1.

7 সংখ্যাটি একটি prime number. তাহলে 7 এর জন্য,
1 2 3 4 5 6 7

so, φ(7) = 7-1
so, φ(prime) = prime-1

Some Properties

phi ফাংশনের কাজ করার মত algorithm লিখতে হলে আমাদেরকে এর কয়েকটি basic properties সম্পর্কে জানতে হবে।

1. প্রথমটি উপরেই বর্ণিত। φ(prime) = prime-1.

2. ধরি P একটি prime নাম্বার। P এর যেকোনো পাওয়ার a হলে,

3. অত্যন্ত গুরুত্বপূর্ণ। ফাংশনটি একটি multiplicative ফাংশন। ব্যাখ্যা করি।
ধরি a এবং b দুইটি relative prime number অর্থাৎ এদের মধ্যে 1 ব্যাতিত কোন common divisor নেই। তাহলে a*b এর জন্য ফাংশনটির চেহারা হবে,

Building an Algorithm

উপরের properties গুলোকে ব্যাবহার করে যেকোনো নাম্বারের phi function value বের করার মত পদ্ধতি বের করা যাক। প্রথমেই একটুখানি গনিত প্রয়োজন।

আমরা যেই নাম্বারটির phi function value বের করব সেটিকে তার prime factor এ ভেঙ্গে ফেলব। এটাই আমাদের algorithom এর ভিত্তি হবে।

ধরি একটি নাম্বার n. একে prime factor এ ভেঙ্গে লিখলে হবে,

এখানে n এর factor এর সংখ্যা k টি। এবং P একটি factor হলে a তার পাওয়ার। তাহলে,

এই শেষের লাইনটাই আমাদের দরকার।

আমরা লুপ চালিয়ে একটা একটা করে n এর prime factor গুলা (P1, P2, P3, ……, Pk) নিব এবং প্রত্যেকবার একটা অপারেশন করব। কি করব বলি, সুবিধার জন্য ধরি n এর factor এর সংখ্যা দুইটি। তাহলে,

এই অবশিষ্ট another_something ই হবে আমাদের রেজাল্ট।

অর্থাৎ আমরা একটা variable এ প্রথমে n এর value টা রাখব। ধরি variable টার নাম result। তারপর একটা একটা করে factor P ধরব এবং result কে P দিয়ে ভাগ করে ভাগফলটাকে result থেকে বাদ দিব। এভাবে ক্রমাগত factor গুলা দিয়ে ভাগ এবং বিয়োগ করতে থাকলে result এর ভ্যালু কমতে থাকবে। সবশেষে যা পড়ে থাকবে তাই আমাদের φ(n).

বিশেষ দ্রষ্টব্যঃ prime factor কিভাবে বের করতে হয় সেটা না জানলে পরের code টুকু বুঝতে কষ্ট হবে। সেক্ষেত্রে prime factor বের করাটা আগে শিখে নেওয়া ভাল। এটাই এই অ্যালগরিদমের ভিত্তি।

A possible C++ Implementation

Some UVA Problems

Happy coding.

Md. Fahim Mohiuddin Dhrubo
11 October 2014