collatz sor & fixpont

Algoritmusok

Van egy f függvényünk, amely így működik:
f(x) = x/2 ha x páros
f(x) = 3x+1 ha x páratlan

Ha egy természetes számra alkalmazzuk ezt a függvényt, majd az értékére újra és újra alkalmazzuk, akkor előbb-utóbb valószínűleg eljutunk az 1-hez. (Ez a Collatz-sejtés)

Az ismételt függvényalkalmazások során egy számsor képződik (milyen meglepő). Például ha a 13-tól indulunk, akkor:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Legyen C az a függvény amelyik egy természetes számhoz a hozzá tartozó
Collatz-sor hosszát rendeli hozzá. Például: C(13) = 10.

A kérdések a következők:
1, Van-e C-nek nem triviális (tehát nem 1 vagy 2) fixpontja? (x fixpontja f-nek, ha f(x)=x)
2, Ha igen, melyik szám(ok)?
3, Hogyan érdemes nekikezdeni egy ilyen probléma vizsgálatához? Vannak általános módszerek, technikák?

  • 5413 megtekintés

( NagyZ v | 2010. 09. 10., p – 15:09 )

jo vicc.

szerk: ja, most latom, hogy nem altalanos megoldast akarsz, hanem az algoritmusokba raktad. az altalanos leirast mar keresik egy ideje ;)

nem értem mi "általános", a témabeli kérdésnek semmi köze az utalt sejtéshez

pl attól hogy van egy fixpont még lehet minden kezdőszámból az 1-be jutni, ha ilyesmire gondoltál, pl (tfh) C(123)=123 az csak azt jelenti 123 lépésben jutunk az 1-be, a sejtés azt mondja minden C(n) véges

( apal v | 2010. 09. 10., p – 16:03 )

Hogyan érdemes nekikezdeni egy ilyen probléma vizsgálatához? Vannak általános módszerek, technikák?
asszem f^p fixpontjaira vannak mindenfele te'telek, pl hogy p<=60 koruli ertekig biztos hogy nincs nemtrivialis fixpont. az altalad is linkelt wikipedia oldal is; mondjuk nem az eredeti f(.) lekepezesre hanem annak vmi redukalt valtozatara (pl a paratlan szamokhoz nem a 3x+1-et rendeli hozza hanem a (3x+1)/2^k-t, ahol k>=1 mondvan hogy 3x+1 mindig paros ha x paratlan), es az sem kozvetlenul, de azert erdekesnek erdekes meg kiindulasnak jo. kicsit regebben volt mikor ezeket nezegettem, szoval lehet hogy nehol hulyeseg amit irtam, olvasd a't :]

egyebkent meg: irj ra egy programot ami kiszamolja C(k)-t es jatszogass vele ;) szep feladat, pl, ha c-ben irod vagy barmilyen nyelvben ami alapbol nem tamogat bigint-et. de meg lehet irni laza'n bc-ben is, es az valoszinuleg elegge hatekony lesz.

a.

Haha, már írtam egyet, pont emiatt gondolkoztam el.
http://projecteuler.net/index.php?section=problems&id=14

(pythonban, rekurzív, memoizálós, kb harminc sor, lassú mint a bűn. nekem olyan 12 másodperc a feladat a megoldása, ott meg van olyan LISP meg C megoldás ami egy másodperc alatt fut)

Igazából az érdekel, hogy milyen matematikai eszközökkel lehet kezelni egy ilyen problémát.

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

Igazából az érdekel, hogy milyen matematikai eszközökkel lehet kezelni egy ilyen problémát.
marmint ha az eredeti problemat (sejtest) oldanad meg? jo kerdes, nezd meg azokat a cikkeket, amikben az m-ciklusok (nem)letezeset bizonyitjak, valoszinuleg az jo kiindulas. az 1-ciklus kizarasat meg valoszinuleg moricka-modszerekkel is lehet bizonyitani, de lehet hogy alabecsulom a problemat.

ott meg van olyan LISP meg C megoldás ami egy másodperc alatt fut
jaja, c-ben dolgozol es ha egymillio alatt vagy, akkor azert nagyvaloszinuseggel minden collatz-sor belefe'r 32bitbe, es akkor ugy viszonylag nem kicsit lesz gyors :] plusz par tru"kk: look-up table a mar kiszamolt sorhosszakra. (egymillio 32bites egesz szam minden mai gep memoriajaban szazszor is elfe'r), (3x+1)/2-t szamolod kapasbol, bitshiftek {while ( ! (x&1) ) x>>=1;} ilyesmik, ugy szepen lehet gyorsitani a dolgon.

Valamikor kacérkodtam a scheme-mel, de aztán megszakadt a kapcsolatunk. Első ránézésre ez viszonylag egyszerűen megoldható probléma, és nincs gond a számábrázolással sem. Mivel a barátság sosem teljesedett ki köztünk, így lehet hogy tévedek.

-----
"Fontosabb egy jó szomszéd, mint egy távoli rokon." (Árvízkárosult, 2010)

A kerdes nagyon jo, de nem tudom ertelmesen megvalaszolni, mar itt gondolkodok 5 perce mit irjak. Ha nem tanultal matematikat, nehez lehet megerteni miert. Megprobalok elni egy hasonlattal: egy nagyon nehez sakkfeladvanyt kell megoldanod. mondjuk tudod a szabalyokat de kezdo sakkozo vagy. hogy oldod meg? nincs igazan modszertanod, csak probalgatsz.
A sakknagymester ugyanugy csak probalkozni tud igazabol, de sokkal rendszerezettebben teszi es hamarabb megoldja a feladvanyt. miert? mert mogotte hatalamas tapasztalat van.
Kb igy van ez a matekkal is. nagyon leegyszerusitve kreativ otletes, de aki mar nagyon sok matekot tapasztalt, estleg jobb otletei vannak, rendszerezettebben gondolkodik es jut egyik reszproblemarol a masikra.
zsolt

( phaul | 2010. 09. 10., p – 22:33 )

Eloszor azt hittem ez ez http://projecteuler.net/index.php?section=problems&id=14. De nem, a kerdes amit foltettel az nem megy ilyen egyszeruen.. Valami hatterinfo a dologhoz? Ha csak ugy random jott az otlet es nincs ezeken kivul fixpontja vagy tul nagy akkor keresheted egy darabig :)

szerk : hozzateszem hogy az Euler megoldasak hossza 525 amibol az is sejtheto ?talan? hogy C(n) joval kisebb mint n, tehat nekem hiheto hogy nincs tobb fixpontja
==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

ez a "jóval kisebb" módszer azért "zsákutca" mert ha egy bármekkora felső korlátot tudnál adni be lenne bizonyítva a collatz sejtés

igen, ha a grafikont nézzük olyan szépen látszik hogy az utolsó ahol C(n)>n ott n=kb110 (most meg nem mondom pontosan) onnan meg a C(n)-n grafikonja olyan gyönyörűen tart ~lineárisan a mínusz végtelenhez, épp ezért a jól látszikért olyan bosszantó a sejtés hogy bizonyítani meg még sem tudják

miert zsakutca? nem akartam en felso korlatot adni, csak talalgatni hogy erdemes e a gepet ejszakara fixpont keresesen hagyni.

> tart ~lineárisan a mínusz végtelenhez

A hosszrol ugy gondoltam hogy nem negativ?

==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

"C(n) joval kisebb mint n"
tehát azt mondod hogy azért nem lesz fixpont (1 és 2 után) mert C(n)<n, ezt nevezik felső korlátnak

a második felét nem értem mit gondoltál:)
egyszerűen rajzold fel grafikonon a "C(n)-n"-et millióig és látod mire gondolok, azaz te is gondoltál az C(1E6)=525-ből, de a grafikon tendenciájából már az is látszik hogy nem annyira "tüskés" hogy talán C(1E1000)-nél már ugorjon

valóban elírtam, a C(1E6)=525 helyett ugye n=millióig a maximum 525..
de hogy honnan tudd mit gondolok nem tudom és nem azt rajzoltad amit mondtam, de ezen is látszik hogy millióig max 220, talán ha millióig millió pontot rajzolnál akkor látnád az 525-öt is, kicsit hiányos az ábrád :)

bahh, de sok okos van itt, mi lenne ha a hejesírási hibák megfigyelése helyett mondjuk a probléma megoldását írnád:)

C(n)-re felső korlát lenne most n, nem egy konstans amit zh-ra belédvertek:), mert nem C divergenciájára vagyunk kíváncsiak, konkrétan "C(n)-n"-et vizsgáljuk

ki beszélt helyesírási hibáról?
azért van idézőjelben mert nem az, de azért került idézőjelestül oda mert pont annyira értelmetlen offolás mint a gramarnáciskodás

arra céloztam hogy valóban hibás felső korlátnak nem konstanst hanem függvényt nevezni, de jelen esetben azért használtam ezt a szót mert más nem jutott eszembe és gondoltam elég érthető

de ha valakinek ez már nem a biciklitároló festés kategória, megértem, de mi*előtt* leszólna érte, a megoldást írja le; amit én írtam az *igaz*, csak a szóhasználatom, "matematikai helyesírásom volt rossz", azaz valóban ha valaki a témabelit úgy akarná megoldani hogy c(n)<n (egy konkrét számtól kezdve) akkor valóban minden n-re c(n) véges, azaz a sejtés be lenne bizonyítva

hat en kerek elnezest :]

az a baj, hogy muszaj vmilyen szinten preciznek lenni, mertha ilyen szintu pongyolasagokat megengedunk (korlatos, konstans, veges, ..., ezek keverve), akkor 3 sorban be lehetne bizonyitani a sejtest.

tovabbi jo fejtorest. ha vki megoldja, azert ossza meg a fo"bb gondolatokat/lepeseket.

( mkristof | 2010. 09. 12., v – 15:05 )

Mivel általános matematikai módszereket végülis senki sem tudot javasolni, ezért az information-junkie/google-huszár módszert alkalmaztam. Egy fél délelőtt alatt átnéztem egy csomó oldalt és nagyjából a következőkre jutottam:

  • A válaszhoz talán ez az cikk jár a legközelebb. Bár az ilyen szintű matekot egyáltalán nem látom át, van egy sejtésem. Ha a linkelt oldalon a B tételben szereplő függvény valamilyen kapcsolatban áll a szám -> "collatz-sor hossza" függvénnyel és ez a kapcsolat azt jelenti, hogy nagyobb k-ra az order is nagyobb lesz (bármit is jelentsen ez) és identitás csak 1-es ordernél lehetséges akkor nem lesz több fixpont a triviálisokon kívül. :) (Ha valaki ért a felsőbb matekhoz és van egy csomó felesleges ideje ránézhet a cikkre, és kijavíthat.)
  • Amennyit megértettem az alapfogalmakból és ezek alkalmazásáról, abból úgy tűnik, hogy a szokásos fixpont-konstrukciós módszerek nem alkalmazhatóak a kérdésbeli C függvényen, mert az nem monoton.
  • Bizonyára a limitált előismereteimmel lehet a probléma, de néhol egymásnak ellentmondónak látszó állításokat lehet találni a wikipédiában. Egyfelől lehet ilyet olvasni: "Every lambda expression has a fixed point, and a fixed point combinator is a "function" which takes as input a lambda expression and produces as output a fixed point of that expression." (itt). De mindjárt ott van egy másik cikk, ahol pedig ezt olvashatjuk: "There can be no such function for Y, because some functions (for example, the successor function) do not have a fixed point." (itt). Van egy tippem, hogy mi lehet a megoldás (szintaxis és szemantika különbsége) de nagyon örülnék minden magyarázatnak.
  • A sok böngészés közben lehet igazán érdekes dolgokat is találni. Például létezik olyan fixpont-kombinátor, amelyik alkalmazható applicative-ordert használó nyelvekben is. Míg az Y csak normal order nyelvekben használható, a belőle levezethető Z már például Pythonban is működik (itt). Ha tehát pl. így implementáltuk a C függvényünket:
    
def C(num):
  if num == 1:
    return 1
  elif num%2 == 0:
    return 1+C(num/2)
  else:
    return 1+C(3*num+1)

    akkor a Z kombinátort 

    
Z = lambda f: (lambda x: f(lambda *args: x(x)(*args)))(lambda x: f(lambda *args: x(x)(*args)))

    és némi trükközést 

    
col = lambda f: lambda x: (x == 1 and 1) or (x%2==0 and 1+f(x/2)) or 1+f(3*x+1)

    felhasználva így is megkaphatjuk C értékeit: 

    
>>> Z(col)(13)
10

    Vagány, nem? :)

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

válaszhoz talán ez az cikk jár a legközelebb.
igen, a Terras-tetel kiemelkedoen fontos a Collatz-sejtes vizsgalataban.

egyebkent hozza kell tenni, hogy az altalad keresett problemanal vagyis ugy altalaban a C(n) sorozat vizsgalatanal egy fokkal kezelhetobb/kozelebbi kerdeskor a "stopping time" kerdese. Ez az S(n) (vagy \sigma(n)) fuggveny azt mondja meg, hogyha f(.) az eredeti collatz lekepezes, akkor mi az a legkisebb p=S(n) kitevo", melyre f^p(n)<n lesz. A collatz-sejtes (minden n-re C(n) ve'ges) az ekvivalens azzal a megfogalmazassal hogy minden n-re S(n) is veges.

Viszont az S(n) fuggvenynek sokkal szebb/jobban bizonyithato/kezelheto" tulajdonsagai vannak. Pl ha n pa'ros, akkor S(n)=1. Ha n=4k+1 alaku, akkor S(n)=3. Vagy pl: 


S(16k+3)=5
S(32k+11)=8
S(32k+23)=8
...

altalabanpedig, ha S(x)=w, es p olyan hogy p+t(p)=w, ahol t=t(p) a legkisebb kitevo" melyre igaz, hogy 3^t < 2^p, akkor minden k egesz szamra S(2^p*k+x)=w, szinten. Ez nagyon egyszeruen bizonyithato. A terras-tetel meg azt bizonyitja, hogy p ill. t novelesevel azon x-ek szama 1 es 2^p-1 kozott, melyre S(x) > w=p+t(p) aranyaiban (2^p-hez kepest) 0-hoz tart.

viszont ez az egesz jatek itt fent, akar az S(.) fuggvenyt, akar a C(.)-t nezed, nem sokat mond a fixpontokrol. nehez metrikat definialni, fixpontos teteleket meg metrikus terekben lehet szepen keresni.

bocs, ha nem sok ujat mondtam, de ha vkinek nem volt kedve elolvasni a fenti cikket es/vagy a kapcs referenciakat de erdekli a problemakor, akkor talan nem volt haszontalan.

Köszi szépen!

Ezek tök hasznosak, mert nekem a linkelt cikkek - főleg az első - azért egy kicsit sűrűek. Minden - kicsit is különböző - magyarázat hozzásegít, hogy egy kicsit jobban megértsem a problémakört. Még egy kicsit rágnom kell azt amit írtál. :)

"viszont ez az egesz jatek itt fent, akar az S(.) fuggvenyt, akar a C(.)-t nezed, nem sokat mond a fixpontokrol. nehez metrikat definialni, fixpontos teteleket meg metrikus terekben lehet szepen keresni." <-- itt lesz a kutya elásva, nem?

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

itt lesz a kutya elásva, nem?
igen, metrikus megkozelitesrol sehol sem hallottam a problema kapcsan. fixpont letezesehez nemhogy metrika kell, hanem teljes metrikus te'r is, amit egesz szamok koreben (mmint a teljesse'get) igen nehez elkepzelni. ez egy szivas. de lehet hogy nem is jo ira'ny ez...

szoval most ugy jon le igy osszessegeben hogy inkabb az S(.)-t erdemes nezegetni, annak viselkedeseit. persze extrem dolgok ma'r itt is hamar elojonnek, pl n=27-nel nemcsak az van hogy S(n)=96 (ami szinten eleg sok/durva, meg a C(n)=111-hez kepest is), hanem hogy a hozza tartozo ertekek (p=59, t=37, igy p+t=w=96) is ugye akkorak, hogy a kovetkezo" sza'm, ami "ugyanugy" viselkedik ahogy a 27, az a 2^59+27=576460752303423515. ami meg mar nem kicsit nagy -- me'g a mezei numerikus keresesek is epphogycsak elertek ebbe a nagysagrendbe (epphogycsak, szoval mar kenyelmesen, de most tartanak olyan parsza'z szorozva 2^58-nal, lasd a tos-fele honlapot).

illetve me'g az S(.) mellett szol az is, hogyha abrazolod a C(.)-t mondjuk n<=1000-ig, meg S(.)-t, akkor ezutobbi joval "letisztultabb" grafikon lesz. erdemes megnezni, latvanyos. es a fentebbi periodicitasok (S(32k+11)=8, stb) is elegge szembeotlo"ek.