[es] - Least denominator

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Least denominator

^{03.01.2006. u 23:08 - pre 248 meseci}

Za date realne

pronaći najmanje

tako da

za neko

.

Naravno, od interesa je slučaj kada nema celog broja između

. Takođe, dobrodošle su i sve ideje u vezi sa specijalnim slučajem

ili

.

Kako to propozicije nalažu, bio bi red da opišem i teškoće na koje sam naišao u pokušaju da rešim ovaj zadatak(?).

Ograničimo se na slučaj

.

Uzmimo neko prirodno

i uočimo sve razlomke

gde je

. Sada uočimo skup svih otvorenih intervala (sadržanih u

) u kojima nema ni jednog od uočenih racionalnih brojeva. Na kraju, od tih intervala napravimo skup

samo onih intervala koji sadrže i barem jedan razlomak oblika

(

). Dakle, za svako

važi

. Primetimo i to je

.

I pored toga, što sam primetio neke zanimljive "šeme" u rasporedu svih pravih racionalnih sa imeniocem ne većim od date granice - ipak ne mogu da uočim nikakvu upotrebljivu vezu izemeđu već pomenutih intervala.

Takođe, u opštem slučaju ne važi

, ali nisam previše "kopao" u tom pravcu...

Jedine stvari koje mi izgledaju povezane sa ovim zadatkom su: Farey-ev niz i Ford-ov krug - ali, očigledno je da mi to nije mnogo pomoglo

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{04.01.2006. u 01:33 - pre 248 meseci}

Hm, ako sam te dobro shvatio, zaključujem da bi traženo

trebalo da bude rešenje sistema

- ali ne znam je li to od pomoći niti kako bi se ti uslovi u najopštijem slučaju rešili. Naravno, očigledno je da je

. Ali, udubiću se kasnije

Napomena: Ako

, onda se sistem sastoji od dve jednačine:

.

_{[Ovu poruku je menjao Farenhajt dana 04.01.2006. u 03:05 GMT+1]}

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{04.01.2006. u 05:38 - pre 248 meseci}

Sviđa mi se u kom pravcu razmišljaš

(veliko hvala na zanimljivim idejama) i dakle, slažem se sa svime što si napisao, osim što mi ovo nije jasno:

Citat:

Farenhajt:

Jer na primer:

daju

pa dobijamo

.

Inače, nisam pomenuo, jer mi se činilo da nije bitno ali

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.

+3 Profil

Re: Least denominator

^{04.01.2006. u 08:35 - pre 248 meseci}

Citat:

Farenhajt:

Mala ispravka, treba

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{04.01.2006. u 08:46 - pre 248 meseci}

Kontraprimer stoji. Dakle, pošto se dati uslov svodi na

, ideja je da posmatramo niz intervala

, sa zaključkom da je "rastezanje" intervala

dovoljno vršiti dok ne postane dugačak bar 1, jer će onda zasigurno obuhvatiti i neki ceo broj (što naravno ne znači da se do celog broja ne može stići i u manje rastezanja - cf. kurziv). Na osnovu ove ideje s "rastezanjem" se i očigledno formulišu oni uslovi s celim delovima.

Biće da sam podsvesno radio sa

, u kom slučaju tvoj primer ima trivijalno rešenje

.

Međutim, možda mogu da se iščupam s procenom

, jer će onda interval postati strogo duži od

, pa će važiti i stroge nejednakosti.

Naravno, ovaj supremum koji si naveo stoji (očit je i iz procedure "rastezanja"), ali nam on neće pomoći da nađemo minimalno

.

EDIT: Srki me preduhitrio sa zaključkom

I kad već ispravljamo, onda treba izbaciti "

" jer se to automatski dobija iz

.

DODATAK: Treba doterati i uslove s celim delovima, jer ako su

uzastopni celi brojevi, kao rešenje se dobija

, a treba nam

.

_{[Ovu poruku je menjao Farenhajt dana 04.01.2006. u 10:32 GMT+1]}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{04.01.2006. u 11:50 - pre 248 meseci}

Elem, malo sam se pozabavio, te ću vas sad smarati s razdvajanjem slučajeva:

Ovde

mora biti

. Oba slučaja objedinjuju se formulom

;

Ako je

, onda je

; ako je

, onda je

; ako je

, onda je

; i tako dalje. Formula će glasiti

;

Ovaj slučaj možemo svesti na prethodni ako posmatramo

, pa zaključujemo da je

;

Ovde moramo razlikovati dve mogućnosti:

. Tada je

(Ne vidim kako bi se

objedinili u jednu formulu, ali su ideje dobrodošle. Slučaj

pokriva situacije tipa

gde je

, a

proizvoljno mali pozitivni brojevi - tu nam baratanje s

ničemu ne služi.)

Dakle, kad sve sumiramo, dobijamo

.

(Napomena: Slučaj

obuhvaćen je prvom granom funkcije jer ako je

celobrojno, onda

)

Izvol'te s diskusijom i kontraprimerima.

_{[Ovu poruku je menjao Farenhajt dana 04.01.2006. u 13:12 GMT+1]}

Odgovor na temu

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3654
*.jetstream.xtra.co.nz.

+3 Profil

Re: Least denominator

^{04.01.2006. u 12:24 - pre 248 meseci}

Da budem iskren nisam bas citao tvoju poruku nego sam letimicno preleteo. Da li je ovaj primer obihvacen tvojom formulom:
npr. a=4.499999999999999999999 b=4.50000000000000000000000000001.
Tu bi resenje bilo q=2 a p=9.

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{04.01.2006. u 12:42 - pre 248 meseci}

U pravu si, formula ne radi za taj slučaj, kao ni za srodne slučajeve "okolina" brojeva

, što bi potpadalo pod slučaj

.

Ali nek to uranium krpi

Elem, tu se vraćamo na onu prvu ideju, da se traži minimalno rešenje jednačine

. Ta jednačina za tvoj primer daje ispravno rešenje

.

_{[Ovu poruku je menjao Farenhajt dana 04.01.2006. u 13:49 GMT+1]}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{04.01.2006. u 13:27 - pre 248 meseci}

Evo dokonah nešto: Mislim da se taj slučaj može rešiti preko izraza

, gde je

"ceiling" funkcija (ne znam joj ime na srpskom), dakle najmanji ceo broj ne manji od argumenta funkcije, a

je razlomljeni deo. (Inače se "ceiling" može izraziti kao

).

Dakle, ako u slučaju

stavimo

, onda se jednačina iz prethodne poruke svodi na

. Ovo pak znači da je

, odakle dobijamo

. Na osnovu ovoga zaključujemo da je najmanje takvo

dato izrazom iz prvog pasusa.

Dopune?

_{[Ovu poruku je menjao Farenhajt dana 04.01.2006. u 14:28 GMT+1]}

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{04.01.2006. u 19:46 - pre 248 meseci}

Neka je

, onda imamo da je traženo

, ali

.

Znači ipak imamo dva podslučaja, onaj koji je rešio Farenhajt i ovaj drugi kada je

iz koga sledi

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{04.01.2006. u 21:46 - pre 248 meseci}

Da, ja sam se ograničio na slučaj kad

premaši

, a

ostane manje od

. Naravno, u opštem slučaju će prvi izraz premašiti neko

, a drugi će ostati manji od

.

Što se primera tiče, recimo za

treba dobiti

, a to ne proizlazi ni iz jedne dosad ponuđene formule, osim iz numeričkog rešavanja sistema

.

_{[Ovu poruku je menjao Farenhajt dana 04.01.2006. u 22:52 GMT+1]}

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{05.01.2006. u 05:51 - pre 248 meseci}

Ovo što sledi odnosi se samo na preostali podslučaj slučaja 4b.

Primetimo to da ako

, donja granica koju dobijamo za broj

izgleda neupotrebljiva jer se za svako unapred dato

mogu naći

tako da bude

. Pomenuo bih još samo to da je ovakvih slučajeva neprebrojivo mnogo (svako

za koje je

ali i još neprebrojivo mnogo onih za koje je

)

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{05.01.2006. u 06:58 - pre 248 meseci}

Ideja (koju pišem kako mi je pala na pamet, te nemam pojma je li plodonosna): Ispostavilo se da su nam problematični samo oni slučajevi gde je

(ili

, to jest ono

iz inicijalne postavke) veće od 1.

Možemo li sačiniti algoritam u suprotnom smeru - dakle, možemo li sažeti interval

tako da

dospe u okolinu broja čiji je razlomljeni deo oblika

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{05.01.2006. u 20:30 - pre 248 meseci}

Ako sam dobro razumeo, tražimo

tako da

i da pri tom bude

. Ideja je odlična, ali jedini problem je u tome što moramo uzeti da bude baš

Znači pitanje je da li se može doći do neke dobre procene za

a da to ne zahteva previše dobru procenu za

.

Primer:

, onda je

, pa ako bi probali sa

, dobili bi da je

, pa smo opet došli na problematičan slučaj. Takođe, ne vidim neki način (osim direktne provere) da utvrdimo da li je slučaj (kada je

) problematičan ili ne.

U svakom slučaju, od srca se zahvaljujem na svoj dosadašnjoj pomoći, pre svih Farenhajt-u a naravno i srki-ju.

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{06.01.2006. u 05:31 - pre 248 meseci}

Ipak sam našao način da odredimo da li se radi o problematičnom podslučaju ili ne:

akko je podslučaj problematičan tj.

akko podslučaj nije problematičan tj.

.

Za obrazloženje je dovoljno da primetimo da uvek važi tačno jedna od sledeće dve situacije:

1.

za pogodno izabrano

.

U prvom slučaju je

, pa dobijamo

a u drugom slučaju je

pa je

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{07.01.2006. u 01:36 - pre 248 meseci}

Evo tri bitna rezultata koja su nam dosad promakla:

Pre svega:

Citat:

Farenhajt
Evo dokonah nešto: Mislim da se taj slučaj može rešiti preko izraza

1. Tačan izraz treba da glasi

, jer će se za celobrojno

u prvom slučaju dobiti pogrešan rezultat.

2. Ako je

, jasno je da je

. Dakle, sva razmatranja slučaja 4b možemo svesti na interval

, te ćemo nadalje podrazumevati da je

.

3. Iz

sledi

, te zapravo možemo staviti

. Ukoliko ovaj slučaj nije problematičan, tj. ako potpada pod 1,2,3,4a, našli smo

, te onda imamo da je

, pošto je

. Ukoliko slučaj jeste problematičan, dakle ako opet potpada pod 4b, ponavljamo postupak svodeći brojeve na razlomljene delove, imajući u vidu da važi sledeće:

. Iz ovoga sledi da ćemo konačnim brojem rekurzija sigurno stići do imenioca

, te ćemo onda lako dobiti i

.

E sad, da li ovo ikako koristi... uraniume, priskoči i razradi

Numerički primer:
1.

. Slučaj je problematičan jer je

.
2.

. Ovaj slučaj nije problematičan jer

. Stoga dobijamo

.
3. Polazni interval sažimamo na

i sada je

_{[Ovu poruku je menjao Farenhajt dana 07.01.2006. u 11:49 GMT+1]}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{07.01.2006. u 11:28 - pre 248 meseci}

Dodatak

Na osnovu iznetog u prethodnoj poruci, može se formulisati opšti numerički postupak za traženje razlomka

. Najlakše će biti da se postupak ilustruje primerom. (Napomena: U tabeli se parne vrste dobijaju od neparnih uzimanjem recipročnih vrednosti svih argumenata, a neparne od parnih svođenjem argumenata na interval

. Takođe, u koloni a nalaze se transformacije argumenta

, a u koloni b transformacije argumenta

, što znači da u nekim vrstama veći broj dolazi pre manjeg. To, međutim, nije od značaja za postupak. Sve vrednosti zaokruživane su na 4 decimalna mesta.)

Naći

Na kraju stižemo do intervala unutar koga se nalazi ceo broj i tu obustavljamo postupak. Uzimamo vrednost

i izjednačavamo je sa

. Rešavanjem jednačine dobijamo

. Dakle,

.

Postupak, koliko mi se čini, funkcioniše i na segmentu

:

Naći

Sada imamo

.

_{[Ovu poruku je menjao Farenhajt dana 07.01.2006. u 15:53 GMT+1]}

Odgovor na temu

uranium
Beograd

Član broj: 60097
Poruke: 543
*.eunet.yu.

Jabber: uranium@elitesecurity.org
ICQ: 324386953

+5 Profil

Re: Least denominator

^{07.01.2006. u 15:35 - pre 248 meseci}

Farenhajte, svaka ti čast za ovo što si smislio!!!

Nemam reči (nor appropriate emoticons

) kojima bih iskazao divljenje...

Veliko ti hvala!

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Odgovor na temu

Farenhajt
Goran Kapetanović
Beograd

Član broj: 78132
Poruke: 449
*.tehnicom.net.

+6 Profil

Re: Least denominator

^{07.01.2006. u 16:08 - pre 248 meseci}

Dodatak 2

U stvari, kad se bolje proanalizira, zaključujemo sledeće:

Brojeve

treba razviti u verižne razlomke po modelu

(gde je

za brojeve iz intervala

, ali u opštem slučaju nema prepreke da bude i veće od nule). Zatim se odgovarajuće karike u ta dva razvoja porede. Čim se pronađu karike koje se razlikuju za barem

(obeležimo te karike sa

), razlomak se tu preseca i završava vrednošću

, pa se onda tako dobijeni verižni razlomak vraća u svedenu formu, čime se dobija traženi razlomak

.

Ukoliko razvoji imaju različit broj karika, treba zamisliti da se kraći završava sa

.

Ukoliko je

(ili uopšteno

, onda se u razvoju broja

gledaju samo prva i druga karika: ukoliko je prva karika veća od 1, odbacuje se čitav razvoj posle te karike, a vrednost karike ostaje nepromenjena, a ukoliko je prva karika jednaka 1, razvoj se prekida posle druge karike i ta se karika povećava za jedan.

Očigledno, ovako formulisan postupak može funkcionisati i za

, s tim što će se karike i generisati i porediti jedna po jedna.

_{[Ovu poruku je menjao Farenhajt dana 08.01.2006. u 17:26 GMT+1]}

Odgovor na temu

Bojan Basic
Novi Sad

SuperModerator
Član broj: 6578
Poruke: 3996
*.dialup.neobee.net.

Jabber: bojan_basic@elitesecurity.org
ICQ: 305820253

+626 Profil

Re: Least denominator

^{07.01.2006. u 20:37 - pre 248 meseci}

Evo i drugog algoritma: krenemo redom od jedinice i čekamo kad ćemo dobiti ceo broj u intervalu koji se dobija kada pomnožimo početni interval sa brojem koji imamo.

E sad, mene zanima koja je razlika između ovog i Farenhajtovog algoritma? Iz navedenih primera mi deluje da je njegov algoritam brži, ali da li je zaista tako ili ima neka druga caka?

Izvinjavam se što nisam mnogo razmišljao o ovome što sam napisao, pa ako sam lupio nešto očigledno nemojte zameriti.

Ljubičice crvena, što si plava kô zelena trava.

Odgovor na temu