Эйлер функциясы

Уикипедия — ашық энциклопедиясынан алынған мәлімет
Мұнда ауысу: шарлау, іздеу
Алғашқы мың мәні

Эйлера функциясы , мұндағы натурал сан, санынан үлкен емес әрі онымен өзара жай натурал сандар санына тең. Эйлера бұл функцияны сандар теориясы еңбектерінде алғашқы болып пайдаланғандықтан соның құрметіне осылай талып кетті.

Анықтама[өңдеу]

жай сандарға келесідей жіктелген натурал саны берілсін:

Онда

функциясы Эйлер функциясы деп аталады. Мұндағы

болады деп саналады. Эйлера функциясын Эйлер көбейтіндісі ретінде де өрнектеуге болады:

мұндағы санының жай сандарға жіктелуінде қатысатын барлық жай сандарды қабылдайды.

Функцияның кейбір мәндері[өңдеу]

+0 +1 +2 +3 +4 +5 +6 +7 +8 +9
0+ 1 1 2 2 4 2 6 4 6
10+ 4 10 4 12 6 8 8 16 6 18
20+ 8 12 10 22 8 20 12 18 12 28
30+ 8 30 16 20 16 24 12 36 18 24
40+ 16 40 12 42 20 24 22 46 16 42
50+ 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44
70+ 24 70 24 72 36 40 36 60 24 78
80+ 32 54 40 82 24 64 42 56 40 88
90+ 24 72 44 60 46 72 32 96 42 60

Қасиеттері[өңдеу]

  1. , егер — жай сан болса. Жекеше түрі: болғанда ;
  2. , егер m мен өзара жай болса. Яғни Эйлер функциясы мультипликативті;
  3. , егер m мен өзара жай болса. Бұл Эйлер теоремасы болып табылады;
  4. , если Ең Кіші Ортақ Еселік, aл Ең Үлкен Ортақ Бөлгіш.

Асимптоталық байланыстар[өңдеу]

  1. мұндағы — белгілі бір тұрақты;

Аналитикалық байланыстар[өңдеу]

  • Дирихле қатарын коэффициенттерімен Риман дзета-функциясы арқылы өрнектеуге болады:
  • Ламберт қатары қосындысын коэффициенттерімен:
мұндағы .
  • , мұндағы .

Компьютерлік іске асырылуы[өңдеу]

Си тілінде[өңдеу]

Төмендегі функция көбейтіндісін есептейді. Бұл санын жай сандарға көбейткіштерге 2-ден бастап барлық сандарға бөлу арқылы іске асырылады; егер санға бөлінсе, бұл сан санын өшіріледі, ал нәтиже-көбейтінді сәйкесінше сол санға көбейтіліп өседі.

int phi(int n)
{
  int ret = 1, p;
  for(p = 2; p * p <= n; p++)
  {
    if (n % p == 0)
    {
      n /= p;
      while(n % p == 0) 
      {
        n /= p;
        ret *= p;
      }
      ret *= p - 1;
    }
  }
  return n > 1 ? ret * (n - 1) : ret;
}

VB.Net[өңдеу]

    Private Function phi(ByVal n As Integer) As Integer
        Dim ret As Integer = 1, p As Integer = 2
        For p = 2 To n / p
            If n Mod p = 0 Then
                n /= p
                While n Mod p = 0
                    n /= p
                    ret *= p
                End While
                ret *= p - 1
            End If
        Next
        Return If(n > 1, ret * (n - 1), ret)
    End Function

F#[өңдеу]

let phi n =
    let rec nod a b = if b = 0 then a
                      else nod b (a % b)
    { 1 .. n-1 }
    |> Seq.filter (fun i -> nod i n = 1)
    |> Seq.length