Collatzin pähkinän todistus

[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...

[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.