Collatzin pähkinän todistus

[Eusa]

Ei aukea selityksesi minulle. Toivottavasti palstalta löytyy matemaatikko joka osaa tehdä katselmoinnin todistuksellesi.

Minusta tuo logiikka on lopulta aika triviaali. Sokeutta lienee aiheuttanut, kuten niin usein, hoksaavan näkökulman valinta.

Näkökulma löytyi vertaamalla (3x+1)/2 ‐ketjua muihin - mikä siinä on erilaista ja Collatzin väistelyt mahdollistavaa verrattuna muihin? Löytö on se, että pohjimmiltaan kyse on vain parittomien osajoukosta. Kun se saadaan bijektoitua koko joukkoon N rekursiokaavalla jotenkin perustellusti, on äkättävissä, että silloin N:n täyttävä alkulukujaollisuus kiinnittää osoitteiston. Kun Collatz-kävely juoksuttaa modulaarisuutta noilla (x+1)/2 ‐lisäyksillä täyttäen N:n, homma pelittää.

Ketjun alussa vertailin muunlaisiin ketjuihin ja tein pienen lapsuksen - tietysti (7x+1)/2 tuottaa lisäyksiä (5x+1)/2 eli suhteessa parittomiin kasvattaen lineaarisen aritmeettisesti 5:n välein (eikä geometrisesti kuten erheellisesti kirjoitin). (5x+1)/2 rekursiona puolestaan tuottaa jäseniä (3x+1)/2 -lisäyksin ja kasvattaen niitä pariton parittomalta 3:n välein. Vain Collatzin (3x+1)/2 (tai (3x-1)/2) -rekursio antaa lisäykset kunkin parittoman jäsenen lisäykseksi seuraavaksi ketjun luvuksi (x+1)/2 eli kasvattaen kutakin paritonta kohden lisäystä yhdellä.

Kun osoitteisto on tiheästi koko N, sieltä nousee identifikaatio yksiselitteisen ainutkertaisena alkulukujen tekijöin, mutta jos on välejä, niin ontuu - edellä mainituissa esimerkeissä tekijöiden 5 ja 3 osilta.

[Eusa]

Ymmärrän, että tuo modulaatio-osoitteisto edellyttää lisäselostusta, jotta saa kiinni mitä se tarkoittaa.

Perustin osoitteiston bijektiona lisäyksistä kutakin paritonta x:ää kohti (3, 5, 7, 9, 11,...) -> (2, 3, 4, 5, 6,...). Tällöin osoitteisto muodostaa luonnollisten lukujen joukon poissuljettuna < 2. Collatzin ketjujen sisältämät kaikki parittomat on noin kytketty niille perustettuun lukujen tekijöitä identifioivaan avaruuteen N. Koska joka lisäyksellä modulo muuttuu yhden askeleen, tarkoittaa se hyppäämistä sellaiseen tekijä-slotiin, joka ei voi myöhemmn ketjussa toistua. Tekijä-slotilla tarkoitan moduloyhdistelmää kaikille tekijöille joukossa N - eli silloinhan voi olla kysymyksessä vain yksi tietty alkulukutekijäyhdistelmä avaruudessa N.

Rekursiolisäyksellä x:n kaikille tekijöille pätee x mod k = x0 mod k +1, missä x0 on edellnen ketjun luku x. Itse asiassa modulo lisääntyy yhdellä kaikille mahdollisille tekijöille kaikkien mahdollisten x:ien suhteen, joten saapumalla ketjussa erääseen parittomaan lukuun x sulkee samalla pois mahdollisuuden päätyä uudestaan samaan tekijä-slotiin ja samaan parittomaan lukuun.

Kun sitten tutkimme tilannetta, jossa x = (3x+1)/2 = x + (x+1)/2 -vaiheen jälkeen ilmenee parillinen luku, sehän jaetaan edelleen kahdella. Eli silloin lisäys on -x/2. Tuossa ei parittomien tekijä-slotiin tule transitiota, joten voimme todeta, että kun kaikki puolitukset on tehty ja päästy seuraavaan parittomaan, on sekin yksilöity omaan tekijä-slotiinsa, johon tultiin, kun parittomien jälkeen ilmeni parillinen. Näin ollen katson konjektuurin todistetuksi siten, että kaikki parittomat luonnolliset luvut tulevat vastaan kukin ainutkertaiseen tekijä-slotiin kytkettynä ja vääjäämättä tullaan lopulta sen tekijäslotin kohdalle, jossa x=2^n ja slotia vastaa pariton luku 1.

mot.qed

[Eusa]

Tässä Python-koodia Collatz-Eusa -rekursiosta, jossa ajetaan:
- (3x+1)/2, kun x yleisesti pariton
- (x+1)/3, kun x edellisen jälkeen parillinen
- x/3, kun x vielä edellisen jälkeen kolmella jaollinen.

Koodi: Valitse kaikki

x = 3**15+5^11+7^7 # syötetään pariton lähtöluku
m = 0
count = 0
while count < 200:
  if m !=2 and x % 2 != 0:
    print(x)
  if x % 2 == 0:
    x = ((x+1) // 3)
    m=2
  if m == 2 and x % 3 == 0:
    x = (x // 3)
  if m == 0:
    x = (3 * x + 1) // 2
  if m == 2 and x % 3 != 0:
    print(x)
    x = (3 * x + 1) // 2
    m=0
  count += 1

[Eusa]

Edellinen ketjulogiikka kehittyi todistuksen löydetyn tekijä-slot -työkalun myötä.

Tässä alkuperäisen Collatz-ketjutuksen mukaista Python-koodia, jolla tulostetan vain kunkin tekijä-slotin ainutkertainen pariton ketjun jäsen.

Koodi: Valitse kaikki

x = 3**15+5^11 # syötetään pariton lähtöluku
m = 0
count = 0
while count < 200:
  if m !=2 and x % 2 != 0:
    print(x)
  if x % 2 == 0:
    x = (x // 2)
    m=2
  if m == 2 and x % 2 == 0:
    x = (x // 2)
  if m == 0:
    x = (3 * x + 1) // 2
  if m == 2 and x % 2 != 0:
    print(x)
    x = (3 * x + 1) // 2
    m=0
  count += 1

[Eusa]

Lukuteoreettinen todistuksen käsite "tekijä-slot" vaatii milteipä uutta matematiikkaa.

Keskinäinen jaollisuus ja jakojäämäsiirtymä eli kongruenssi on tietysti aivan juurikeino. Mutta koko luonnollisten lukujen joukon perspektiivivaihto jakojäännössiirtymällä generoiden nousi ainakin itselleni ihan todistuksen logiikasta.

Kyse on siitä kuinka jokin luku voidaan muodostaa ainutkertaisesti seuloen eikä niinkään alkulukutekijöitä poimien. Tietyt luvut ovat mahdollisia tuottaa tietystä tekijä-slotista eri "korkeuksilla". Yritän kuvailla haparoivalla esimerkillä mistä on kysymys.

Listataan peräkkäisiä lukupareja erotuksella kaksi: (1,3) (2,4) (3,5) (4,6) (5,7) (6,8) (7,9) (8,10) (9,11) (10,12) (11,13) (12,14) (13,15) (14,16) (15,17) (16,18) (17,19) (18,20) ...
Muodostetaan edellisistä lista, jossa on edellisten alkulukutekijät: (3) (2) (3,5) (2,3) (5,7) (2,3) (7,9) (2,5) (3,11) (2,3,5) (11,13) (2,3,7) (3,5,13) (2,7) (3,5,17) (2,3) (17,19) (2,3,5) ...

Jälkimmäinen lista muodostaa erään lajin tekijä-slotia, jossa voidaan esittää ensimmäisen listan lukuparien tuloja; 3, 8, 15, 24, 35, 48, 63, 80,..., jotka muodostavat rekursion x+a, jossa lisäys a lisääntyy joka askeleella kahdella.

Esimerkin tekijä-slotissa ei rakenne ole sellainen kuin Collatz-ketjun todistuksessani. Todistuksessa (x+1) siirtää ketjua parittomuuden tekijä-slotista seuraavaan. Generoimani Collatz-Eusa-ketju osoittaa kuinka tietoa voidaan hyödyntää luomalla variaatioita algoritmista. Kunhan saan rauhallisemman jakson, koitan esittää nimenomaisesta todistuksen tekijä-slotista täsmällisempää. Siinähän tietyissä sloteissa osutaan parittomaan "matalammalta korkeudelta" parillisuuden kautta. Koska luku kaksi ei sisälly parittomien tekijä-slotiin Yksilöivänä tekijänä, toimii se slotissa redusoijana viemään sen slotin parittomaan ketjun jäseneen. Kolmonen ei ole yksilöivä tekijä Collatz-Eusa-ketjun vaiheessa, jossa voi jakaa peräkkäin kolmella. Tutkimus jatkuu voisiko algoritmista kehittää muitakin variaatioita. Ainakin Collatz-Eusa-ketjun variaationa voi käyttää jakojäännöstä vähentävää transitiota, kuten perus-Collatzissakin, eli (3x-1)/2.../2...(x-1)/3.../3... Kahdella jaon loputtua tekijä-slotin vaihtaminen transitiosuuntaan, x+1 tai x-1 riippuen algoritmin luotaisesta tarnsitiosuunnasta, tarjoaa mahdollisuuden kolmella jakamalla redusoida ainutkertaiseen parittomuuteensa.

[Eusa]

Näyttää, että tukeutuen todistukseni löytöön kongruenssin hallitusta siirrosta, voin pienellä mielikuvituksen käytöllä generoida uusia Collatzin ketjun tavoin käyttäytyviä rekursioita.

Tässä kolmella jakamiseen ja kahdella kertomiseen perustuva viritys Python-koodina:

Koodi: Valitse kaikki

x = 44628**15 # seed number
count = 0
while count < 2000:
  print(x)
  if x % 3 == 0:
    x = (x // 3)
  if x % 3 != 0 and count % 2 == 0:
    x = 2 * x + 1
  if x % 3 != 0 and count % 2 == 1:
    x = 2 * x - 1
  if x<2:
    print(x)
    count = 2000
  count += 1

[Eusa]

On esitetty, ettei Collatzin tyypin ketjua (kx+l)/m saada käyttäytymään hyvin kuin suhteuttajilla k=3, l=1 ja m=2, koska yleisesti johtaa sitten silmukkaluuppeihin.

Rakensin kuitenkin todistusperusteitten perusteella hyvin käyttäytyvän ketjun vakioilla k=4, l=+-1 ja m=3:

Koodi: Valitse kaikki

x = 7**77 # seed number
count = 0
while count < 2000:
  print(x)
  if x % 3 != 0 and (4 * x + 1) % 3 == 0:
    x = 4 * x + 1
  if x % 3 != 0 and (4 * x - 1) % 3 == 0:
    x = 4 * x - 1
  if x % 3 == 0:
    x = (x // 3)
  if x<2:
    print(x)
    count = 2000
  count += 1

[Eusa]

Ehtisiköhän kukaan testailla laajemmin näiden luomieni rekursioiden pätevyyttä? Itselläni aika tuppaa olla varattu muuhun...

[Eusa]

Tässä mennään jo aika limiiteille löytämieni periaatteiden suhteen:

Koodi: Valitse kaikki

x = 34569**22 # seed number
count = 0
while count < 2000:
  print(x)
  if x % 5 != 0 and (6 * x + 1) % 5 == 0:
    x = 6 * x + 1
  if x % 5 != 0 and (6 * x - 1) % 5 == 0:
    x = 6 * x - 1
  if x % 5 != 0 and (3 * x + 1) % 5 == 0:
    x = 3 * x + 1
  if x % 5 != 0 and (3 * x - 1) % 5 == 0:
    x = 3 * x - 1
  if x % 5 == 0:
    x = (x // 5)
  if x<2:
    print(x)
    count = 2000
  count += 1

[Eusa]

Tässä algoritmi, jolla saadaan paljastettua Collatzin pähkinän logiikan salat laajennetussa muodossaan - kun tekijä-slot muuntuu täyttävästi siirtyen vain yhden kongruenssitransition tekijäavaruudessa poissuljettuna vakiojakaja, ei voida päätyä ketjussa samaan lukuun ja kun paisuntakertoimet ovat alle kaksinkertaiset neliöttömästi alkulukuisia, ei myöskään kasva äärettömiin. Vakiojakaja 7 sallii liki kaksinkertaiseen asti paisuntakertoimet (...13). Tämä kiertelee ketjussa lukuja samalta korkeudelta n. viisi kertaa hitaammin kuin alkuperäinen Collatzin rekursio. Tällä logiikalla voidaan rakentaa mielivaltaisen suuren jakajan rekursio, joka rajatta lähestyy sitä, että käy läpi kaikki luonnolliset luvut eli kaikenlaiset tekijä-slotit.

Koodi: Valitse kaikki

x = 156**55 # seed number
count = 0
while count < 5000:
  print(x)
  if x % 7 != 0 and (13 * x + 1) % 7 == 0:
    x = 13 * x + 1
  if x % 7 != 0 and (13 * x - 1) % 7 == 0:
    x = 13 * x - 1
  if x % 7 != 0 and (11 * x + 1) % 7 == 0:
    x = 11 * x + 1
  if x % 7 != 0 and (11 * x - 1) % 7 == 0:
    x = 11 * x - 1
  if x % 7 != 0 and (10 * x + 1) % 7 == 0:
    x = 10 * x + 1
  if x % 7 != 0 and (10 * x - 1) % 7 == 0:
    x = 10 * x - 1
  if x % 7 != 0 and (6 * x + 1) % 7 == 0:
    x = 6 * x + 1
  if x % 7 != 0 and (6 * x - 1) % 7 == 0:
    x = 6 * x - 1
  if x % 7 != 0 and (5 * x + 1) % 7 == 0:
    x = 5 * x + 1
  if x % 7 != 0 and (5 * x - 1) % 7 == 0:
    x = 5 * x - 1
  if x % 7 != 0 and (3 * x + 1) % 7 == 0:
    x = 3 * x + 1
  if x % 7 != 0 and (3 * x - 1) % 7 == 0:
    x = 3 * x - 1
  if x % 7 == 0:
    x = x // 7
  if x < 3:
    print(str(x) + " - " + str(count) + " steps.")
    count = 5000
  count += 1

[Eusa]

Aikaisemmasta jakaja viiden rekursiosta oli unohtunut paisuttaja 7 pois. Vaikka seitsemän ei ole lähelläkään tuplarajaa 10, joillain luvuilla tulee todella pitkiä ketjuja suhteessa lähtölukuun, kuten luvulla 156 saa 212 askelta:

Koodi: Valitse kaikki

x = 156 # seed number
count = 0
while count < 2000:
  print(x)
  if x % 5 != 0 and (7 * x + 1) % 5 == 0:
    x = 7 * x + 1
  if x % 5 != 0 and (7 * x - 1) % 5 == 0:
    x = 7 * x - 1
  if x % 5 != 0 and (6 * x + 1) % 5 == 0:
    x = 6 * x + 1
  if x % 5 != 0 and (6 * x - 1) % 5 == 0:
    x = 6 * x - 1
  if x % 5 != 0 and (3 * x + 1) % 5 == 0:
    x = 3 * x + 1
  if x % 5 != 0 and (3 * x - 1) % 5 == 0:
    x = 3 * x - 1
  if x % 5 == 0:
    x = x // 5
  if x < 2:
    print(str(x) + " - " + str(count) + " steps.")
    count = 2000
  count += 1

[Eusa]

Eli, kun en saanut helposti kuvattua tekijä-slotin sielunelämää muuten, todistin ikään kuin induktiolla: vakiojakajana 3, 5, 7, 11,... Seuraava mielenkiintoinen vakiojakaja olisi 19, koska sillä suurin mahdollinen paisuttaja 37 on juuri yhtä pienempi kuin 2x19. Mikäli joku haluaa testailla, odotettavissa olisi pitkiä mutkittelevia ketjuja...

[Eusa]

Yleisestä Eusa-rekursiokaavasta Collatzin konjektuuri löytyy siitä laitetaanko yhden askeleen kongruenssisiirtoehdoksi ensin +1 eli onko 3x+1 jaollinen kahdella - no, se on aina, joten seuraavaa ehtoa 3x-1 ei koskaan tarvita. Jos -1 -ehto laitetaankin kärkeen, saadaan Collatzin sisarkonjektuuri eli (3x-1)/2... Enää ei oikeastaan sovi puhua konjektuurista vaan ymmärrettävästä yksinkertaisimmasta Eusa-rekursiosta.

Rekursiostani löytyy tietysti variantteja riippuen mihin järjestykseen pareittain eri mahdollisten paisuttajien -1 & +1 -ehdot järjestetään.

Mikäli joku jäi ihmettelemään miksi alkulukujen potensseja ei saa esiintyä paisuttajakertoimissa, esim. 7-rekursiossa ei tekijöinä 4, 8 eikä 9, niin se johtuu luonnollisesti siitä, että silloin kertaudutaan samassa tekijä-slotissa ja ketju voikin ajautua luuppiin - vrt. peräkkäiset operaatiot vakiojakajalla.

[Eusa]

Mielestäni todistuksen logiikka on niin selvä, että sen voi peruskoululainen ymmärtää, vai kuinka?

[Eusa]

Hm. Vakiojakajalla 7 näyttää algoritmi vievän lukuja luuppiin joillain pienillä arvoilla, mitä ei tapahdu vakiojakajan 5 algoritmissa. Näyttäisi liittyvän koottuihin paisuttajiin ja peräkkäin vuorottaisiin +1 / -1 -siirtoihin, joilla pääsee luikahtamaan samaan slotiin... Ehkä paisuttajat on järjestettävä niin, että priorisoidaan puhtaita alkulukutekijöitä ja jos sen seulan jälkeen on vielä siirtoluku vakiojakajalle löytymättä, saadaan mennä koottuihin paisuttajiin, ei kuitenkaan potensseja sisältäviin - tai pitääkin ilmeisesti priorisoida kootut kertojat alkuun... Tutkimus jatkuu...