1. Domácí úkol: Eulerova a Carmichaelova funkce

Úvod

Cílem prvního úkolu je seznámit se se základy Julia (podmínky, cykly, metody, atp.), typového systému se dotkneme jen částečně a necháme si ho hlavně na další úkoly. Vypracování tohoto úkolu by vám nemělo zabrat příliš času.

Cvičnými objekty v tomto úkolu pro nás budou Eulerova a Carmichaelova funkce, které se objevují a používají v problémech souvisejících s teorií čísel. V tomto prvním jednodušším úkolu se budeme zabývat jejich implementací v Julia.

Funkce jsou pojmenovány po Leonhardovi Eulerovi (nejen matematik žijící v osmnáctém století, původem ze Švýcarska) a Robertu Carmichaelovi (americký matematik žijící v devatenáctem a dvacátem století).

Teoretický background

Pro kladné celé $n$ definujeme hodnotu Eulerovy funkce $\varphi(n)$ jakožto počet přirozených čísel mezi $1$ a $n$ (včetně mezí), která jsou nesoudělná s $n$ (dvě celá čísla $m$ a $k$ jsou nesoudělná, právě když jejich největší společný dělitel je roven $1$, tj. $\gcd(m, k) = 1$). Například tedy platí

Pro kladné celé $n$ definujeme hodnotu Carmichaelovy funkce $\lambda(n)$ jakožto nejmenší kladné celé $m$, pro které platí rovnosti (tj. zbytek po dělení čísla $a^m$ číslem $n$ je roven $1$)

pro všechna kladná celá $a$ menší než $n$ a nesoudělná s $n$. Například tedy platí

Implementační pokyny

V souboru main.jl doplňte implementaci funkcí euler (Eulerova funkce $\varphi$) a carmichael (Carmichaelova funkce $\lambda$), které budou přijímat kladná celá čísla nebo vektory kladných celých čísel a počítat odpovídající funkční hodnoty. Pokud je na vstupu vektor, tak ho naše implementace nebude modifikovat, ale vrátí nový vektor s napočítanými hodnotami. Například

julia> include("main.jl")

julia> euler(6)
2

julia> euler(7)
6

julia> euler([6, 7])
2-element Vector{Int64}:
 2
 6

julia> carmichael(big"123456")
5136

julia> carmichael(UInt64[1, 2, 3, 4])
4-element Vector{Int64}:
 1
 1
 2
 2

Další ukázky lze nalézt v přiložených testech v adresáři test.

V případě neceločíselného typu argumentu (např. float nebo řetězec) dojde k vyvolání výjimky MethodError. Pokud je argument záporný celočíselný, pak dostaneme výjimku ArgumentError.

Věnujte péči výpočtu zbytku po dělení mocniny v Carmichaelově funkci (tj. vyhněte se nutnosti explicitně počítat $a^m$, N.B.: $(ab) \bmod n = (a \bmod n) (b \bmod n) \bmod n$). V implementaci můžete použít metodu gcd pro výpočet nejmenšího společného dělitele, která je dostupná v prostředí Julia a poradí si s mnoha různými datovými typy (vytvářet vlastní implementaci nejmenšího společného dělitele tedy nemusíte).

Metoda musí být typově stabilní. Tj. pokud dostaneme argument typu např. UInt64, pak návratová hodnota je také typu UInt64.

Svou implementaci můžete lokálně snadno otestovat příkazem julia test/runtests.jl, výstup by měl vypadat přibližně takto:

$ julia test/runtests.jl
┌ Info:
│ Running tests in test_carmichael.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Carmichael's function: types of argument                     |    4      4  0.2s
Test Summary:                                                | Pass  Total  Time
Carmichael's function: first few values                      |   11     11  0.0s
Test Summary:                                                | Pass  Total  Time
Carmichael's function: vector argument                       |    2      2  0.1s
Test Summary:                                                | Pass  Total  Time
Carmichael's function: various data types                    |    4      4  0.4s
┌ Info:
│ Running tests in test_euler.jl...
└ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Test Summary:                                                | Pass  Total  Time
Euler's function: types of argument                          |    4      4  0.0s
Test Summary:                                                | Pass  Total  Time
Euler's function: first few values                           |   10     10  0.0s
Test Summary:                                                | Pass  Total  Time
Euler's function: vector argument                            |    2      2  0.0s
Test Summary:                                                | Pass  Total   Time
Euler's function: various data types                         |    4      4  11.5s
Test Summary:                                                | Pass  Total  Time
Euler's function: Multiplicativity test                      |    1      1  0.6s

Tyto testy se spouští i automaticky na Gitlabu.

Součástí vyhodnocení řešení bude porovnání rychlosti i robustnosti vaší implementace s ostatními studentskými řešeními.

Řešení a odevzdání

Opět vytvořte větev odvozenou z větve assignment/01-functions a nezvěte ji solution/01-functions. Do solution/01-functions vložte své řešení editací souboru main.jl případně přidáním testů do složky test. Až budete se svým řešením spokojeni, vytvořte MR (to můžete i dříve, aspoň uvidíte výsledek testů, pokud je nespouštíte lokálně) a přiřaďte mě k němu jako assignee. Tímto aktem úkol odevzdáte.