i i “Grasselli-algoritem” — 2010/5/12 — 11:14 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 13 (1985/1986) Številka 2 Strani 70–74 Jože Grasselli: EGIPČANSKI ALGORITEM Ključne besede: matematika, teorija števil, egipčanski ulomki. Elektronska verzija: http://www.presek.si/13/13-2-Grasselli.pdf c© 1985 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. EGIPČANSKI ALGORITEM Pozitivne ulomke, ki so manjši od 1, zapisujemo danes največkrat v obliki F. Pri tem sta a, b tuji naravni števili in a < b, Zgled: r, f, j~. Ta zapis je plod dolgega razvoja. Nadomestil je razne drugačne oznake, ki so se uporabljale sko- zi zgodovino. Ustavimo se na kratko ob zapisu iz starega Egipta. Najdeni viri izpričujejo, da so imeli stari Egipčani že pred štiri tisoč leti posebne znake za osnovne ulomke tJ in še za ulomka f in t .Za drugačne ulomke posebnih znakov niso poznali. Pri zapisovanju teh drugih ulomkov so si pomagali z znaki za osnovne ulomke in včasih še z znakoma za 1- in f. Ulomek ~ so npr. naznačili tako, da so znak za i zapisali trikrat zapovrstjo. Domneva se , da so do tega zapisa prišli takole. Vemo, da je ~=_1_+_1_+_1_ 888 8 (1) (2) Simbola za seštevanje pri starih Egipčanih še ni bilo. Seštevanje so nakazali ta- ko, da so znake za števila, ki jih je treba sešteti, pisali drugega ob drugem. Gle- de na (1) so zato ~ zapisali s trikrat postavljenim znakom za osnovni ulomek 1 8 ' Ker je ~ = ~ + i. se namesto (1) dobi ~=_1_+_1_ 8 4 8 Res so ulomek ~ zapisovali tudi tako, da so postavili znaka za osnovna ulomka i in ; drugega za drugim. Namesto treh sta bila zdaj potrebna le dva znaka. Pri zapisu ulomka ~ je bilo treba osemkrat zapored postaviti znak za ~. To je precej nerodno . Ker je JL=2+_1_+_1_ 9 3 6 18 (3) so zadošča li tudi že znaki za f' t, ,-k- zapisani po vrsti. Namesto osmih so tu le trije znaki. Podobni zapisi kot za 1 in ~ so se ohranili iz starega Egipta še za nekatere druge pozitivne ulomke . Pri vsakem teh zapisov gre kakor v (2) in (3) za izra- zitev ulomka z vsoto različnih osnovnih ulomkov in kdaj še ulomkov t oziro- ma~. Ulomek i ~e v (2) izražen s samimi osnovnimi ulomki, torej brez uporabe ulomkov ~ in 4 ' Take izrazitve, ko ulomka ~ in f ne nastopata , so znane iz 70 starega Egipta še za nekatere druge ulomke. Tako vidimo, da so znali stari Egip- čani vsaj nekatere ulomke izražati le z vsoto različnih osnovnih ulomkov. Ko to opažamo, se vsiljuje vprašanje, ki nas bo v nadaljnjem zanimalo. Ali se da vsak od 1 manjši pozitivni ulomek izraziti kot vsota samih različnih osnovnih ulomkov? Odgovor na zastavljeno vprašanje daje egipčanski algoritem. Pridevnik egipčanski ne pomeni, da so algoritem odkrili Egipčani; nakazuje le povezanost algoritma z egipčanskim zapisovanjem ulomkov. Egipčanski algoritem sloni na tejle lastnosti naravnih števil: Če sta u in v tuji naravni števlll, 1 1. To ne gre, saj sta u, v tuji števili. Večkratn iki v zaporedju (7) naraščajo in presežejo vsako še tako veliko vrednost . Zato so vsi večkratniki od nekega dalje večji od v. Naj bo ku prvi večkratnik, ki je nad v . Ker noben več­ kratnik ni enak v, je (k - 1)u < v r > rl > .... Ker je vseh ulomkov, ki imajo imenovalec v, za števec pa naravno število med 1 in u, ravno u, je v (18) kvečjemu U ulomkov. Torej se naše ravnanje najpozneje po u korakih ustavi. Zadnji ulomek, ki v (18) nastopa, je ~. Za vsak ulomek -f-, pri katerem je'