Эйлер функциясы
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/EulerPhi.svg/220px-EulerPhi.svg.png)
Эйлера функциясы , мұндағы — натурал сан, санынан үлкен емес әрі онымен өзара жай натурал сандар санына тең. Эйлера бұл функцияны сандар теориясы еңбектерінде алғашқы болып пайдаланғандықтан соның құрметіне осылай талып кетті.
Анықтама
[өңдеу | қайнарын өңдеу]жай сандарға келесідей жіктелген натурал саны берілсін:
Онда
функциясы Эйлер функциясы деп аталады. Мұндағы
болады деп саналады. Эйлера функциясын Эйлер көбейтіндісі ретінде де өрнектеуге болады:
мұндағы — санының жай сандарға жіктелуінде қатысатын барлық жай сандарды қабылдайды.
Функцияның кейбір мәндері
[өңдеу | қайнарын өңдеу]+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 |
Қасиеттері
[өңдеу | қайнарын өңдеу]- , егер — жай сан болса. Жекеше түрі: болғанда ;
- , егер m мен өзара жай болса. Яғни Эйлер функциясы мультипликативті;
- , егер m мен өзара жай болса. Бұл Эйлер теоремасы болып табылады;
- , если — Ең кіші ортақ еселік, aл — Ең үлкен ортақ бөлгіш.
Асимптоталық байланыстар
[өңдеу | қайнарын өңдеу]- мұндағы — белгілі бір тұрақты;
Аналитикалық байланыстар
[өңдеу | қайнарын өңдеу]- Эйлер функциясы Мёбиус функциясымен де байланысы бар:
- Дирихле қатарын коэффициенттерімен Риман дзета-функциясы арқылы өрнектеуге болады:
- Ламберт қатары қосындысын коэффициенттерімен:
- мұндағы .
- , мұндағы .
Компьютерлік іске асырылуы
[өңдеу | қайнарын өңдеу]Си тілінде
[өңдеу | қайнарын өңдеу]Төмендегі функция көбейтіндісін есептейді. Бұл санын жай сандарға көбейткіштерге 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;
}
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
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
![]() |
Бұл — математика бойынша мақаланың бастамасы. Бұл мақаланы толықтырып, дамыту арқылы, Уикипедияға көмектесе аласыз. |