Collatz conjecture of 3x+1 probleem

[Nesciyolo]

Zoals in mijn vorige post zal ik in deze post uitgaan van het omgeschreven probleem. Dus in het geval een getal oneven is bewerk ik het niet met naar y=3x+ 1 maar naar y=1,5x+0,5. Een even getal zal ik volgens de regels delen door 2.

laten we de reeks eens doorlopen voor het getal 255. Dat is \(2^8-1\).
\(x = 2^8-1\)
\(y=1,5x+0,5=2^8-1+(2^7-0,5)+0,5 = 2^8+2^7-1\)
\(y=1,5x+0,5=2^8+2^7-1+(2^7+2^6-0,5)+0,5 = 2^8+2*2^7+2^6-1=2^9+2^6-1\)
\(y=1,5x+0,5=2^9+2^6-1+(2^8+2^5-0,5)+0,5=2^9+2^8+2^6+2^5-1\)
\(y=1,5x+0,5=2^9+2^8+2^6+2^5-1+(2^8+2^7+2^5+2^4-0,5)+0,5\)
\(=2^9+2*2^8+2^7+2^6+2*2^5+2^4-1=2\)¹⁰\(+2^8+2^4-1\)
\(y=1,5x+0,5=2\)¹⁰\(+2^8+2^4-1+(2^9+2^7+2^3-0,5)+0,5\)
\(=2\)¹⁰\(+2^9+2^8+2^7+2^4+2^3-1\)
\(y=1,5x+0,5=2\)¹⁰\(+2^9+2^8+2^7+2^4+2^3-1+(2^9+2^8+2^7+2^6+2^3+2^2-0,5)+0,5\)
\(=2\)¹⁰\(+2*2^9+2*2^8+2*2^7+2^6+2^4+2*2^3+2^2-1\)
\(=2\)¹¹\(+2^9+2^8+2^6+2^5+2^2-1\)
\(y=1,5x+0,5\)
\(=2\)¹¹\(+2^9+2^8+2^6+2^5+2^2-1+(2\)¹⁰\(+2^8+2^7+2^5+2^4+2^1-0,5)+0,5\)
\(=2\)¹¹\(+2\)¹⁰\(+2^9+2*2^8+2^7+2^6+2*2^5+2^4+2^2+2^1-1\)
\(=2\)¹²\(+2^8+2^4+2^2+2^1-1\)
\(y=1,5x+0,5\)\(=2\)¹²\(+2^8+2^4+2^2+2^1-1+(2\)¹¹\(+2^7+2^3+2^1+2^0-0,5)+0,5\)
\(=2\)¹²\(+2\)¹¹\(+2^8+2^7+2^4+2^3+2^2+2*2^1+1-1\)
\(=2\)¹²\(+2\)¹¹\(+2^8+2^7+2^5\) Deze is even!
\(y=x/2=(2\)¹²\(+2\)¹¹\(+2^8+2^7+2^5)/2\)\(=2\)¹¹\(+2\)¹⁰\(+2^7+2^6+2^4\)
\(y=x/2=(2\)¹¹\(+2\)¹⁰\(+2^7+2^6+2^4)/2\)\(=2\)¹⁰\(+2^9+2^6+2^5+2^3\)
\(y=x/2=(2\)¹⁰\(+2^9+2^6+2^5+2^3)/2\)\(=2^9+2^8+2^5+2^4+2^2\)
\(y=x/2=(2^9+2^8+2^5+2^4+2^2)/2\)\(=2^8+2^7+2^4+2^3+2^1\)
\(y=x/2=(2^8+2^7+2^4+2^3+2^1)/2\)\(=2^7+2^6+2^3+2^2+2^0=2^7+2^6+2^3+2^2+1\)Deze is oneven!

We hebben nu een waarde bereikt die lager is dan 255.
We kunnen elk positief natuurlijk getal schrijven als een combinatie van 2-machten
5 = 2^0+2^2
7 = 2^0+2^1+2^2 enzovoorts. Dat is hoe we binaire getallen schrijven.
Elke 2-macht die we met 1,5ⁿ vermenigvuldigen komt noodzakelijkerwijs uiteindelijk op een oneven getal uit en leidt daardoor noodzakelijkerwijs tot een situatie waarin we moeten gaan delen. Bij elke deling neemt de complexiteit van de samenstelling van het getal iets af.

Dus voor elk positief geheel getal geldt dat de Collatz bewerkingen uiteindelijk naar de loop 1-4-2-1 bewegen.

Ik moet nog even nadenken over hoe ik dat op moet schrijven. Maar ik denk dat dat de oplossing van het probleem is.

[Nesciyolo]

Om dit voor alle getallen tot x=2⁶⁹ te bewijzen hoeven we het alleen maar te bewijzen voor x=(2⁶⁹-1). Maar eigenlijk is zelfs dat niet nodig.

[HansH]

Zoals in mijn vorige post zal ik in deze post uitgaan van het omgeschreven probleem. Dus in het geval een getal oneven is bewerk ik het niet met naar y=3x+ 1 maar naar y=1,5x+0,5. Een even getal zal ik volgens de regels delen door 2.

Ik denk dat je in de goede richting zit door te denken in het binaire stelsel (schrijven als machten van 2), maar ik zou blijven denken in y=3x+ 1 en dat ook binair opschrijven dus nieuw getal= oud getal x (2^1+2^2)+1
dan zie je dat je het oude getal feitelijk alle bits 1 naar links schuift (= vermenigvuldigen met 2^1) en dan hetzelfde maar dan 2 bits naar links (=2^2) en dan die 2 optelt en er nog 2^0 bijtelt.

het resultaat is dan nog steeds een binair getal wat je kunt delen door 2 behalve als bit 0 gelijk is aan 1 want dan is het oneven. Dat proces herhalen levert dus steeds weer een even getal op bij elke 2 keer dat je de stap nieuw getal= oud getal x (2^1+2^2)+1 doet. wat er inks van het LSB staat wordt steeds groter maar is altijd deelbaar door 2 (= 1 bit naar recht schuiven) en levert dus bij delen door 2 een oneven getal als jet LSB+1 een 1 is. Je kunt dus door 2 delen als het LSB gelijk is aan 0. Dat proces algemeen opschrijven en goed kijken naar waar de nullen voorkomen in de bits van het binaire getal want die leveren weer een oneven getal als deelt door 2 (alle bits 1 naar rechts)
de structuur zien in dat proces zal dan waarschijnlijk het bewijs opleveren.

[HansH]

bv binair 100101101 =301dec is oneven dus krijg je daarna
01001011010 (= x 2^1=alles 1 bit naar links)=602 plus
10010110100 (= x 2^2= alles 2 bits naar links)=1204 plus 1
00000000001 =
11100001111 (=1807)
dat kun je niet delen door 2 dus als je nogmaals de stap y=3x+ 1 doet dan krijg je
binair 1010100101110 (5422 dec) en heb je dus bij het oorspronkelijke getal 2 opgeteld dus weer even. verder is er dan eea naar links geschoven en door de optellng kan het dan dus zijn dat je ergens meer naar links 1+1=0 en een extra 1 erbij 1 bit meer naar links krijgt. Dat proces moet je dus structuur in herkennen op een of andere manier voor het bewijs.

[HansH]

Ik denk dat je in de goede richting zit door te denken in het binaire stelsel

helaas kan ik mijn bericht niet meer editen, dus dan maar mijn eigen bericht citeren (dat is dus geen voorbeeld van jezelf belangrijk proberen te maken)
niet alleen in de goede richting, maar een doorbraak denk ik in de kans om tot een bewijs te kunnen komen.
De reden is dat je door in het binaire stelsel te denken duidelijk kunt volgen wat er in de hogere bits gebeurt bij delen door 2 (= 1 bit naar rechts schuiven) en dus al vantevoren kunt zien aankomen hoe lang je door 2 kunt blijven delen zonder op een oneven getal uit te komen. Voor het bewijs zul je dus moeten aantonen dat je uiteindelijk geen nullen meer hebt links van het LSB als je het proces herhaalt. want als er ergens een 0 zit komt die uiteindelijk bij herhaald delen door 2 als LSB en komt je dus niet uit.

[Xilvo]

Om dit voor alle getallen tot x=2⁶⁹ te bewijzen hoeven we het alleen maar te bewijzen voor x=(2⁶⁹-1). Maar eigenlijk is zelfs dat niet nodig.

Waar komt dat vandaan?
Als het vermoeden bewezen is voor alle getallen tot en met n, dan weet je dat het voor een getal m>n geldt zodra je in de reeks beginnend met m een getal kleiner of gelijk n aantreft.

Als je met n begint dan kom je onderweg naar 1 (stel dat je daar komt) getallen kleiner dan n tegen. Maar zeker niet alle getallen kleiner dan n. Dus als n-3 niet voorkomt in de reeks van n, dan heb je het niet bewezen voor n-3.

[Xilvo]

bv binair 100101101 =301dec is oneven dus krijg je daarna
01001011010 (= x 2^1=alles 1 bit naar links)=602 plus
10010110100 (= x 2^2= alles 2 bits naar links)=1204 plus 1
00000000001 =
11100001111 (=1807)

Hier gaat volgens mij iets verkeerd.
301 is oneven dus kom je op 3 x 301+1=904 (1110001000)

[Marko]

3 is dan ook niet gelijk aan 2^2 + 2^1

[Nesciyolo]

Om dit voor alle getallen tot x=2⁶⁹ te bewijzen hoeven we het alleen maar te bewijzen voor x=(2⁶⁹-1). Maar eigenlijk is zelfs dat niet nodig.

Waar komt dat vandaan?
Als het vermoeden bewezen is voor alle getallen tot en met n, dan weet je dat het voor een getal m>n geldt zodra je in de reeks beginnend met m een getal kleiner of gelijk n aantreft.

Als je met n begint dan kom je onderweg naar 1 (stel dat je daar komt) getallen kleiner dan n tegen. Maar zeker niet alle getallen kleiner dan n. Dus als n-3 niet voorkomt in de reeks van n, dan heb je het niet bewezen voor n-3.

Dat heb ik zelf ingezien maar kan ik nog niet hard maken. Ik neem het voorlopig even terug. Het was laat gisteren en ik draafde wat door. Ik heb wel het gevoel dat ik op de goede weg ben maar ik moet nog zien waar die uitkomt.
x=(2^n)-1 is interessant omdat dat vanaf het begin de langste aaneengesloten rij vermenigvuldigingen geeft. Namelijk n. Daarna is er altijd minstens 1 deling.
Al deze getallen zijn deelbaar door 3 en oneven. Daardoor kunnen ze niet worden bereikt met een vermenigvuldiging. Ook de veelvouden zijn deelbaar door 3 en dus onbereikbaar voor vermenigvuldiging. Het getal y=3x+1 is uiteraard altijd een getal deelbaar door 3 + 1.

Kijken in 2-machten kan de doorbraak zijn inderdaad. Ik moet en wil die kant op. Proberen aan te tonen dat een combinatie van 2-machten altijd noodzakelijk in neerwaartse richting gaat. Ik heb al een idee maar ik moet er nog aan rekenen Het kan loos alarm zijn en alleen maar al gevonden regelmatigheden onderbouwen.

[Xilvo]

Kijken in 2-machten kan de doorbraak zijn inderdaad.

Dat is zeker geen slecht idee maar wel heel voor de hand liggend. En daarom vrijwel zeker al veel vaker geprobeerd.

[HansH]

3 is dan ook niet gelijk aan 2^2 + 2^1

klopt dat is 6 dus 1 bit te veel naar links. 3 is gelijk aan 2^1 + 2^0.
probeer aub even mijn gedachten te volgen ipv af te rekenen op rekengfoutjes. anders komen we per definitie al geen stap verder.

[HansH]

[En daarom vrijwel zeker al veel vaker geprobeerd.

kan, maar dat is dan weer een open deur opmerking. laten we in plaats daarvan dan liever die probeersels proberen op te sporen en kijken of je daar verder mee komt.

[HansH]

Kijken in 2-machten kan de doorbraak zijn inderdaad. Ik moet en wil die kant op. Proberen aan te tonen dat een combinatie van 2-machten altijd noodzakelijk in neerwaartse richting gaat. Ik heb al een idee maar ik moet er nog aan rekenen Het kan loos alarm zijn en alleen maar al gevonden regelmatigheden onderbouwen.

het geeft in ieder geval een grotere kans om tot een redenatie te komen dan alleen te concluderen dat dat vast al geprobeerd is en dus vast wel tot niets heeft geleid. Dus ga er zeker mee door ben benieuwd naar de redenatie die daaruit volgt.

[Marko]

3 is dan ook niet gelijk aan 2^2 + 2^1

klopt dat is 6 dus 1 bit te veel naar links. 3 is gelijk aan 2^1 + 2^0.
probeer aub even mijn gedachten te volgen ipv af te rekenen op rekengfoutjes. anders komen we per definitie al geen stap verder.

Je gedachtengang is niet te volgen als je beschrijving ervan vol staat met rekenfouten. Het is niet eens duidelijk of de gedachtengang wel klopt, omdat je dingen illustreert aan de hand van al dan niet fout berekende getallen. En zo kom je inderdaad per definitie geen stap verder.

Lees gewoon eerst je bericht door voor je hem plaatst, en wacht dan af wat voor inhoudelijk commentaar er komt.

[HansH]

bv binair 100101101 =301dec is oneven dus krijg je daarna
01001011010 (= x 2^1=alles 1 bit naar links)=602 plus
10010110100 (= x 2^2= alles 2 bits naar links)=1204 plus 1
00000000001 =
11100001111 (=1807)

Hier gaat volgens mij iets verkeerd.
301 is oneven dus kom je op 3 x 301+1=904 (1110001000)

moet dus zijn:
bv binair 1 0010 1101 =301dec is oneven dus krijg je daarna
0010 0101 1010 (= x 2^1=alles 1 bit naar links)=602 plus
0001 0010 1101 (= 301 oorspronkelijke getal)=301 plus 1
0000 0000 0001 =
0011 1000 1000 (=904)
het gaat dus om de vraag of je met deze procedure kunt verklaren als je dat herhaald doet dat je dan eindigt in een reeks enen met daaromheen alleen maar nullen.