Euler's totient function

 

Euler's totient function

নাম্বার থিওরির খুব গুরুত্তপূর্ণ একটা টপিক হচ্ছে এই Euler's totient function. যা, বলা যায় অনেকটা না জানলেই না । আমি মনে করি এই ফাংশনের ক্রিয়া কর্ম না জানলে নাম্বার থিওরির বিশাল একটা পার্ট আপনার কাছে অজানাই থেকে যাবে । 
তাই এই নিয়ে কিছু বলব বলে ঠিক করেছি ... 

শুরুতে বলি ...
তখন সালটা ১৭৬৩ । লিওনার্দ অয়লার তখন সবে এই ফাংশন টা আবিস্কার করেছেন । কিন্তু দূর্ভাগ্যবশত তিনি কোন সিম্বল খুজে পাচ্ছিলেন না এটা প্রকাশ করার জন্য । 
১৭৮৪ সালে এক পাব্লিকেশনের উদ্দ্যেশ্যে তিনি এই বিষয়ে আবার স্ট্যাডি করেন এবং এটাকে প্রকাশ করার জন্য একটা গ্রিক সিম্বল ব্যবহার করেন যা দেখতে অনেকটা ' π ' এর মত । 
তখন তিনি সেটাকে πD হিসেবে প্রকাশ করেছিলেন যা বুঝাচ্ছে "the multitude of numbers less than D, and which have no common divisor with it".
এরপর ১৮০১ সালে গণিতবিদ গাউস Disquisitiones Arithmeticae তে একটি স্ট্যান্ডার্ড নোটেশনের মাধ্যমে অয়লারের এই ফাংশনটি ব্যবহার করেন, এবং সেই  স্ট্যান্ডার্ড নোটেশনটি ছিল φA (আমরা বলি phi of A) . তখন থেকেই এই ফাংশনটি Euler's phi function বা কেবল phi function নামে পরিচিতি লাভ করে । 
১৮৭৯  সালে  J. J. Sylvester এই ফাংশনে totient  কথাটি জুড়ে দেন । এরপর থেকেই এটি মূলত Euler's totient function বা  Euler totient বা কেবল Euler's totient হিসেবে আত্মপ্রকাশ করে ।

 Euler's totient function কি করে ... 

নাম্বার থিওরিতে Euler's totient function কে φ(n) প্রকাশ করা হয় । যদি φ(n)=x হয়, তার মানে 1 থেকে n পর্যন্ত x টি সংখ্যা আছে যাদের সাথে n এর gcd হচ্ছে 1 ।  যদি gcd(a,b)=1 হয়, আমরা বলি a আর b একে অপরের co-prime. যেমন n=9 এর জন্য gcd(9,3)=gcd(9,6)=3  এবং  gcd(9,9)=9 । 
আর বাকি ৬ টি সংখ্যার ক্ষেত্রে  gcd(9,1)=gcd(9,2)=gcd(9,4)=gcd(9,5)=gcd(9,7)=gcd(9,8)=1 ... দেখা যাচ্ছে এখানে সবকটি নাম্বারের ক্ষেত্রে gcd=1 হচ্ছে এবং এমন নাম্বারের সংখ্যা ৬ টি । আর তাই φ(9)=6 ।

অয়লারের প্রোডাক্ট ফরমুলা অনুযায়ী  Euler's totient function কে এভাবে প্রকাশ করা যায়ঃঃ

φ(n)=n∏p|n(1−1p)
যেখানে p হচ্ছে প্রাইম নাম্বার । আর p|n হচ্ছে সেই সব প্রাইম নাম্বার যারা n কে নিঃশেষে ভাগ করতে পারে । [ তাঁর মানে n এর প্রাইম ফেক্টোরাইজেশন ]
যেমনঃ  a|b এর মানে হচ্ছে  a নিঃশেষে ভাগ করতে পারে b কে । যেখানে  a অবশ্যই একটা প্রাইম নাম্বার । তাঁর মানে a হচ্ছে  b এর ডিভিজর ।
একটা উদাহরণ দেখা যাকঃ 
 9 = 3 * 3 ; 
φ(9) = 9 * (1 - ( 1 / 3 ) ) = 9 * ( 2 / 3 ) = 6;
p = 3 ; যা  ৯ এর ডিভিজর ।
∏
এখন এই উদাহরণ থেকে এও স্পস্ট যে, ৯ এর relatively prime ৬ টি । এর মানে  gcd(9,1)=gcd(9,2)=gcd(9,4)=gcd(9,5)=gcd(9,7)=gcd(9,8)=1।  সুতরাং ৯ এর  Relatively Prime হচ্ছেঃ 1,2,4,5,7,8 । (উপরেই বলা ছিল)

Relatively Prime Number হচ্ছে যে যে নাম্বারের সাথে n এর gcd=1 ; 

আবার 120 এর ক্ষেত্রে, 120 =  23 * 31 * 51
 φ(120) = 120 (1- (1/2)) * (1- (1/3)) * (1- (1/5)) = 32 ;

সুতরাং বুঝাই যাচ্ছে ১২০ এর Relatively Prime ৩২ টি ।
[বিঃদ্রঃ φ(n) = n * ( 1 - ( 1 / p ) ) =  n * n / p ও লিখা যায় । ( কোডে ইমপ্লিমেন্টেশন করা হয়েছে এইভাবে ) ]
RSA Encryption System এ Euler's totient function এর গুরুত্ব অনেক । 
সাধারণ ইমপ্লিমেন্টেশনঃঃ
 // Implements Euler Totient Function with Prime factorization
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define nl puts("")
#define MX 105
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

// generating Seieve of Erathosthenis

bool stats[MX]; vector<int> p; int plen;

void seieve()
{
    mem(stats,false);

    stats[0]=stats[1]=true;
    int i,j,qrt;

    for(i=4;i<=MX;i+=2) stats[i]=true;

    qrt=(int) sqrt(double(MX));

    for(i=3;i<=qrt;i+=2)
    {
        if(!stats[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                stats[j]=true;
            }
        }
    }

    for(i=2;i<=MX;i++)
    {
        if(!stats[i])
        {
            p.push_back(i);
        }
    }

    plen=p.size();
}

vector<int>primefactors; int prmfctorlen;

bool color[MX];

void primefacto(int n) // performing prime factorization
{
    int i,j;

    mem(color,false);

    for(i=0;i<plen and p[i]*p[i]<=n;i++)
    {
        if(!(n%p[i]))
        {
            while(!(n%p[i]))
            {
                if(!color[p[i]]) // same factor never come multiple time..
                {
                    primefactors.push_back(p[i]);
                }

                color[p[i]] = true;

                n/=p[i];

                if(n==0 or n==1) break;
            }
        }
    }

    if(n!=1)
    {
        primefactors.push_back(n);
    }

    prmfctorlen = primefactors.size();
}

int euler_phi(int n)
{
    primefacto(n);

    int i,phi=n;

    for(i=0;i<prmfctorlen;i++)
    {
        phi-=phi/primefactors[i];
    }

    return phi;
    //cout << phi;
}

int main()
{
    int i;
    seieve();
    //lp1(i,plen)cout << p[i] << " ";
    int n; cin >> n;
    //primefacto(n);
    //lp1(i,prmfctorlen) cout << primefactors[i] << " ";
    int res=euler_phi(n);
    cout << res << endl;

    return 0;
}
অপ্টিমাইজড ইমপ্লিমেন্টেশনঃঃ  


 // Euler Totient Function modified Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <sstream>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#define sf scanf
#define pf printf
#define sfint scanf ("%d %d",&a,&b)
#define sfl scanf ("%ld %ld",&a,&b)
#define sfll scanf ("%lld %lld",&a,&b)
#define sfd scanf ("%lf %lf",&a,&b)
#define sff scanf ("%f %f",&a,&b)
#define lp1(i,n) for(i=0;i<n;i++)
#define lp2(i,n) for(i=1;i<=n;i++)
#define LL long long
#define L long
#define mem(c,v) memset(c,v,sizeof(c))
#define nl puts("")
#define MX 1005
#define N 100
#define MOD 10000000007
#define pb push_back
#define pi acos(-1.0)
#define sz size()
#define gc getchar ()
#define ps push
#define clr clear
#define bn begin()
#define ed end()

using namespace std;

// generating Seieve of Erathosthenis

bool stats[MX]; vector<int> p; int plen;

void seieve()
{
    mem(stats,false);
    int i,j,qrt;

    stats[0]=stats[1]=true;

    for(i=4;i<=MX;i+=2) stats[i]=true;

    qrt=(int)sqrt(double(MX));

    for(i=3;i<=qrt;i+=2)
    {
        if(!stats[i])
        {
            for(j=i*i;j<=MX;j+=i+i)
            {
                stats[j]=true;
            }
        }
    }

    for(i=2;i<=MX;i++)
    {
        if(!stats[i])
        {
            p.push_back(i);
        }
    }

    plen=p.size();
}

int phi[MX+5];

void euler_phi()
{
    int p,k,i,j;

    for(i=1;i<=MX;i++) phi[i]=i; // initialize the phi array.

    for(p=2;p<=MX;p++)
    {
        if(!stats[p]) // check either p is prime or not.
        {
            if(phi[p]==p)
            {
                for(k=p;k<=MX;k+=p)
                {
                    phi[k]-=phi[k]/p;
                }
            }
        }
    }
}

int gcd (int a, int b)
{
    return (b==0 ? a : gcd(b,a%b));
}

int main()
{
    int i,j,n,p,k,sp,c;
    seieve();
    //lp1(i,plen) cout << p[i] << " ";
    euler_phi();

    while(cin >> n)
    {
        sp=0;

        cout << "Relatively Primes of " << n << " are : ( ";

        lp2(i,n)
        {
            if(gcd(n,i)==1) // finding relatively prime numbers
            {
                sp++; c=sp;

                cout << i;

                if(c>0)
                {
                    cout << " ";
                    c--;
                }
            }
        }

        cout << ")";

        cout << endl << "Total Number of Relatively Primes of " << n << " is ( " << phi[n] << " )" << endl;
    }

    return 0;
}
 
 
Euler Phi Sieve_Version
 

// Euler Phi Sieve version

#include<bits/stdc++.h>

#define SZ 100100

using namespace std;

int phi[SZ+9];

void generate_phi()
{
    int i,j;

    phi[1] = 1;

    for(i=2; i<SZ ; i++)
    {
        if(!phi[i])
        {
            phi[i] = i-1;

            for(j=i+i; j<SZ; j+=i)
            {
                if(!phi[j])
                {
                    phi[j] = j;
                }

                //phi[j] = phi[j] / i * (i-1) ;
                phi[j] = phi[j] / i;
                phi[j]*=(i-1);
            }
        }
    }
}

int main()
{
    generate_phi();

    for(int i=1;i<=10;i++)
    {
        cout << "for " << i << ".number of Co prime: " << phi[i];
        puts("");
    }

    return 0;
}
 
আশা করি কোড বুজতে কোন অসুবিধা হবে না এবং প্রবলেম সল্ভ করার পরামর্শ থাকল । আমি অবশ্য স্টার্ট করেছিলাম LightOJ 1007 - Mathematically Hard এই প্রবলেম দিয়ে । সব শেষে শুভকামনা রইল । আর হ্যাঁ, যেকোন ভুল ক্ষমার দৃষ্টিতে দেখবেন সেই সাথে কমেন্ট করতে কোন দ্বিধা করবেন না । 
Happy Coding...

Comments

Post a Comment

Popular posts from this blog

Almost Prime Numbers

                                         ==   Almost Prime Number   == Almost Prime Number হচ্ছে সেই সকল প্রাইম নাম্বার যাদের প্রাইম ফেক্টোরিজেশন কেবলেই একটা প্রাইম নাম্বার । যেমনঃ               ১-১০ পর্যন্ত Almost Prime Number ৩ টি ।                 ৪=২*২ ; ৮=২*২*২ ; ৯=৩*৩ ; এখানে ৪,৮,৯ প্রতিটি সংখ্যার প্রাইম ফেক্টোরিজেশন কেবল একটা সংখ্যা । ৪ ও ৮ এর ক্ষেত্রে ২ এবং ৯ এর ক্ষেত্রে ৩ । আবার ১১-২০ পর্যন্ত Almost Prime Number ১ টি । তা হল ১৬=২*২*২*২ ;  কিন্তু লক্ষ্য করুন, Almost Prime Number গুলুর একটি সংখ্যাও প্রাইম নাম্বার নয় । তো, সে ক্ষেত্রে আপনি যদি প্রতিটি প্রাইম নাম্বারের ২ থেকে ইনফিনিটি সংখ্যক পাওয়ারের কথা চিন্তা করেন দেখবেন আপনি আপনার Almo...
Read more

Seieve of Eratosthenes

  সিভ অফ এরাটোসথেনিসের ইফিসিয়েন্ট ভার্সনঃ বিটওয়াইজ সিভ  প্রথমে কোডটা দেখা যাকঃ   কোডঃ // bitwise Seieve of Eratosthenes #include <iostream> #include <cstdio> #include <cstring> #include <map> #include <string> #include <vector> #include <cmath> #include <cctype> #include <sstream> #include <set> #include <list> #include <stack> #include <queue> #include <algorithm> #define sf scanf #define pf printf #define sfint scanf ("%d %d",&a,&b) #define sfl scanf ("%ld %ld",&a,&b) #define sfll scanf ("%lld %lld",&a,&b) #define sfd scanf ("%lf %lf",&a,&b) #define sff scanf ("%f %f",&a,&b) #define lp1(i,n) for(i=0;i<n;i++) #define lp2(i,n) for(i=1;i<=n;i++) #define LL long long #define L long #define mem(c,v) memset(c,v,sizeof(c)) #define ui unsigned int #define ull unsigned long long int #define nl puts("") ...
Read more