Collatz conjecture of 3x+1 probleem

[Nesciyolo]

m en n hebben een vaste verhouding. We hoeven dus niet alle getallen te bekijken. Alleen getallen die aan die verhouding voldoen. Dat zijn er relatief gezien maar enkele.

Dat denk ik niet.
\(n\approx m\frac{\log 2}{\log 3}\)
Er zijn geen gehele getallen n en m te vinden die hier exact aan voldoen.

Precies! Als je aantoont dat de bandbreedte onbereikbaar is voor gehele waardes van m en n dan heb je aangetoond dat er geen loops kunnen bestaan. Moeten we natuurlijk mijn berekening van de bandbreedte nog wel even goed nalopen.
In de Veritasium video werd wel verteld dat mensen hebben berekend dat een loop heel erg lang moet zijn. misschien hebben ze dat wel met deze methode gedaan.

[Xilvo]

Zie dat ook dit basisgetal in slechts 3 stappen een kleiner getal bereikt.

Voor sommige getallen kun je dat direct al beredeneren, zoals je eerder schreef. Voor andere zal je het moeten proberen.

Natuurlijk kun je een fors percentage van de getallen al uitsluiten maar op de enorme hoeveelheid getallen die je zou willen controleren als je zelfs maar een decade verder wil komen dan die 2⁶⁸ is dat een druppel op een gloeiende plaat.

[Xilvo]

In de Veritasium video werd wel verteld dat mensen hebben berekend dat een loop heel erg lang moet zijn. misschien hebben ze dat wel met deze methode gedaan.

Ja, minstens 186 miljard, dacht ik.

Als je numeriek een tegenvoorbeeld wil vinden dan moet je naar zo'n loop zoeken, volgens mij. Numeriek kun je nooit aantonen dat een reeks nooit naar 1 gaat, als die maar blijft groeien maar niet in een loop terecht komt.

[Nesciyolo]

Numeriek kun je nooit aantonen dat een reeks nooit naar 1 gaat, als die maar blijft groeien maar niet in een loop terecht komt.

Maar je kan wel analyseren waarom het gebeurt. Of er bijvoorbeeld regelmatigheden zijn in de opvolging van de bewerkingen. De computer kan een getal "waar wat mee is" identificeren zodat er door menen naar gekeken kan worden als er na meer dan zeg een miljoen stappen nog geen zicht op daling is.

[Xilvo]

Maar je kan wel analyseren waarom het gebeurt. Of er bijvoorbeeld regelmatigheden zijn in de opvolging van de bewerkingen. De computer kan een getal "waar wat mee is" identificeren zodat er door menen naar gekeken kan worden als er na meer dan zeg een miljoen stappen nog geen zicht op daling is.

Natuurlijk, maar dan ben je al niet meer alleen numeriek bezig. Dan probeer je patronen te herkennen.
Maar dan moet je eerst maar eens zo'n getal zien te vinden, dat na een miljoen iterarties nog niet naar 1 is gezakt.
Dat is op zich al in een astronomisch grote hooiberg zoeken naar een speld die er misschien niet eens is.

[RedCat]

n=1240913164837493520914469575281720548839055905624577375251388717505927743

Wat is de status van dat getal? Is dat de kleinste uitzondering?

Je had al gevonden dat iteratief q keer de functie f(x)=(3x+1)/2 toepassen op begingetal n oplevert:

\(\small f^q(n)=\frac{3^q}{2^q}(n+1)-1\)

Vervolgens willen we dat f^q(n) een macht van 2 is, zodat de Collatz-rij door herhaald delen door 2 naar 1 gaat:

\(\small f^q(n)=\frac{3^q}{2^q}(n+1)-1 = 2^c\)

voor gehele getallen c

Hieruit volgt dat ons begingetal moet voldoen aan

\(\small n = \frac{2^q}{3^q}(2^c+1)-1\)

Als n een geheel getal is dan moet (2^c+1) deelbaar zijn door 3^q:

\(\small 2^c+1 \equiv 0 \mod 3^q\)

ofwel

\(\small 2^c \equiv -1 \mod 3^q\)

ofwel

\(\small (3-1)^c \equiv -1 \mod 3^q\)

ofwel

\(\small 3^c + {c \choose 1}3^{c-1}(-1) + {c \choose 2}3^{c-2}(-1)^2 + ... + {c \choose c-1}3(-1)^{c-1}+ (-1)^c\equiv -1 \mod 3^q\)

Voor q=1 rekenen we modulo 3, dus zijn alle termen links behalve de laatste equivalent aan nul, en houden we over:

\(\small (-1)^c\equiv -1 \mod 3\)

waardoor we oplossingen hebben voor alle oneven getallen c: c ∈ I = {1, 3, 5, 7, 9, ...}

Vervolgens kan je met bovenstaande formule inductief bewijzen dat voor elke q de oplossingen voor c gegeven worden door:

\(c = 3^{q-1}\cdot i\)

met i ∈ {1, 3, 5, 7, 9, ... }

De eerste (= kleinste) oplossing voor q=6 is daardoor

\(\small c = 3^{6-1}\cdot 1 = 3^5 = 243\)

waardoor in dit geval

\(\small n = \frac{2^q}{3^q}(2^c+1)-1 = \frac{2^6}{3^6}(2^{243}+1)-1\)

\(\small = 1240913164837493520914469575281720548839055905624577375251388717505927743\)

Hier de eerste getallen van deze Collatz-rij:

Code: Selecteer alles

0       1240913164837493520914469575281720548839055905624577375251388717505927743
1       1861369747256240281371704362922580823258583858436866062877083076258891615
2       2792054620884360422057556544383871234887875787655299094315624614388337423
3       4188081931326540633086334816575806852331813681482948641473436921582506135
4       6282122896989810949629502224863710278497720522224422962210155382373759203
5       9423184345484716424444253337295565417746580783336634443315233073560638805
6       14134776518227074636666380005943348126619871175004951664972849610340958208 = 2^243

[Nesciyolo]

\(\small c = 3^{6-1}\cdot 1 = 3^5 = 243\)

OK. Ik begin je een beetje te volgen. Ik moet er nog een paar keer naar kijken denk ik voordat ik het helemaal door heb.

[Xilvo]

Hier die eerste termen binair (waarbij 3x+1 en x/2 separate stappen zijn) tot er een macht van 2 ontstaat.

Code: Selecteer alles

101100111100110000000111000001011111100001000110001110111011001010111110010101001111101101101111010100011101001001011001001100100011011101111011111101100010101011010111100111011010110001101100001010001011110000111001100101110101101000111111
10000110110110010000010101000100011110100011010010101100110001100000111010111111101111001001001101111101010111011100001011100101101010011001110011111000101000000010000110110110010000010101000100011110100011010010101100110001100000111010111110
1000011011011001000001010100010001111010001101001010110011000110000011101011111110111100100100110111110101011101110000101110010110101001100111001111100010100000001000011011011001000001010100010001111010001101001010110011000110000011101011111
11001010010001011000011111100110101101110100111100000011001010010001011000011111100110101101110100111100000011001010010001011000011111100110101101110100111100000011001010010001011000011111100110101101110100111100000011001010010001011000011110
1100101001000101100001111110011010110111010011110000001100101001000101100001111110011010110111010011110000001100101001000101100001111110011010110111010011110000001100101001000101100001111110011010110111010011110000001100101001000101100001111
100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101111011010000100101110
10010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111101101000010010111
111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000111000110
11100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
//
1000
100
10
1

[Nesciyolo]

Vervolgens kan je met bovenstaande formule inductief bewijzen dat voor elke q de oplossingen voor c gegeven worden door:

\(c = 3^{q-1}\cdot i\)

met i ∈ {1, 3, 5, 7, 9, ... }

Dat is consistent met de waarde die ik gevonden heb voor q=4 in mijn post namelijk 2^27.