[viesti Survo-keskustelupalstalla (2001-2013)]
| Kirjoittaja: | Seppo Mustonen |
|---|---|
| Sähköposti: | - |
| Päiväys: | 13.1.2005 11:45 |
Äskeisen talvipähkinän ratkaisun avain oli muuntaa taulukon luvut yksikkömurtolukujen summiksi. Laatiessani tehtävää en tiennyt, että muinaiset egyptiläiset esittivät murtoluvut tähän tyyliin ja vieläpä juuri niin, että kaikkien nimittäjien tuli olla eri lukuja. (Tämän tiedon lähteille pääsin, kun uteliaisuuttani kokeilin hakua "unit fraction" verkosta.) Egyptiläisille ei siis esimerkiksi 2/7=1/7+1/7 kelvannut vaan se piti esittää muodossa 2/7=1/4+1/28. Syitä esitystapaan ei ole täysin saatu selvitettyä. Siihen vaikutti osaltaan merkintätyyli. Yksikkömurtoluvut ilmaistiin panemalla vastaavan kokonaisluvun yläpuolelle soikio eikä yleisemmille murtoluvuille ollut omaa merkintää. Esitystavalla lienee ollut jopa käytännön sovelluksia. Esim. jos tulee jakaa 7 samankokoista viljasäkillistä tasan 8 viljelijän kesken, jokainen saisi siis 7/8-säkillistä. Se vaikuttaa hankalalta käytännössä ja saattaisi johtaa riitaan. Luku 7/8 egyptiläisittäin esitettynä on 7/8=1/2+1/4+1/8, jolloin jako onnistunee käytännössä sujuvasti, kun ensin 4 säkkiä puolitetaan, 2 seuraavaa puolitetaan kahdesti ja ainoa jäljelle jäänyt puolitetaan kolmasti. Tällöin jokainen saa yhden puolikkaan, neljäsosan ja kahdeksasosan. Verkosta löytyy haulla "egyptian fractions" paljonkin tietoa. Hyviä tietolähteitä ovat mielestäni mm. seuraavat: http://www.ics.uci.edu/~eppstein/numth/egypt/ (David Eppstein) http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html Aihe on kiinnostanut matemaatikkoja läpi matematiikan historian. Viime vuosikymmeninä (osittain aikaisemminkin) on kehitetty lukuisia algoritmeja murtolukujen esittämiseksi egyptiläisittäin. Esitys ei ole koskaan yksikäsitteinen, sillä esim. viimeinen termi 1/n voidaan aina jakaa kahdeksi pienemmäksi 1/(n+1) + 1/[n*(n+1)]. Kuitenkin jos rajoitetaan termien lukumäärä vakioksi ja valitaan se esitys, jossa viimeinen termi on suurin mahdollinen eli jakaja pienin mahdollinen, saadaan tulos, joka vaikuttaa yksikäsitteiseltä. En ole tähän mennessä keksinyt tälle vastaesimerkkiä enkä mitään viitteitä verkossa avautuvista lähteistäkään. Käytin jonkin verran aikaa etsiäkseni sellaista algoritmia, joka antaisi edellä kuvatussa mielessä hyviä tuloksia. Päädyin David Eppsteinin sivuilta löytyvään, alunperin I. Stewartin (1992) esittämään raakaan hakualgoritmiin http://www.ics.uci.edu/~eppstein/numth/egypt/force.html#short josta Eppstein on tehnyt C++ -ohjelman http://www.ics.uci.edu/~eppstein/numth/egypt/efrac.c Olen muuttanut ohjelmakoodin tavalliseksi C-koodiksi, lisännyt siihen eräitä mielestäni hyödyllisiä, mm. hakua rajoittavia optioita ja liittänyt sen nykyiseen Survoon (COMB-modulin kylkiäisenä). Egyptiläisiä k termin mittaisia yksikkömurtolukusummia tehdään rationaaliluvulle m/n, missä m ja n ovat positiivisia kokonaislukuja yksinkertaisesti komennolla EGYPT m/n,k Esimerkkejä: EGYPT 7/8,3 / 7/8=1/2+1/4+1/8 EGYPT 36/37,4 / No solution found! EGYPT 36/37,5 / 36/37=1/2+1/3+1/9+1/37+1/666 Tässä nähdään, miten ykkönenkin voidaan esittää erisuurten yksikkö- murtolukujen summana: EGYPT 1/1,3 / 1/1=1/2+1/3+1/6 EGYPT 1/1,4 / 1/1=1/2+1/4+1/6+1/12 EGYPT 1/1,5 / 1/1=1/2+1/4+1/10+1/12+1/15 EGYPT 1/1,6 / 1/1=1/3+1/4+1/6+1/10+1/12+1/15 ........................................................................ Jos yrittää jakaa ykköstä 7 tai useampaan osaan, haku kestää edellisiin verrattuna paljon kauemmin. Tällöin toiminta nopeutuu, kun rajoitetaan nimittäjiä sekä alhaalta (NMIN) että ylhäältä (NMAX) päin. NMIN=3 NMAX=30 EGYPT 1/1,7 / 1/1=1/3+1/4+1/9+1/10+1/12+1/15+1/18 TIME COUNT START EGYPT 1/1,8 / 1/1=1/4+1/5+1/6+1/9+1/10+1/15+1/18+1/20 TIME COUNT END 5.422 TIME COUNT START EGYPT 1/1,9 / 1/1=1/4+1/6+1/8+1/9+1/10+1/12+1/15+1/18+1/24 TIME COUNT END 173.454 ........................................................................ Myös kaikkien löydettyjen esitysten nimittäjät saa talletetuksi tekstitiedostoon (SAVE). Esim. SAVE=EG.TXT EGYPT 36/37,5 / 36/37=1/2+1/4+1/6+1/18+1/1332 LOADP EG.TXT Denominators of Egyptian fractions for 36/37: 2 4 5 44 4070 2 4 5 45 1332 2 4 6 18 1332 2 4 5 44 4070 2 4 5 45 1332 2 4 6 18 1332 jne. ........................................................................ Talvipähkinän ratkaisu on näillä keinoin mutkatonta. Alkuperäinen taulukko murtoluvuin: _" 23/22 _A 15/56 _D 1/13 _E 1/14 _I 251/510 _L 173/720 _R 1/4 _O 1/12 _S 191/630 _T 1/11 _U 307/1140 _V 1/2 Luomalla blokkisiirroin seuraava asetelma EGYPT 23/22 2 EGYPT 15/56 2 EGYPT 1/13 1 EGYPT 1/14 1 EGYPT 251/510 3 EGYPT 173/720 3 EGYPT 1/4 1 EGYPT 1/12 1 EGYPT 191/630 3 EGYPT 1/11 1 EGYPT 307/1140 3 EGYPT 1/2 1 ja jatkuvalla aktivoinnilla saadaan kaikki tarvittavat tiedon palaset: EGYPT 23/22 2 / 23/22=1/1+1/22 " EGYPT 15/56 2 / 15/56=1/7+1/8 A EGYPT 1/13 1 / 1/13=1/13 D EGYPT 1/14 1 / 1/14=1/14 E EGYPT 251/510 3 / 251/510=1/3+1/10+1/17 I EGYPT 173/720 3 / 173/720=1/9+1/15+1/16 L EGYPT 1/4 1 / 1/4=1/4 R EGYPT 1/12 1 / 1/12=1/12 O EGYPT 191/630 3 / 191/630=1/5+1/18+1/21 S EGYPT 1/11 1 / 1/11=1/11 T EGYPT 307/1140 3 / 307/1140=1/6+1/19+1/20 U EGYPT 1/2 1 / 1/2=1/2 V Jokaisen EGYPT-komennon k-parametri on pienin mahdollinen (eli sellainen, josta ei tule ilmoitusta "No solution found!"). -Seppo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!