ISETL-Harjoitus 3, 1999. Kertausta, alkuluvut, kongruenssi

Tehtävä 1. Kertausta

a) Selvitä mitä tekevät seuraavat ISETL-rivit: 
>  At := [4,6,4,7,8,-4,3]; Bt := [6,1,3,5]; #At; #Bt;
>  At + Bt;  At - Bt;
>  At inter Bt;
>  %+Bt; %*Bt;
>  Aj := {a|a in At}; Bj := {b|b in Bt}; Aj;Bj; #Aj; #Bj;
>  Aj union Bj; Aj inter Bj; Aj - Bj;
>  7 in Aj; 5 in Aj; 5 notin Bj;
>  Aj - Bj = Aj inter (Aj - Bj);
>  Aj subset (Aj - Bj); (Aj - Bj) subset Aj;
b) Muodosta tuplet tai joukot:
1) Joukko, jossa on luvut -7,-4,-1,2,...,101.
2) Tuple, jossa ovat luvut 2,3,..., floor(Ö157).
3) Joukko, jossa on välin [-100,100] ne kokonaisluvut, jotka ovat jaollisia sekä seitsemällä että kolmella.
4) Tuple, jossa ovat lukujen 4259, 1311, 232 ja 2413 jakojäännökset jaettaessa luvulla 3, samassa järjestyksessä.

Tehtävä 2. Ohjelmointia: interaktiivinen tapa

Selvitä rivi riviltä, mitä seuraavat ISETL-syötteet tekevät: 
>  a := 96; b := 36;
>  r0 := a; r1 := b; jj := r0 mod r1;
Tilanne: [r0,r1,jj] = 
>  if (not jj = 0) then r0 := r1; r1 := jj; jj := r0 mod r1; end if;
Tilanne: [r0,r1,jj] = 
>  if (not jj = 0) then r0 := r1; r1 := jj; jj := r0 mod r1; end if;
Tilanne: [r0,r1,jj] = 
>  if (not jj = 0) then r0 := r1; r1 := jj; jj := r0 mod r1; end if;
Tilanne: [r0,r1,jj] =

Jatka prosessia kunnes jj = 0. Mitä ohjelma tekee?

Tehtävä 3. Ohjelmointia: funktiomainen ohjelma

Pue edellinen prosessi funktioksi nimeltä sytti, joka saa kokonaislukusyötteet a ja b, toistaa if-lauseessa tehtäviä käskyjä kunnes jj = 0 ja lopulta tulostaa lukujen a ja b suurimman yhteisen tekijän.
Huomaa, että if-then-lause tulee korvata while-do-rakenteella, jolloin kyseistä käskyriviä suoritetaan niin kauan kuin jj ¹ 0. Aloitat siis: 
> sytti := func(a,b);

Tehtävä 4. Tekijät etsivä funktio

Tee funktio tekijat, joka etsii ja palauttaa annetun positiivisen kokonaisluvun b positiiviset tekijät.
Opastus: Päätetään ensin, millaisena tulos halutaan. Koska kysytään vain tekijötä, ei niiden kertalukuja, riittää hyvin tulos joukkona. Tekijän matemaattinen kriteeri:
a\mid b     Û     b = ka jollakin k Î Z.
 
Kaikki tekijät ovat joukko { a Î Z \mid $ k Î Z : b = ka }. Tämä pitää pukea ISETL-muotoon {a | a in A : exists k in B : b = k*a}, jossa vielä pitää muuttaa esiintyvät joukot A ja B sopiviksi äärellisiksi joukoiksi tai tupleiksi. Sitten pitää kääriä saavutus funktioksi. Aloita 
> tekijat := f ... ;

Tehtävä 5. Alkulukutesti (uudelleen)

Tee funktio alkulukuko, joka tutkii onko annettava luku alkuluku. Mieti ensin, mitä alkuluku tarkoittaa. Vertaa edelliseen tehtävään, voitko hyödyntää siinä saatua tietoutta. Sen onko luku toisen tekijä voit testata suoraan mod-käskyllä.
Opastusta: Tee ensin exists-rakenne, joka selvittää onko luku jaollinen millään luvuista 2, 3, ¼ Tietenkin pitää pysähtyä lukua yhtä pienempään; jopa vieläkin pienempi riittää, mikä? Lopuksi pistä eteen not (negaatio).

Tehtävä 6. Kongruenssifunktio

Olkoon m Î N ja a,b Î Z. Luvut a ja b ovat kongruentteja modulo m jos m | (a-b).
Merkintä: a º b (mod m).
Kirjoita funktio kongruenttiko, joka tutkii onko luku a kongruentti luvun b kanssa modulo m. Funktiollasi on siis kolme syötettä a,b ja m.

Tehtävä 7. Kongruenssitehtäviä

Aseta ISETLissä !setrandom off, niin ISETL ei luettele joukon jäseniä satunnaisesti. Olkoon kaikissa tämän tehtävän kohdissa k in [-20..20].
a) Muodosta kokonaislukujen k joukko kon3, jotka ovat kongruentteja 3:n kanssa modulo 5.
b) Muodosta kaikkien niiden kokonaislukujen k joukko kon4, jotka ovat kongruentteja neljän kanssa modulo 5, sekä vastaavat joukot kon1,kon2 ja kon5 ja kon0. Mitkä kaksi muodostamistasi joukoista ovat samoja? Miksi?
c) Mikä on äskeisten joukkojen yhdiste (unioni)?
d) Muodosta niiden kokonaislukujen x joukko, joiden jakojäännös jaettaessa viidellä on kolme. Mitä huomaat?
e) Mikä on kon1 inter kon2? Entä muille joukkopareille? Miksi?

Tehtävä 8. Lukujen kanoninen esitys (kotitehtäväksi)

Tee funktio, joka etsii annetulle positiiviselle kokonaisluvulle esityksen alkulukujen tulona, ts. sen kanonisen esityksen , jossa esiintyy vain alkulukujen potensseja. Esimerkiksi luvun 24 alkutekijäesitys on 23·3 ja luvun 50400 alkutekijäesitys on 2532527. Voit suunnitella ohjelman niin, että se antaa tuloksena joukon, jonka alkioina ovat järjestetyt kaksikot (tuplet) [p,a], jotka vastaavat tekijää pa.
File translated from TEX by TTH, version 1.96.
On 11 Oct 1999, 09:31.