Collatzin pähkinän todistus

[JMe1]

Ehdotan että laitat ongelman tauolle kuukaudeksi, sen jälkeen voi löytyä uusia näkökulmia.

[Eusa]

Ehdotan että laitat ongelman tauolle kuukaudeksi, sen jälkeen voi löytyä uusia näkökulmia.

Lukuteoreettisessa näkökulmassa en näe mitään vaihdettavaa. Tekninen ratkaisu +1 ja -1 -vuorottelujen kautta palaamiseen samaan tekijä-slotiin voi olla olemassa tai sitten ei; kahdella, kolmella ja viidellä vakiojakajana positiivisen ja negatiivisen kongruenssitransition rekursiot saattavat erikoistapauksina peittää toisensa ilman peräkkäisheilahduksia, jotka johtavat luuppeihin pienillä luvuilla, joissa edelliseen slotiin yltää siirtyä = siirtymä+-ykkönen on suhteellisesti riittävän suuri.

No, jakajana 2 eli Collatz-rekursiohan toimii puhtaasti yhden suunnan transitiolla - samoin se Collatz-Eusa-kehitelmä, jossa otettiin mukaan kolmellajakoa kaveriksi. Sen sijaan suuremmilla jakajilla sloteja on seulottava edestakaisella ryömimisellä. Voi löytyä jaollisuuksiin perustuva ryömintäohje - itse asiassa jo se, että huolehtisin algoritmiin, että käsillä olevista transitioista saa toteuttaa aina vain kaksi tai enemmän peräkkäin samaan suuntaan, taitaisi taklata puutteen... Seuraavan kerran kun ehdin työstää, kokeilenpa laittaa tuollaisen välittömän fluktuoinnin estävän lippumuuttujan mukaan.

Suuremmissa Eusa-rekursioissa saattaa olla vääjäämätöntä, että pienin luuppi suurenee asteittain. Tuo tulee kyllä selvitettyä. Ei minulla ole tähän harrastukseen ollut aikaa kuin tunti pari silloin tällöin. On ihan antoisa hobby kylläkin ja tyydyttää uteliaisuuden, kun lukujen mekanismeja löytyy.

[Eusa]

Tutkailin paisuttajien käyttöjärjestystä. Induktiorekursion pitämiselle ainutkertaisesti täyttävänä löytyi kaava, joka avaa tekijä-slotin luonnetta käänteisenä Erastotheneen seulana. Kun vakiojakajaa kasvatetaan, ketjujen loppu saa muotoa "...4, 3, 2, 1". Raja-arvona vakiojakajaa viemällä mielivaltaisen suureksi tekijä-slotit tuottavat ketjuksi lähtöluvusta luonnolliset luvut järjestyksessä alaspäin - tämä on odotettu tulos.

[Eusa]

Alkuperäiseen ongelmaan tekijä-slotista sain sievennettyä osuuden tilanteesta, jossa ollaan luvussa x=A*2^n-1 ja päädytään n toistolla (3x+1)/2 eli lisäyksillä (x+1)/2 lopulta parittomien sijaan parilliseen:

Tuosta jatkaen puolituksilla pysytään tekijä-slotissa, josta ei ole parittomia pitkin pääsyä saman ainutkertaisen A*3^m -luvun viereen ja ketjuluku ei voi koskaan päästä samoin pienenemään puolituksilla eli ketju ei voi ajautua ei-triviaaliin luuppiin. Mikäli tuosta parillisesta on puolitettavissa useamman kerran, voi tietysti ketjun muista haaroista tulla tähän slotiin, mutta ei enää uudestaan. Niihin 2^n -lukuihin päädytään A*2^0-1 -muotoisista edeltäjistä ja sitten kutsuukin ykkönen.

[Eusa]

Alkuperäiseen ongelmaan tekijä-slotista sain sievennettyä osuuden tilanteesta, jossa ollaan luvussa x=A*2^n-1 ja päädytään n toistolla (3x+1)/2 eli lisäyksillä (x+1)/2 lopulta parittomien sijaan parilliseen:
Screenshot_20240101_003005_Chrome.jpg

Tuosta jatkaen puolituksilla pysytään tekijä-slotissa, josta ei ole parittomia pitkin pääsyä saman ainutkertaisen A*3^m -luvun viereen ja ketjuluku ei voi koskaan päästä samoin pienenemään puolituksilla eli ketju ei voi ajautua ei-triviaaliin luuppiin. Mikäli tuosta parillisesta on puolitettavissa useamman kerran, voi tietysti ketjun muista haaroista tulla tähän slotiin, mutta ei enää uudestaan. Niihin 2^m -lukuihin päädytään A*2^1-1 -muotoisista edeltäjistä ja sitten kutsuukin ykkönen.

Hups - korjattu ylle; ainahan paritonta yhtä ylemmässä on vähintään yksi kakkonen tekijänä. Mutta voi olla ainoastaan yksi silloin, kun päädytään seuraavaksi 2^m -muotoon, esim. x=21 eli 22-1, josta (3*21+1)/2 tuottaa 32.

[Eusa]

Se käänteinen Erastotheneen seula on tuossa kahdella useamman kerran peräkkäin jakamisessa. 3^m sitoo peräkkäiset parittomat (3x+1)/2-termit kunnes parillinen. Siinä A*3^m ja se parillinen A*3^m-1 = B*2^k muodostavat toisilleen suhteelliset alkuluvut A ja B. Kun parillisuus on puoliteltu pois, jää vain B, josta saadaan uusi A=(B+1)*2^n - n kertoo sen kuinka monta paritonta tulee seuraavaksi ketjuun ja kuinka ne sitoutuvat uuteen termiin A*3^(n+1), jne...

Kolmosen potenssit antavat Erastotheneen seulan selkärangan, jonka suhteen kaikki esiin nousevat A:t ja B:t ovat ainutkertaisen tekijä-slotin rakennetta yhdessä 2^m -muotojen kanssa tietyssä ketju"korkeudessa".

Collatzin ketju ei voi koskaan toistaa itseään ja vääjäämättä osuu 2^i -lukuun, josta karahdetaan ykköseen.

Päädyin tähän todistukseen Erastotheneen seulamaisuudesta, koska näin, ettei osoittaminen lähtöluvusta aina päädyttävän sen alle ole ollenkaan konsistentisti mahdollinen todistelutapa.

[Eusa]

(3x-1)/2 -ongelmassa 3^m -selkäranka jää juuri pienemmälle puolelle ja käänteinen Erastotheneen seula ei kaikkineen toteudu samoin kuin (3x+1)/2 -ongelmassa, koska B ei pysy varmuudella seulan sisäpuolella, joka vaaditaan varmuudella ykköseen redusoitumiseen. Sopivan pienillä luvuilla ketjuun tulee jäseniä samasta tekijä-slotista. Tunnetut kaksi looppia ovat pidempi/suurempi lähtien luvusta 17 ja jatkuu 25, 37, 55, 82, 41, 61, 91, 136, 68, 34, 17,... ja toinen pienempi 5, 7, 10, 5,...

Muuten kyllä tuo Collatzin sisarketju toimii vastaavasti redusoituen pohjalle; joko noihin kahteen kehään tai ykköseen. Pidemmässä kehässä slotista suistuminen tapahtuu kohdassa 82 = 3⁴+1, joka puolittuu heti alkulukuun 41 = 2*5*2²+1; lisäyksin päädytään 3*5*2² + 5*2*3 + 5*1*3² + 1 = 136:een = 5*3³+1. Verrataan (3x+1)/2‐ketjun vastaavaan kohtaan 80 = 3⁴-1, josta 40 -> 20 -> 10 -> 5. Siinä 3^m -muodon alapuolella pysytään seulassa ja saadaan 3⁴:ää vastaava suhteellinen alkuluku 5. Sisarketjussa seulan ulkopuolella vastaavaan selkärankaan liittyen tuli 41 -> 61. Tutkitaan selkärankaa 3⁵: 33 -> 49 -> 73 -> 109 -> 163 -> 244 = 3⁵-1 (5 peräkkäistä paritonta). B = 244/4 = 61, eli tullaan samaan slotiin sekä ylä- että alasuunnasta - sekvenssissä molempien A3^m-termien suhteellinen on alkuluku A=1.

Voiko jotenkin tunnistaa, että B=41 on liian suuri tuohon kohtaan? Kyllä - selkärankasuhteen 3^m/B tulee olla suurempi kuin 2, jotta ei lipsahdeta naapuri-sloteihin. Alkuperäisellä Collatz-ketjulla tuo suhde on pakotetusti >2, koska 3^m - 1.

Onko sisarongelmassa edellä mainittujen kahden lisäksi muita syklejä? Asiaa voidaan tarkastella suhteella sqrt(3^m +1) / 2^(m-1), jossa osoittaja päädyttävän luvun sisältämän suhteellisen alkulukutekijän suurin mahdollinen arvo (mukana kulkevasta A-tekijästä riippumatta) kertauttamalla nimittäjällä peräkkäisten parittomien sekvenssissä ja huomioiden vielä eka parittoman poisjako. Suhde ollessa >1 kertoo onko ko korkeudella riittävästi voimaa toteuttaa tarjottu slotin vaihto.

5-loopille suhde on sqrt(9)/2 > 1, 9-loopille sqrt(27)/4 > 1 [puolittuu kahdesti -> -> 7] ja 17-loopin kohdalla laskelma antaa 9/8 > 1. 33-ketjun kohdalla saataisiin sqrt(244)/16, joka jää jo niukasti alle yhden ja pidemmillä/suuremmilla parittomien sekvensseillä suhde jää yhä selvemmin alle yhden eli ei kykene siirtymään toiseen slotiin eikä siis muita looppeja voi esiintyä.

[Eusa]

Kun ei täällä synny keskustelua, laitoin juttuni MathStackExchangeen: https://math.stackexchange.com/question ... 14#4837814

Jospa sieltä saisi jotain palautetta.

[Eusa]

Suomenkielinen teksti:

Olen huomannut, että jonkinlaisen käänteisen Eratothenes-seulan toteuttamiseksi [math](ax+1)/b -sekvenssissä sekä luku [math]a että luku [math]b tulee olla todellisia alkulukuja, ja jotta joukko [math]N täyttyisi tiheästi, lisäystermi tulee olla [math](x+1)/b -> [math](a-1)x/b=x -> [math]a=b+1. Vain [math]a=3, b=2 ovat kelvollisia.

Jos rakennetaan toinen sekvenssi, joka pinoutuu samaan tapaan, on käytettävä sekä [math](ax+1)/b- että [math](ax-1)/b -termejä sekä useita paisutuskertoimia [math]a:lle, vakiota [math]b:lle ja ensin tarkistettava, onko tulos kokonaisluku ja suorittaa sitten, kun se on...

Collatz-sekvenssin selkäranka perustuu kertoimen [math]3 potensseihin. Voit kirjoittaa [math](3x+1)/2 muotoon [math](2x/2+(x+1)/2. Olkoon lisäystermi [math](x+1)/2=A2^n. Riippuen [math]n:stä saamme [math]k-sekvenssin peräkkäisiä parittomia lukuja + viimeinen parillinen, [math]k=1+n (ensimmäinen lähtöpariton ja summa muista [math]k-jakson jäsenistä), missä kahden potenssit häviävät ja kolmen potenssit nousevat. Ottaen huomioon, että sekvenssiin lähdettäessä [math](x=-1+2\times A2^n) :

[math]-1+3\times A2^{n}+\sum_{i=1}^{n}(2^{n-i}\times3^{i})=A3^{n+1}-1

Siksi koko kasvava k-sekvenssi peräkkäisillä parittomilla luvuilla määritellään termillä [math]3^k säilyttämällä jokin suhteellinen alkuluku [math]A. Kun vähennetään yhdellä, saadaan uusi [math]A-liitetty suhteellinen alkuluku [math]B parillisessa luvussa [math]A3^{n+1}-1=B2^{m} Kun puolitetaan peräkkäin, on vain [math]B. Sitten uusi [math]x=B saamme uuden [math]B-liitetyn suhteellisen alkuluvun [math]A: [math](x+1)/2=A2^n - jne...

Minusta näyttää siltä, että Collatz-sekvenssit ilmenevät käänteisenä Eratostheneen seulana, joka nojaa luvun kolmen potensseihin vahvana selkärankana.

[Eusa]

Suomenkielinen teksti:

Olen huomannut, että jonkinlaisen käänteisen Eratothenes-seulan toteuttamiseksi [math](ax+1)/b -sekvenssissä sekä luku [math]a että luku [math]b tulee olla todellisia alkulukuja, ja jotta joukko [math]N täyttyisi tiheästi, lisäystermi tulee olla [math](x+1)/b -> [math](a-1)x/b=x -> [math]a=b+1. Vain [math]a=3, b=2 ovat kelvollisia.

Jos rakennetaan toinen sekvenssi, joka pinoutuu samaan tapaan, on käytettävä sekä [math](ax+1)/b- että [math](ax-1)/b -termejä sekä useita paisutuskertoimia [math]a:lle, vakiota [math]b:lle ja ensin tarkistettava, onko tulos kokonaisluku ja suorittaa sitten, kun se on...

Collatz-sekvenssin selkäranka perustuu kertoimen [math]3 potensseihin. Voit kirjoittaa [math](3x+1)/2 muotoon [math](2x/2+(x+1)/2. Olkoon lisäystermi [math](x+1)/2=A2^n. Riippuen [math]n:stä saamme [math]k-sekvenssin peräkkäisiä parittomia lukuja + viimeinen parillinen, [math]k=1+n (ensimmäinen lähtöpariton ja summa muista [math]k-jakson jäsenistä), missä kahden potenssit häviävät ja kolmen potenssit nousevat. Ottaen huomioon, että sekvenssiin lähdettäessä [math](x=-1+2\times A2^n) :

[math]-1+3\times A2^{n}+\sum_{i=1}^{n}(2^{n-i}\times3^{i})=A3^{n+1}-1

Siksi koko kasvava k-sekvenssi peräkkäisillä parittomilla luvuilla määritellään termillä [math]3^k säilyttämällä jokin suhteellinen alkuluku [math]A. Kun vähennetään yhdellä, saadaan uusi [math]A-liitetty suhteellinen alkuluku [math]B parillisessa luvussa [math]A3^{n+1}-1=B2^{m} Kun puolitetaan peräkkäin, on vain [math]B. Sitten uusi [math]x=B saamme uuden [math]B-liitetyn suhteellisen alkuluvun [math]A: [math](x+1)/2=A2^n - jne...

Minusta näyttää siltä, että Collatz-sekvenssit ilmenevät käänteisenä Eratostheneen seulana, joka nojaa luvun kolme potensseihin vahvana selkärankana.

Tämä tiivistetty määrittely

[math]x\;mod\;2 = 0\;=>\;x=x/2
[math]x\;mod\;2 = 1\;=>\;x=(3x+1)/2

tiivistyy parittoman ja parillisen vuorotteluksi:

[math]x\;mod\;2 = 0\;=>\;x=B=x/2^m,\;m:\;suurin pitäen joukossa[math]N, saadaan pariton
[math]x\;mod\;2 = 1\;=>\;x=A\times3^k-1,\;k:\;(x+1)/2^k:ssa suurin pitäen joukossa[math]N, saadaan parillinen

Koska [math]B määrittää yksiselitteisesti [math]B:lle ja [math]2:lle suhteellisen alkuluvun [math]A ja [math]A määrittää yksiselitteisesti [math]A:lle ja [math]2:lle ja [math]3:lle suhteellisen alkuluvun [math]B ja parittomien [math](x+1)/2-lisäystahti kuvautuu [math]N:ksi, eivät [math]A tai [math]B voi toistua muuten kuin siten, että [math]A=B=1 eli [math]1 -> [math]1\times3^1-1=2 -> [math]2/2^1=1. Koska [math]B on aina alle [math]3^k/2, pysyvät generoituvat tekijät suhteellisten alkulukujen ohajuksessa "sloteissaan" miltä korkeudelta eli kuinka suuresta luvusta lähdetäänkään ja [math]B:n tekijät eli nousevien ja laskevien ketjujaksojen käännesolmujen tekijät täyttävät lopulta koko alkulukuavaruuden ikään kuin Erastotheneen seula, mutta käänteisesti yhä suuremmista luvuista aloittaen ja kootut luvutkin samalla läpi käyden (jos aloitukset jokaisesta [math]N:n jäsenestä).

Collatzin sisarketjun [math](3x-1)/2 kompastus on se. että nousujakson viimeinen vääjäämätön ylin luku [math](3^k+1)/2 on suurempi kuin [math]3^k/2, koska silloin kun A=1, ja tuo [math](3^k+1)/2 osuu heti parittomaksi ja alkuluvuksi, se menee slotin hallinnan rajan ulkopuolelle ja voi olla jatkumossa toisen slotin kanssa - niin tapahtuu, kun aloitetaan luvusta [math]17 tai [math]5.

Tässä esimerkki kuinka alkulukutekijöitä kivasti generoituu (siniset [math]B:n alkulukutekijöitä, huvikseen myös [math]A:n tekijöitä avattu punaisella, suluissa riveittäin nousevien lukujen [math](3x+1)/2-operaatioiden määrä k ja laskevien lukujen [math]x/2-operaatioiden määrä m):

[Eusa]

Ehkä voisi olla kuvaavaa käytää binäärien sijaan trinäärejä?

Videon 13 -> 27 -> 40 -ketju näyttäisi tältä:
111 -> 1000 -> 1111.

Toki tiivistetyn käännesolmunhakualgoritmini avulla tiedämme, että 13:sta parilliseen päästään katsomalla 13+1 muodossa A2^k ja menemällä suoraan A3^k-1:een eli 14=7×2^1 ja todellinen (3x+1)/2-nousua kääntävä solmu on 7×3^1-1=20, mikä on trinäärisesti:

111 -> 202. Sitä sitten puolitetaan -> 101 -> 12. Seuraava parillinen solmu on desimaalisesti 3×3^1-1=8 ja tunnetusti puolitellaan ykköseen; trinäärisesti: 12 -> 22 -> 11 -> 2 -> 1.

Havannollista trinäärein olisi ainakin silloin, kun luvusta 2^k-1 siirrytään parilliseen käännesolmuun 3^k-1, esim. 31 -> 242 trinäärisesti: 1011 -> 22222.

[JMe1]

Ehkä voisi olla kuvaavaa käytää binäärien sijaan trinäärejä?

Videon 13 -> 27 -> 40 -ketju näyttäisi tältä:
111 -> 1000 -> 1111.

Toki tiivistetyn käännesolmunhakualgoritmini avulla tiedämme, että 13:sta parilliseen päästään katsomalla 13+1 muodossa A2^k ja menemällä suoraan A3^k-1:een eli 14=7×2^1 ja todellinen (3x+1)/2-nousua kääntävä solmu on 7×3^1-1=20, mikä on trinäärisesti:

111 -> 202. Sitä sitten puolitetaan -> 101 -> 12. Seuraava parillinen solmu on desimaalisesti 3×3^1-1=8 ja tunnetusti puolitellaan ykköseen; trinäärisesti: 12 -> 22 -> 11 -> 2 -> 1.

Havannollista trinäärein olisi ainakin silloin, kun luvusta 2^k-1 siirrytään parilliseen käännesolmuun 3^k-1, esim. 31 -> 242 trinäärisesti: 1011 -> 22222.

Siinäpä keksijä !

MUTTA : hän mokasi yhdessä kohdassa - poisti binääriluvusta kaikki loppunollat kerralla. Jos sensijaan poista vain yhden, huomaa että viimeisen bitin poisto lähenee jonoa 10101010101.. kun luku lähenee satunnaislukua. Ja 3x+1 sattuu olemaan funktio joka pakottaa minkä tahansa aloitusluvun satunnaiseksi.

Kun luku on saavuttanut riittävän satunnaisuuden tason, se alkaa pakostakin lyhentyä, sillä 3x+1/2 ei aina kasvata binääriluvun numeroiden määrää kun taas YKSI poistettu nolla vähentää sitä aina yhdellä.

Jäljelle jää todistus että 3x+1 kykenee murskaamaan minkä tahansa aloitusluvun satunnaiseksi. Tässä on oleellista että puuhun ei saa tulla luuppeja. Jos tulee, 3x+1 satunnaistajana menee jumiin. Eli tämän kun todistaa niin voi käydä kuittaamassa tuon videolla mainitun jenisumman.

Korjaan tässä yhteydessä aiemman päättelyvirheeni. Sanoin että jos Collazin puuta aletaan rakentamaan keskeltä, sinne ei voi tulla numeroa kahteen kertaan sillä polku roottin on yksikäsitteinen. Oikea päättely olisi ollut että siinä vaiheessa kun ensimmäisen kerran huomataan "tämä numero on jo puussa" se ei voi olla keskellä puuta. Se voi kuitenkin olla puun reunalla ja siten on syntynyt numerosilmukka.

Ja siis heti kun numerosilmukka on syntynyt, 3x+1 funktiolle on osoitettu lähtöluku josta se ei osaa murskata satunnaista. Mutta tällaistahan ei ole löytynyt.

[Eusa]

Ja 3x+1 sattuu olemaan funktio joka pakottaa minkä tahansa aloitusluvun satunnaiseksi.

Eihän tuollaiseen väitteeseen ole mitään perusteluja.

Jos lukisit matematiikkaani, ymmärtäisit kuinka täsmällisesti Collatzin ketju toimii nousten ensin kolmen potenssilla jaollisesta yhden alle ja sitten laskee jaettuna kahden potenssilla. Sitä jauhaa päätyen alas ykköseen.

Termini A×3^k toteuttavat luvun x korkeustasossa tekijä-slotia, joka varmistaa, ettei looppia voi syntyä samaan korkeustasoon, vaan x ajautuu termissä B×2^m vääjäämättä alemmas keskimäärin luokkaa (2/3)^2 = 4/9 -pienemisvauhdilla per k-kääntymisaalto. Tuo perustuu siihen, että laajassa otoksessa erilaisia Collatz-ketjuja k ja m ovat esiintymiseltään tasa-arvoisia ja huomioidaan peräkkäisten aaltojen vuorovaikutus. Tulos on linjassa tunnnetun sen huomion kanssa, että JMe1:n ajattelun tapaisessa probabilistisessa hengessä peräkkäisten parittomien suhde on keskimäärin 3/4 (Jeff Lagarias, AT&T Bell Laboratories; https://www.cecm.sfu.ca/organics/papers ... node3.html) - siis tuo oli jo tutkittu; pyörää ei tarvitse keksiä siltä osin uudelleen.

[JMe1]

Eihän tuollaiseen väitteeseen ole mitään perusteluja.
--
Täällä:
https://en.wikipedia.org/wiki/Linear_co ... _generator
The generator is defined by the recurrence relation:

X n + 1 = ( a X n + c ) mod m
...

Riittääkö ?

[JMe1]

Ja 3x+1 sattuu olemaan funktio joka pakottaa minkä tahansa aloitusluvun satunnaiseksi.

Eihän tuollaiseen väitteeseen ole mitään perusteluja.

Jos lukisit matematiikkaani, ymmärtäisit kuinka täsmällisesti Collatzin ketju toimii nousten ensin kolmen potenssilla jaollisesta yhden alle ja sitten laskee jaettuna kahden potenssilla. Sitä jauhaa päätyen alas ykköseen.

Termini A×3^k toteuttavat luvun x korkeustasossa tekijä-slotia, joka varmistaa, ettei looppia voi syntyä samaan korkeustasoon, vaan x ajautuu termissä B×2^m vääjäämättä alemmas keskimäärin luokkaa (2/3)^2 = 4/9 -pienemisvauhdilla per k-kääntymisaalto. Tuo perustuu siihen, että laajassa otoksessa erilaisia Collatz-ketjuja k ja m ovat esiintymiseltään tasa-arvoisia ja huomioidaan peräkkäisten aaltojen vuorovaikutus. Tulos on linjassa tunnnetun sen huomion kanssa, että JMe1:n ajattelun tapaisessa probabilistisessa hengessä peräkkäisten parittomien suhde on keskimäärin 3/4 (Jeff Lagarias, AT&T Bell Laboratories; https://www.cecm.sfu.ca/organics/papers ... node3.html) - siis tuo oli jo tutkittu; pyörää ei tarvitse keksiä siltä osin uudelleen.

No olen minä ne lukenut läpi mutta en ole tottunut ajattelemaan matematiikan kaavojen kautta.