Re: Egyptiläisistä murtoluvuista

[vastaus aiempaan viestiin]

Muuntaessani I. Stewartin egyptiläisten murtolukujen hakualgoritmia
olin unohtanut erään hakua olennaisesti nopeuttavan ehdon.
Niinpä esim. viime viestissäni mainitsemani tapaus
(luvun 1 hajottaminen 9 erikokoisen yksikkömurtoluvun summaksi) sujuu
korjauksen jälkeen näin:

NMIN=3 NMAX=30
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   0.220

eli aikaa menee vain 0.22 sekuntia, kun aikaisemmin tarvittiin
173 sekuntia (samoilla NMIN-, NMAX-rajoituksilla).
Nopeutus on siis tässä esimerkissä yli 700-kertainen.
.......................................................................
Ajoajan kannalta on olennaista supistaa nimittäjien vaihteluväliä NMIN-
ja NMAX-täsmennyksillä (silloin kun tietää, että ratkaisu löytyy
näilläkin rajoituksilla). Etenkin NMAX vaikuttaa tässä suhteessa
kriittiseltä. Jos edellisessä esimerkissä valitaan väljemmin
NMIN=1 NMAX=100,
saadaan
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   88.485
eli aikaa menee 400 kertaa enemmän. Kun jätin NMAX-rajoituksen kokonaan
pois, laskenta tuntui kestävän ikuisuuksia, joten keskeytin sen (ENTER-
napilla).
Stewartin alkuperäinen algoritmi on siis todella hidas.

Totesin:
> 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.

Saattaessani nyt paremmin tehdä kokeiluja havaitsin pian, ettei tulos
sittenkään ole aina yksikäsitteinen, vaikka useimmiten se sitä on.
On jopa ilmeistä, että luvuilla M/N (M<N) N:n kasvaessa rajatta
niiden lukujen osuus, joilla k termin minimaalinen esitys ei ole
yksikäsitteinen, lähenee nollaa.

Kuitenkin esim. luvulle 2/11 on peräti 4 erilaista 3 termin
"minimaalista esitystä":
.......................................................................
Ensin todetaan, että
EGYPT 2/11,3 / 2/11=1/10+1/15+1/66
.......................................................................
Tällöin pelkät erilaiset minimaaliset ratkaisut saadaan seuraavasti:
NMAX=66  / suurin sallittu nimittäjä
SAVE=EG.TXT / kaikki ratkaisut talteen
EGYPT 2/11,3 / 2/11=1/10+1/15+1/66
LOADP EG.TXT
Denominators of Egyptian fractions for 2/11:
7 42 66
8 24 66
9 18 66
10 15 66

Suoraan EGYPT tarjoaa aina ratkaisuista sen, jolla toiseksi suurin
nimittäjä on pienin jne.
.......................................................................
Vastaavasti 8/11 on yksinkertaisin murtoluku, jolla ei ole yhtään
3 termin esitystä:
EGYPT 8/11,3 / No solution found!
EGYPT 8/11,4 / 8/11=1/2+1/6+1/22+1/66
.......................................................................

EGYPT tulee mukaan SURVO MM:n versiosta 2.23 lähtien, mutta sen
saa vanhempiin versioihin ympätyksi seuraavasti:

Olen siirtänyt uusimman COMB-modulin, johon myös EGYPT sisältyy,
Survon verkkosivuille tilapäisesti osoitteeseen

www.survo.fi/tmp/_comb.exe 

Tämä tiedosto on kopioitava Survon ohjelmien päähakemistoon
<Survo>\U
ja jotta Survo tunnistaisi uuden EGYPT-komennon,
tulee SURVOEXE.SYS-tiedostoon tehdä seuraava lisäys:

Ota tyhjään toimituskenttään SURVOEXE.SYS komennolla
LOADP <Survo>\U\SURVOEXE.SYS
Lisää listan loppuun rivi
EGYPT _COMB
ja talleta uusi lista SAVEP-komennolla (muuntamalla edellä oleva
LOADP SAVEP:ksi ja aktivoimalla).

Pienenä lisäpähkinänä (palkinnoitta) pyytäisin selvittämään, mikä
on yksinkertaisin M/N, jolla 3 termin minimaalisia ratkaisuja on
ainakin 20. Yksinkertaisella tarkoitan sitä, että N on mahdollisimman
pieni.

-Seppo

Luettelo keskustelunaiheista

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!