3n+1 - collatz conjecture

Algemene info over deze site. Suggesties e.d. kunnen hier ook geplaatst worden.
Plaats reactie
PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

3n+1 - collatz conjecture

Bericht door PingPong77 » 06 okt 2015, 17:08

hallo allemaal.

ff, mezelf en mijn probleem voorstellen. Ik ben een Lichtjockey in een discotheek, Deze job geeft mij in de week veel tijd om zinloze dingen te doen, zoals youtubefilmpjes bekijken. ongeveer 2 jaar geleden kwam in deze video reeks tegen (famous math problems by dr wildberger).

De collatz conjecture is een fantastisch probleem om uren en uren aan te spenderen, zonder ook maar een stap verder te komen. m.a.w. Het probleem was op mijn lijf geschreven.

Hellaas, na twee jaar sporadish, (en af en toe fanatiek) met deze materie te spelen kom ik opeens op een punt waar ik denk dat ik een deel van het probleem kan bewijzen. En dit is het punt waar ik een vast zit... ik ben op zoek naar iemand die zou willen helpen met het uitschrijven en controleren van mijn oplossing. Ik denk dat ik de kern op 3 A4-tjes kan uitleggen, Kan dit hier op het forum?

PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

Stap 1: Algemene patronen.

Bericht door PingPong77 » 06 okt 2015, 18:52

wanneer een getal even is deel het door 2



wanneer een getal oneven is vermenigvuldig het door 3 en tel er 1 bij op




Bijvoorbeeld



ieder even getal zal uiteindelijk omgevormd worden tot een oneven getal dus. In een eerste vereenvoudigde versie van de colatzformatie (als het een transformatie is???) zullen we de even getallen weg laten.

bijvoorbeeld:




Als een tweede vereenvoudiging zullen we de oneven getallen indexeren door een index (i). Dit wil zeggen 1 schrijven we als 0, 3 als 1, 5 als 2 ect



ter verduidelijking onderstaande tabel:

Code: Selecteer alles

 0 ( 1)     1 ( 3)      2 ( 5)     3 ( 7) 
 4 ( 9)     5 (11)      6 (13)     7 (15)
 8 (17)     9 (19)     10 (21)    11 (23)
12 (25)    13 (27)     14 (29)    15 (31) 
vanaf hier werk ik enkel nog met indexen.


laat ons een kijken of we patronen kunnen herkennen in de geindexeerde collatz map. onderstaande tabel geeft ons een index gevolgd door de index die resulteert uit de collatztransformatie


ter verduidelijking onderstaande tabel:

Code: Selecteer alles

kolom A   | kolom B    | kolom C   | kolom D
 0 -> 0   |  1 ->  2   |   2 -> 0  |   3 ->  5 
 4 -> 3   |  5 ->  8   |   6 -> 2  |   7 -> 11
 8 -> 6   |  9 -> 14   |  10 -> 0  |  11 -> 17
12 -> 9   | 13 -> 20   |  14 -> 5  |  15 -> 23

16 -> 12  | 17 -> 26   |  18 -> 3  |  19 -> 29 
20 -> 15  | 21 -> 32   |  22 -> 8  |  23 -> 35 
24 -> 18  | 25 -> 38   |  26 -> 2  |  27 -> 41 
28 -> 21  | 29 -> 44   |  30 -> 11 |  31 -> 47 

32 -> 24  | 33 -> 50   |  34 -> 6  |  35 -> 53 
in kolom kolomen A, B en D kunnen we een duidelijk patroon zien. Op het eerste zicht gedraagt kolom C zich echter vrij chaotish. (we zullen dadelijk aantonen dat deze chaos met een simpele bewerking te weg valt).

Voor kolom A kunnen we scrijven



Voor kolom B en D geld





Laten we nu ff kolom C wat ordelijker maken:

2 (op de nulde rij van kolom C) geeft als resultaat 0, de index 0 geeft ook als resultaat 0.
6 (op de eerste rij van kolom C) geeft als resultaat 2, de index 1 geeft ook als resultaat 2.
10 (op de tweede rij van kolom C) geeft als resultaat 0, de index 2 geeft ook als resultaat 0.
16 (op de derde rij van kolom C) geeft als resultaat 5, de index 3 geeft ook als resultaat 5.
... en zo kunnen we nog even doorgaan (dit heb ik nog niet bewezen, maar voor de eerste 200 rijen klopt dit resultaat)

we kunnen kolom C ordelijker maken door een "virtuele tussenstap te introduceren" in plaats van naar het directe resultaat te gaan (hetgeen chaotisch lijkt), kunnen we een ordelijkere weg volgen via een tussenstap. deze tussenstap zal ons vriendelijk en ordelijk naar het uiteindelijk resultaat lijden (zonder we de indruk hebben dat er iets willekeurig gebeurt).

Voor kolom C kunnen we scrijven




we herscrijven onze tabel dan als volgt

Code: Selecteer alles

kolom A   | kolom B    | kolom C   | kolom D
 0 -> 0   |  1 ->  2   |   2 -> 0  |   3 ->  5 
 4 -> 3   |  5 ->  8   |   6 -> 1  |   7 -> 11
 8 -> 6   |  9 -> 14   |  10 -> 2  |  11 -> 17
12 -> 9   | 13 -> 20   |  14 -> 3  |  15 -> 23

16 -> 12  | 17 -> 26   |  18 -> 4  |  19 -> 29 
20 -> 15  | 21 -> 32   |  22 -> 5  |  23 -> 35 
24 -> 18  | 25 -> 38   |  26 -> 6  |  27 -> 41 
28 -> 21  | 29 -> 44   |  30 -> 7  |  31 -> 47 

32 -> 24  | 33 -> 50   |  34 -> 8  |  35 -> 53 
We stellen nu dat er 4 verzamelingen zijn: A B C D, met respectievelijk de indexen uit kollomen A,B,C,D (dit kan formeler geschreven worden maar ik wil het hier zo kort mogelijk houden.)

een element van D kan enkel naar D of naar B "springen"
een element van C kan naar A B C of D "springen"
een element van B kan naar A of C "springen"
een element van A kan naar A B C of D "springen"

(ik gebruik hier "springen" omdat ik niet weet of ik "getransformeerd" in deze context kan gebruiken)

we kunnen onze vertrouwde tabel dan nog eens herschrijven, deze keer met de index, en de doelverzameling.

Code: Selecteer alles

kolom A   | kolom B   | kolom C   | kolom D
 0 -> A   |  1 -> C   |   2 -> A  |   3 -> B  
 4 -> D   |  5 -> A   |   6 -> B  |   7 -> D
 8 -> C   |  9 -> C   |  10 -> C  |  11 -> B
12 -> B   | 13 -> A   |  14 -> D  |  15 -> D

16 -> A   | 17 -> C   |  18 -> A  |  19 -> B 
20 -> D   | 21 -> A   |  22 -> B  |  23 -> D 
24 -> C   | 25 -> C   |  26 -> C  |  27 -> B 
28 -> B   | 29 -> A   |  30 -> D  |  31 -> D 

32 -> 24  | 33 -> C   |  34 -> A  |  35 -> B 
we merken op de er zich een herhaaldelijk patroon voordoet. dat zich na 16 indexen herhaalt.

Dit patroon herhaalt zich zo mooi dat we er gebruik van maken in onze volgende stap, de VierkantsRepresentatie.

PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

De vierkants representatie

Bericht door PingPong77 » 06 okt 2015, 19:52

tot nu toe hebben we steeds de onze voorbeeld tabel met 4 kolomen afgebeeld, maar we hebben echter opgemerkt dat deze zich na 16 indexen herhaalt. wat als we deze tabel herscrijven met 16 kolomen?

Code: Selecteer alles

 0 -> A |  1 -> C |  2 -> A |  3 -> B |  4 -> D |  5 -> A |  6 -> B |  7 -> D |  8 -> C |  9 -> C | ...
16 -> A | 17 -> C | 18 -> A | 19 -> B | 20 -> D | 21 -> A | 22 -> B | 23 -> D | 24 -> C | 25 -> C | ...
32 -> A | 33 -> C | 34 -> A | 35 -> B | 36 -> D | 37 -> A | 38 -> B | 39 -> D | 40 -> C | 41 -> C | ...
Het is duidelijk dat elk van deze 16 kolomen verwacht dat er elk van zijn rijen dezelfde bewerking word uitgevoerd...
wanneer we dit doen dan krijgen we:

Code: Selecteer alles

 0 -> 0  -> 0  (A) |  1 ->  2 ->  0 (A)  |  2 ->  0 ->  0 (A) |  ...  |  15 ->  23 ->  35 (D)
16 -> 12 -> 9  (B) | 17 -> 26 ->  6 (C)  | 18 ->  4 ->  3 (D) |  ...  |  31 ->  47 ->  71 (D)
32 -> 24 -> 18 (C) | 33 -> 50 -> 12 (A)  | 35 ->  8 ->  6 (C) |  ...  |  47 ->  71 -> 107 (D)
48 -> 36 -> 27 (D) | 49 -> 74 -> 18 (C)  | 34 -> 12 ->  9 (B) |  ...  |  63 ->  95 -> 143 (D)

64 -> 48 -> 36 (A) | 65 -> 98 -> 24 (A)  | 66 -> 16 -> 12 (A) |  ...  |  79 -> 119 -> 179 (D)
wegens plaatsgebrek kan ik hier maar 4 van de 16 kolomen weergeven... Ook hier valt het op (en zeker via de computer gegenereerde tabellen) dat het patroon van doelverzamelingen zich hier ook na 4 rijen herhaalt. (of anders gezecht, na 64 indexen).

Wanneer we een dit proces herhalen, en naar 64 kolomen gaan, komen we tot de konstatatie dat wederom het zelfde gebuert, na de eerste vier rijen herhaalt zich het patroon van doelverzamelingen. (of na 256 indexen).

We merken ook op dat we voor elke kolom een formulle kunnen opstellen om het doelgetal op de rij (r) kunnen bekomen.

(1)

Wat Bedoelen we nu met vierkants-representatie?
een vierkants-representatie is eigenlijk gelijk aan de tabel die we al de hele tijd gebruiken.

Een vierkanstrepresentatie van de eerste graad heeft 4 kolomen, en in elke kolom wordt een colatz transformatie uitgevoerd.

Een vierkantsrepresentatie van de tweede graad heeft 16 kolomen, en in elke kolom worden er 2 collats transformaties uitgevoerd.

dus het aantal kolomen "K" bescrijven we als volgt

(2)

waar k gelijk is aan de graad van de voorstelling.

merk op dat K ook gelijk is aan het verschil tussen twee opeenvolgende beginindexen in een zelfde kolom. (dit zullen we later gebruiken)

ik ga er vanuit (maar heb dit nog niet bewezen) dat dit herhaaldelijk patroon zich steeds zal voordoen, en dat dusdanig er steeds een hogere graad van vierkantsvoorstelling mogelijk is. Ik veronderstel dit op basis van de verschillende tussenstappen die gedurende 2 jaar tegengekomen ben, dus het is meer dan een vermoeden, maar geen bewijs.
Laatst gewijzigd door PingPong77 op 06 okt 2015, 20:13, 1 keer totaal gewijzigd.

PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

Mogelijkheid op gedeeltelijk bewijs.

Bericht door PingPong77 » 06 okt 2015, 20:05

Er zijn drie mogelijkheden om de collatz conjecture te onkrachten.

1. Counter example (brute force computation), dit gaan we niet doen :)
2. bewijzen dat er een sequentie is die oneindig ver oploopt. (dit gaan we ook niet doen)
3. bewijzen dat er een andere cyclus bestaat buiten (1 -> 4 -> 2 -> 1 -> ...) of in index notatie (0 -> 0 -> ... ). Dat gaan we ook niet doen.

Wat we wel willen doen is bewijzen dat de optie op een andere cyclus niet bestaat. dus dat de enige cyclus die mogelijk is die van is.

We gaan dit doen via ¨Proof by contradiction" m.a.w. ff aannemen dat zo'n lus bestaat, en dan aantonen dat dit onlogische consequenties met zich me brengt, zodat het duidelijk is dat we niet kunnen aanemen dat die lus bestaat.

PS, waarschijnlijk zal ik wel weer een fout in de mijn logica hebben... maar ik denk dat de bovenstaande twee posts informatie bevatten die ik nog niet ben tegengekomen online. Voornamelijk de virtuele tussenstap om kolom C ordelijk te maken, hetgeen het geheel een minder random karakter geeft.

PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

Re: 3n+1 - collatz conjecture

Bericht door PingPong77 » 07 okt 2015, 13:22

hmm, heb een foutje ontdekt... geen bewijs dus.

PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

Re: 3n+1 - collatz conjecture

Bericht door PingPong77 » 14 okt 2015, 16:51

Na nog wat puzzelen denk ik dat ik toch een bewijs kan formuleren...




We bescrijven de volgende lus:


waarin



iedere staat voor een van de volgende bewerkingen

A:

B:

C:

A en B worden gebruikt als L_n even is, en hierbij geld dat

B wordt gebruikt als L_n oneven is, en hierbij geld dat


hieruit kunnen we opmaken dat een lus zowel even als oneven indexen moet bevatten.

laat ons aannemen dat we voor L_0 van onze lus een oneven getal nemen:
L_n zal dan altijd van de volgende vorm zijn:



wanneer we een lus hebben dan kunnen we dit herscrijven tot:















2^y = even (voor y > 0)
3^x = oneven

2^y - 3^x = oneven


L_0 is oneven (begin conditie)

(2^y - 3^x) l_0 = oneven omdat (oneven * oneven = oneven)

dit geeft de volgede contradictie:
2p= oneven, met

het is dus onmoglijk om een lus te maken, beginnend bij een oneven index. (en een lus moet even en oneven indexen bevatten)

PingPong77
Nieuw lid
Nieuw lid
Berichten: 13
Lid geworden op: 30 mei 2012, 22:06

Bericht door PingPong77 » 14 okt 2015, 23:51

PingPong77 schreef:Na nog wat puzzelen denk ik dat ik toch een bewijs kan formuleren...

A en B worden gebruikt als L_n even is, en hierbij geld dat

B wordt gebruikt als L_n oneven is, en hierbij geld dat

typo gevonden, ik bedoelde eigenlijk:

A en B worden gebruikt als L_n even is, en hierbij geld dat

B wordt gebruikt als L_n oneven is, en hierbij geld dat

Plaats reactie