Collatz conjecture of 3x+1 probleem

[Nesciyolo]

Een korte update.
Ik ben nog steeds met de hierboven genoemde methode bezig om te bepalen hoeveel keer gedeeld wordt door 2 voordat de sequence onder het basisgetal zakt.

Ik heb geturfd welke reeksen van x = a+n(2^b) bestaan t/m het basisgetal 512 (2^9)
Ik heb wat opmerkelijke dingen gezien.

• 2^3, 2^6 3n 2^9 komen niet voor. Als dat t/m 2^9 geldt dan is dat ook zo voor hogere getallen.
• 2^12, 2^15, 2^18, 2^21 en zelfs 2^24 heb ik al wel gevonden. Het ligt dus niet aan het veelvoud van 3 in de machten.
• 2^8 komt 6x voor. Dat vind ik best veel
• 2^10 heb ik ook al 4x gevonden

Ik heb handmatig geturfd. De gegevens zijn dus onbetrouwbaar en misschien onvolledig.

Met alleen een spreadsheet kom ik hier niet verder. Ik weet niet of ik de moeite wil nemen om hier een programma voor te maken.

Als ik dat doe zal ik waarschijnlijk de volgende methode gebruiken:
Ik zal werken per 2-macht. Dus beginnen bij 2, dan naar 4, naar 8, naar 16 enzovoort.
Iedere keer zal ik per getal (vanaf 1) het aantal delingen naar 1 of naar een getal lager dan het basisgetal tellen zoals in de vorige post en in mijn spreadsheet beschreven. Als ik de 2-macht berekeningen gedaan heb dan ga ik kijken welke getallen een aantal delingen <= de exponent van de 2-macht die ik op dat moment bekijk heeft. Die getallen schrap ik uit de lijst en beschouw ik als bewezen reeksen. De andere getallen dupliceer ik voor de volgende fase vermeerderd met de 2-macht.

Dus stel ik ga van 2^4 (16) naar 2^5 (32) werken dan bekijk ik het aantal delingen nodig zoals hierboven beschreven. Als dat 4 of minder is dan schrap ik die getallen. Is het meer dan dupliceer ik het getal door er 16 bij op te tellen. Het getal 15 bijvoorbeeld met 7 delingen dupliceer ik dan naar 15+16 = 31.
Als ik dan bij de stap naar 2^6 beslis dat ik ze allebei moet houden zal ik ze allebei dupliceren naar 15+32 = 47 en 31+32=63.
Op die manier zal ik als ik het goed doe voor elke reeks maar 1x hoeven rekenen en als ik geluk heb steeds minder getallen overhouden.
Ik denk dat ik een log moet bijhouden van getallen die ik berekend heb en welke reeks eruit voortkomt voor latere bewijsvoering en toetsing.
Uiteraard zal ik dat niet handmatig doen maar het door het programma laten uitvoeren. Per stap zal ik moeten bijhouden welke getallen geëlimineerd worden en welke overblijven.
Even getallen zal ik overslaan.

Ik zal moeten kijken hoeveel rekenkracht dit kost. Misschien wordt het te moeizaam in de buurt van de 2^40 of 2^50. Het zal er vanaf hangen hoe snel getallen geëlimineerd kunnen worden.

Wat denken jullie. Zou dat kunnen werken?

[wnvl1]

Ik denk dat je je verhaal op een meer formele wiskundige manier moet neerschrijven om het gemakkelijker begrijpbaar te maken voor de lezers van het forum. Het is typisch voor amateurwiskundigen en natuurkundigen dat ze de dingen te weinig formeel opschrijven.

Ik vermoed dat je op zoek bent naar een bewijs door inductie. Je gaat aantonen dat als je veronderstelling geldt tot 2^(x) dat ze dan ook geldt tot 2^(x+1). Gewoon aantonen dat de veronderstelling geldt tot 2^x met x een groot getal lijkt me niet zo nuttig.

[wnvl1]

Deze paper van Terrence Tao (een van de meest populaire wiskundigen vandaag de dag) is mogelijk ook interessant.
De eerste pagina's zijn wel begrijpbaar en geven een idee van zijn aanpak.

https://arxiv.org/pdf/1909.03562.pdf

[Nesciyolo]

Ik denk dat je je verhaal op een meer formele wiskundige manier moet neerschrijven om het gemakkelijker begrijpbaar te maken voor de lezers van het forum. Het is typisch voor amateurwiskundigen en natuurkundigen dat ze de dingen te weinig formeel opschrijven.

Ik vermoed dat je op zoek bent naar een bewijs door inductie. Je gaat aantonen dat als je veronderstelling geldt tot 2^(x) dat ze dan ook geldt tot 2^(x+1). Gewoon aantonen dat de veronderstelling geldt tot 2^x met x een groot getal lijkt me niet zo nuttig.

Het is niet helemaal zo. Ik denk wel dat ik niet veel verder zal komen. Zelfs al zou mijn methode snellere resultaten opleveren dan een brute force methode die alleen maar voor elk getal tot het einde doorrekent. Ik denk niet dat ik op een bepaald moment met een schone tafel zal zitten. Dus het zal een oneindig zoeken worden naar die ene uitzondering die er waarschijnlijk helemaal niet is.

Zo'n doorrekenverhaal is leuk voor een computer die op een universiteit ergens in een hoekje staat te pruttelen. Maar bij mij thuis zal ik er waarschijnlijk niets anders uithalen dan lange rijen getallen.

Ik denk inderdaad dat ik er niet mee door moet gaan. Het zal geen bewijs leveren en ik zal er ook niet meer door gaan begrijpen.

Daarnaast vind ik het eigenlijk helemaal niet zo'n interessant probleem. Meer een spelletje. Dus het moet wel leuk blijven.

[Nesciyolo]

Ik vermoed dat je op zoek bent naar een bewijs door inductie. Je gaat aantonen dat als je veronderstelling geldt tot 2^(x) dat ze dan ook geldt tot 2^(x+1). Gewoon aantonen dat de veronderstelling geldt tot 2^x met x een groot getal lijkt me niet zo nuttig.

Ik denk inderdaad dat het inductie is in verschillende opzichten. Er is inderdaad een dominosteenwerking. Door te stoppen bij het eerste lagere getal dan de basis haak ik aan op een ander getal waarvoor ik dat ook zal moeten doen. Ook gebruik ik inductie door reeksen te definiëren die ik koppel aan de basiswaardes. Ik had al een beginnetje gemaakt door te stellen dat voor alle x = (1 + n(2^2)) geldt dat ze in 3 stappen naar een lager getal bewegen. Ook andere reeksen had ik zo al gedefinieerd.
Helaas zal een computer zo met veel noeste arbeid voor een heleboel reeksen steeds hetzelfde trucje uit kunnen halen maar ik ben bang dat er geen eindig aantal reeksen is dus dat ik net als anderen nooit verder zal komen dan "voor bijna alle getallen" geldt het.

Het zal dus mogelijk zijn om voor een indrukwekkende hoeveelheid individuele gevallen te bepalen dat het klopt, maar niet voor alle gevallen.
Tenzij er een eindig, niet al te groot maximum aantal stappen is. Als bijvoorbeeld de 59 delingen voor x = (27 + n(2^59)) niet overtroffen wordt. Jammer genoeg blijkt na kijken naar de eerste 1024 gevallen dat x = (703 + n(2^81)) al 81 delingen nodig heeft. Het voorkomen van zulke extremen lijkt zeldzaam (steeds zeldzamer?) en de gaten die erdoor ontstaan worden denk ik in veel gevallen opgevuld door lagere waardes maar een waterdicht bewijs zal er denk ik nooit komen op deze manier.

[wnvl1]

Bij de laatste stelling van Fermat zijn ze ook begonnen met het te bewijzen voor verschillende categorieën tot er op het einde nog een lastige categorie overbleef. Dat was een mooi verhaal met toepassingen van stukken wiskunde zoals die modulair forms waar je het niet zou verwachten. Wie weet leidt dit ook ooit tot zo een verhaal.

[HansH]

ik vraag me af of dit ooit te bewijzen valt. Ik vergelijk het een beetje met een kamer gevuld met lucht met een gaatje. alle lucht deeltjes botsen voortdurend maar als je maar lang genoeg wacht dan komt elk deeltje vanzelf en keer uit dat gaatje. Maar om te bewijzen wanneer een deeltje eruit komt lijkt onmogelijk. we hebben een set wiskunderegels en manieren van aanpak waarmee je een aantal problemen kunt oplossen, maar sommige dingen zijn gewoon niet oplosbaar. zoals be bepaalde integralen alleen numeriek oplosbaar zijn.

[Xilvo]

Er zijn volgens mij (als niet-wiskundige) vier mogelijkheden.
1. Het is niet waar en dat is aan te tonen, bijvoorbeeld doordat je uitgaande van een begingetal in een lus terecht komt en zo nooit op 1 komt.
2. Het is niet waar maar er is geen tegenvoorbeeld te vinden. Bijvoorbeeld doordat je vanuit een begingetal naar steeds groter getallen komt maar zonder in een lus terecht te komen. Dan kan een computer oneindig lang op die reeks malen zonder tot een conclusie te komen.
3. Het is waar en bewijsbaar. Dan is het wachten op iemand die dat bewijs vindt (misschien is dat t.z.t. wel AI).
3. Het is waar maar onbewijsbaar.

[Math-E-Mad-X]

Er zijn volgens mij (als niet-wiskundige) vier mogelijkheden.

Bijna goed. Er zijn inderdaad vier mogelijkheden, maar deze klopt niet helemaal:

2. Het is niet waar maar er is geen tegenvoorbeeld te vinden.

In plaats hiervan had je moeten schrijven: "Het is niet waar, maar het is onmogelijk te bewijzen dat het niet waar is".

Dat is een sterkere uitspraak, want het is in principe ook mogelijk om te bewijzen dat er een tegenvoorbeeld bestaat, zonder dat je dat tegenvoorbeeld kan vinden. Oftewel, het zou kunnen dat er een tegenvoorbeeld bestaat, en dat je kunt bewijzen dat er eentje bestaat, maar het bewijs geeft niet aan welk nummer dan een tegenvoorbeeld zou zijn, en zelfs als ik jou dat nummer zou geven, dan nog kon je onmogelijk aantonen dat dat specifieke nummer inderdaad een tegenvoorbeeld is.

[Xilvo]

@Math-E-Mad-X
Duidelijk. Dank!

[wnvl1]

Met punt 2 wordt verwezen naar het is een 'onbeslisbaar' probleem. Maar is die 'het is niet waar' er dan niet te veel aan? Een onbeslisbaar probleem is een ​​beslissingsprobleem waarvoor het onmogelijk is gebleken om een ​​algoritme te construeren dat altijd leidt tot een correct ja-of-nee-antwoord.

[WillemB]

De effectiviteit van 3x+1 is klein, omdat daarna altijd een even getal uitkomt, die door 2 gedeeld wordt.

Dus uiteindelijk wordt elk oneven getal na bewerking slechts 1,5 x +0,5 groter,
Daar instegen wordt bij elk even getal door 2 gedeeld, dat weegt zwaarder dan maal 1,5

Als voorbeeld als acht keer oneven voorkomt geeft dat een vergroting van 25 maal
terwijl als even acht maal voorkomt dat een verkleining geeft van 256 maal.

De deling door 2 weegt zwaarder, dus zal het eind nooit meer zijn dan het begin,
statistisch zou dat wellicht te bewijzen zijn.

Aangezien de reeks door gaat net zolang tot er 1 uitkomt, gaat de deling het altijd winnen. 1,5 tegen 2
mits er meer oneven als even getallen zouden zijn.

[Nesciyolo]

Aangezien de reeks door gaat net zolang tot er 1 uitkomt, gaat de deling het altijd winnen. 1,5 tegen 2
mits er meer oneven als even getallen zouden zijn.

Waarschijnlijk wel. Maar kan je het ook bewijzen? Als je een muntje opgooit (waar niet mee geknoeid is) is er een hele kleine kans dat je tot het oneindige alleen maar kop gooit. Je kan daarom nooit op voorhand uitsluiten dat er een geval (reeks van gevallen) is die niet naar 1 gaat. Ofwel hij gaat oneindig door naar steeds hogere getallen of hij komt in een loop terecht.

Een brute force methode die alle getallen probeert (en die al op 2^68 gekomen is) zoekt naar zo'n geval. Hij zal dus de conjecture nooit kunnen bewijzen. Alleen maar kunnen weerleggen.

Een voordeel van de methode die ik hierboven beschrijf zou zijn (naast dat hij veel sneller is) dat er een mogelijkheid denkbaar is dat bewezen wordt dat er geen uitzonderingen kunnen zijn.

De verdeling van het aantal pogingen lijkt op een randomverdeling. Als je ze allemaal op een rijtje zet komt er een grafiek in de vorm van een normaalverdeling uit. Maar dat kan bedrieglijk zijn. Er zit misschien wel een duidelijk niet random structuur achter die we nog niet gezien hebben.
Bedenk bijvoorbeeld dat ik met deze methode elk getal aanhaak aan een ander getal dat lager is. Misschien zijn er wel structuren van aangehaakte getallen die zich van achteraf laten zien als een boom die zich vertakt. De meeste getallen vinden een vrij korte weg naar 1 maar anderen hebben de "pech" dat ze aanhaken op een getal dat iets hoger in de boomstructuur zit waardoor er een langere weg ontstaat.

Er zijn bijvoorbeeld opvallende pieken in de verdeling. Zo heb ik gevonden dat 80 of 81 delingen vaker voorkomen terwijl ik aantallen daar in de buurt niet zie.
Het getal 704 lijkt op een of andere manier belangrijk. Vanaf het getal 703 (-1?) 704 of een veelvoud van 704 op te tellen leidt tot een aantal gevallen waar 80 of meer delingen noodzakelijk zijn om tot een lager getal te komen:

703: 81 delingen
1407: 81 delingen
2111: 80 delingen
45055: 111 delingen

Tussen 81 en 111 heb ik 96 gezien maar niet veel andere. 15 delingen verschil. Toeval?
Ook als ik op andere manieren door de mogelijkheden blader lijk ik 80 en 81 vaker tegen te komen.

Let op: Ik heb niet systematisch gezocht en heb ook niet alles wat ik gezien heb precies gedocumenteerd. Algemene uitspraken die ik doe kunnen dus onjuist zijn.

[Xilvo]

Hier nog een 'geweldige' manier om een tegenvoorbeeld te vinden waarbij je in een lus terechtkomt en dus nooit op 1 uitkomt.
Het is kennelijk al geprobeerd tot 2⁶⁸=295E18. Of dat werkelijk met brute force is gebeurd betwijfel ik, een enkele computer zou dan iedere sceconde 1000 miljard mogelijkheden moeten uitproberen, 10 jaar lang. Maar misschien met veel slimmigheidjes en inzet van veel computers...

Hoe dan ook, het is een heel groot getal. \(3x+1\) verschilt dan nauwelijks van \(3x\).
Probeer een \(n\) en \(m\) te vinden zodat \(3^n\approx 2^m\).
Helemaal gelijk worden ze niet, het ene getal is altijd oneven, het andere even.
Maar je zou dan \(n\) keer \(3x+1\) kunnen doen en kijken of je weer terugkomt op het oorspronkelijke getal door \(m\) keer door twee te delen.
Natuurlijk kan je die twee operaties niet in willekeurige volgorde uitvoeren, ach, een kleinigheidje.

Wie het proberen wil mag, ongetwijfeld is ook dit al lang geleden bedacht en geprobeerd.

[Nesciyolo]

Als je een oneven getal met 3 vermeigvuldigt en er 1 bij optelt komt daar altijd een even getal uit. De volgende bewerking moet dus altijd een deling zijn. Je kan de vermenigvuldiging en daarop volgende deling daarom bij elkaar trekken en als 1 bewerking beschouwen.
Je krijgt dan y =(3x+1)/2= 1,5x+0,5
Voor de helft van alle oneven getallen komt uit deze bewerking een even getal en voor de helft een oneven getal. Zet je ze op een rijtje dan zie je dat ook. Na deze bewerking komt er uit voor:
1: 2-1-2 e-o-e
3: 5-8-4 o-e-e
5: 8-4-2 e-e-e
7: 11-17-26 o-o-e
9:14-7-11 e-o-o
11:17-26-13 o-e-o
o=oneven,
e=even
het patroon van (on)even uitkomsten voor basisgetallen 1, 3, 5, 7, 9, 11 enz is dus na de eerste bewerking::
e-o-e-o-e-o- enz
na de tweede bewerking:
o-e-e-o-o-e-e-o-o-e-e- enz
na de derde bewerking:
e-e-e-e-o-o-o-o-e-e-e-e-o-o-o-o- enz.
Opmerkelijk is dat het patroon minder duidelijk wordt na de 4e bewerking. Je zou misschien iets verwachten in de richting van o-o-o-o-o-o-o-o-e-e-e-e-e-e-e-e-o-o-o- enz maar dat is niet het geval Ondanks dat loopt het patroon wel door maar minder duidelijk. Er lijken zich vlechten af te splitsen.
Het patroon:
o-e-o-o-o-e-e-e-o-e-e-e-o-o-o-o enz lijkt niet zo regelmatig. Maar als we de stapgrootte tussen de basisgetallen van 2 naar 4 brengen dan krijgen we de patronen:
voor 1-5-9-13- enz
o-o-o-e-e-e-e-o-o-o-o-e-e-e-e- enz
en voor 3-7-11-15 enz:
e-o-e-e-o-e-o-o-e-o-e-e- enz.
Dat laatste ziet er nog niet regelmatig uit
Vergroten we de stap naar 8 en kijken we naar basisgetallen 3-11-19-27 enz dan zien we het patroon herstellen:
e-e-o-o-e-e-o-o- enz.
bekijken we dan de overige getallen (7-15-23-31-39 etc) dan zien we het patroon:
o-e-e-o-o-e-e-o-o-e-e- opdoemen.

Voor deze laatste reeks (7-15-23-31-39 etc) geldt na de 5e bewerking ook weer een keurig regelmatig:
e-e-e-e-o-o-o-o-e-e-e-e-o-o-o-o- enz.
Ook voor (5-13-21-29 etc) is er een regelmatig patroon:
e-e-e-e-o-o-o-o-e-e-e-e enz.
De basisgetalreeksen (1-9-17-25-33 etc.) en (3-11-19-27 enz) leveren juist de minder duidelijke (vermengde) patronen op die wel weer door het vergroten van de stappen op te schonen zijn.

De patronen van even en oneven uitkomsten na een aantal stappen hebben een heel duidelijk terugkerend patroon.
Bij stapgrootte 32 (2^5) bijvoorbeeld zien we bij basisgetallen 3-35-67-99-131 altijd het patroon van uitkomsten van de eerste 4 bewerkingen (per basisgetal):
o-e-e-e terugkomen. De uitkomst van de volgende bewerking is dan steeds afwisselend e-o-e-o-e- enz
bij basisgetallen (5,39,67,101 enz) is dat patroon altijd:
e-e-e-o
Daarna wisselt het af als
e-o-e-o-e-o etc.

Hoe groter de stapgrootte (als 2-macht) hoe langer de overeenkomende reeks even en oneven uitkomsten.

Hoe dan ook, het is een heel groot getal. \(3x+1\) verschilt dan nauwelijks van \(3x\).
Probeer een \(n\) en \(m\) te vinden zodat \(3^n\approx 2^m\).
Helemaal gelijk worden ze niet, het ene getal is altijd oneven, het andere even.
Maar je zou dan \(n\) keer \(3x+1\) kunnen doen en kijken of je weer terugkomt op het oorspronkelijke getal door \(m\) keer door twee te delen.
Natuurlijk kan je die twee operaties niet in willekeurige volgorde uitvoeren, ach, een kleinigheidje.

Wie het proberen wil mag, ongetwijfeld is ook dit al lang geleden bedacht en geprobeerd.

Het aardige is dat je \(3^n\div 2^m\) natuurlijk wel in willekeurige volgorde kan uitvoeren. Het probleem zit hem in de +1. Ook \(1*3^n\div 2^m\) kan je in willekeurige volgorde uitrekenen. Maar voor elke keer dat je een 1 extra toevoegt is het aantal keren dat het moet gebeuren anders.
Ook daarbij is een patroon: het aantal keren dat je 1 toevoegt is even groot als het aantal vermenigvuldigingen en het aantal keren dat je die 1-en dan vermenigvuldigt is ook een reeks. Voor n vermenigvuldigingen:

1*3^n-1 + 1*3^n-2 + 1*3^n-3 ... + 1*3^n-n
In de zoals hierboven omgeschreven bewerkingsvoortgang wordt dat dan:
0,5*1,5^n-1 + 0,5*1,5^n-2 + 0,5*1,5^n-3 ... + 0,5*1,5^n-n

Voor de delingen is er helaas verder geen regelmaat aan te geven.