Collatz conjecture of 3x+1 probleem

[Nesciyolo]

Sinds ik de afgelopen weken weer terug ben gekomen op dit forum heb ik een nieuwe slechte gewoonte opgevat. Namelijk het kijken naar onderhoudende video's over wiskunde op youtube.
Zo kwam ik deze video over de Collatz conjecture of het 3x+1 probleem tegen. Het probleem kort samengevat: begin met een willekeurig getal te kiezen en bewerk dat bij herhaling op maar 2 manieren:. Als het getal even is deel je het door 2, is het getal oneven, vermenigvuldig het met 3 en tel 1 op.
Dus:
kies een getal x en bewerk:
y = x/2 of y = 3x+1 al naar gelang even of oneven.
Als je dat gedaan heb, ga verder met dezelfde bewerking met het getal y.
bijvoorbeeld je begint met 7
7x3+1 = 22
22/2 = 11
11X3+1 = 34
34/2 = 17
17X3+1 = 52
52/2 = 26
26/2 = 13
13x3+1 = 40
40/2 = 20
20/2=10
10/2 = 5
5x3+1 = 16
16/2 = 8
8/2 = 4
4/2 = 2
2/2 = 1

Nu wordt in de video gezegd dat het bewijs nog niet geleverd is dat dit voor alle getallen geldt. Wel zijn alle getallen t/m 2^68 geprobeerd en ze kwamen allemaal op 1 uit.
Het vermoeden is dus dat dit voor alle getallen moet gelden.
Ik denk dat het niet fair is om aan jullie te vragen om het te bewijzen. Maar ik heb wel een gedachte. Ik zou het een vangnet methode of een spinnenweb methode willen noemen. Een manier om tot een uitzondering te komen of een bewijs dat er geen uitzonderingen zijn zou kunnen zijn dat je aantoont dat er een vangnet van getallen is dat zo groot is dat het alle getallen moet vangen of dat ergens een gat heeft waardoor sommige getallen niet worden gevangen.
Het is een vangnet of spinnenweb omdat je ermee willekeurige reeksen "vangt" zodra ze één van de bekende waardes bereiken. Wat dan zou moeten gebeuren is bewijzen dat dat net boven een bepaalde waarde geen gaten meer kan hebben of dat er juist gaten moeten zijn.

Dat werkt zo:
Eigenlijk gewoon van achter af terugrekenen.
De laatste reeks van delingen door 2 loopt altijd door de welbekende reeks van 2-machten: 2^n met n∈{0,1,2,3...∞}
Om daar te komen zal de laatste oneven bewerking een getal zijn van een van de 2-machten verminderd met 1 en gedeeld door 3
bijvoorbeeld: 2^4=16. Het oneven getal dat daar op uitkomt is 5 (5x3+1=16). Berekend: (16-1)/3=5
Elk van de oneven getallen die op die manier de 2-macht kunnen bereiken kunnen zelf ook maar op een beperkt aantal manieren bereikt worden. 5 bijvoorbeeld door te delen door 2 (10/2 = 5 ; 20/2 = 10 etc.

Het vangnet breidt zich dus uit naar alle getallen 5x2^n.
Een aantal van die getallen kan ook vanuit een oneven getal bereikt worden: 10 (3x3+1), 40 (3x13+1), 160 (3x53+1) enz.
Op dezelfde manier worden ook 3, 13, 53 vermenigvuldigd met een 2-macht deel van het vangnet.

Ook 2^6 =64 kan bereikt worden met het oneven getal 21 (3x21+1=64). Ook 21x2^n kan dus deel van het vangnet worden.

In principe hoeft het alleen voor alle oneven getallen bewezen te worden. Alle even getallen worden altijd gedeeld en komen altijd uit op een veel lager oneven getal.

Wat denken jullie? Zou deze werkwijze ergens toe kunnen leiden?

[Math-E-Mad-X]

Wat denken jullie? Zou deze werkwijze ergens toe kunnen leiden?

Dit zou wellicht het begin van een bewijs kunnen zijn, maar... iedere serieuze wiskundige die zich hier mee bezig heeft gehouden zal deze gedachtes van jou allang zelf gehad hebben. Ik denk dus helaas niet dat jou ideeën iemand verder op weg zullen helpen.

[HansH]

Dit zou wellicht het begin van een bewijs kunnen zijn, maar... iedere serieuze wiskundige die zich hier mee bezig heeft gehouden zal deze gedachtes van jou allang zelf gehad hebben. Ik denk dus helaas niet dat jou ideeën iemand verder op weg zullen helpen.

zo kun je alle redenaties om zeep helpen.
https://nl.wikipedia.org/wiki/Dooddoener_(stijlfiguur)

[Xilvo]

zo kun je alle redenaties om zeep helpen.

De praktijk toont aan dat Math-E-Mad-X gelijk heeft. Op gebieden waar het laaghangende fruit al lang geleden geplukt is, is de kans dat een amateur iets aantoont wat vele professionals eerder niet lukte nihil.

[HansH]

zo kun je alle redenaties om zeep helpen.

De praktijk toont aan dat Math-E-Mad-X gelijk heeft. Op gebieden waar het laaghangende fruit al lang geleden geplukt is, is de kans dat een amateur iets aantoont wat vele professionals eerder niet lukte nihil.

Punt is dat dat aannames zijn en vermoedens. Daar schiet niemend op het forum veel mee op met zo'n open deur. Het zou meer helpen om er wat energie in te steken en een overzicht te geven van wat er dan al aan bewijsvorming gedaan is.

[Xilvo]

Het zou meer helpen om er wat energie in te steken en een overzicht te geven van wat er dan al aan bewijsvorming gedaan is.

Ga je gang, als je denkt dat dat nuttig is.

[HansH]

Ga je gang, als je denkt dat dat nuttig is.

Ik ben niet de specialist en heb die constatering helaas al een keer teveel meegemaakt op het forum. Het is naar mijn idee dus wel nuttig, maar logischer als mensen die meer gespecialiseerd zijn dat dan even uitzoeken en posten.
zeker gezien deze opmerking voel ik me niet echt geroepen om er energie in se steken: 'iedere serieuze wiskundige die zich hier mee bezig heeft gehouden zal deze gedachtes van jou allang zelf gehad hebben. Ik denk dus helaas niet dat jou ideeën iemand verder op weg zullen helpen.'

[Xilvo]

Dan zul je inderdaad moeten wachten tot er iemand is die het kan, het nut ervan inziet en er tijd en moeite in wil steken.

[HansH]

Dan zul je inderdaad moeten wachten tot er iemand is die het kan, het nut ervan inziet en er tijd en moeite in wil steken.

Of de bijdragen van alle forumleden op waarde weten te schatten en zo stimuleren dat alle leden meedenken in oplossingen en in hun bijdragen gewaardeerd voelen. Misschien levert dat wel verrassende resultaten.

[Xilvo]

Dan zul je inderdaad moeten wachten tot er iemand is die het kan, het nut ervan inziet en er tijd en moeite in wil steken.

Of de bijdragen van alle forumleden op waarde weten te schatten en zo stimuleren dat alle leden meedenken in oplossingen en in hun bijdragen gewaardeerd voelen. Misschien levert dat wel verrassende resultaten.

Het één sluit het andere niet uit. Maar of de gebruiker, die een overzicht wil plaatsen van wat er al aan bewijsvorming gedaan is, alle forumleden op waarde weet te schatten zal je aan die hypothetische gebruiker zelf moeten vragen.

[wnvl1]

Jeffrey Lagarias heeft al een overzicht gemaakt voor de forumleden van pogingen om de Collatz hypothese te bewijzen.

https://arxiv.org/pdf/2111.02635.pdf

Als ik zou kunnen kiezen, dan zou ik liever een bewijs vinden voor de Riemann hypothese of dat openstaand Navier Stokes probleem.

[Math-E-Mad-X]

Dit zou wellicht het begin van een bewijs kunnen zijn, maar... iedere serieuze wiskundige die zich hier mee bezig heeft gehouden zal deze gedachtes van jou allang zelf gehad hebben. Ik denk dus helaas niet dat jou ideeën iemand verder op weg zullen helpen.

zo kun je alle redenaties om zeep helpen.
https://nl.wikipedia.org/wiki/Dooddoener_(stijlfiguur)

Dat is niet helemaal hetzelfde. Ik bedoel niet te zeggen: "er is vast wel iemand geweest die er al aan gedacht heeft", want dat kun je inderdaad overal wel tegen zeggen.

Wat ik wel bedoelde was: "ik weet 100% zeker dat men hier al aan gedacht heeft, want dit is simpelweg de meest logische gedachtegang die iedere wiskundige (inclusief mijzelf) als eerste zou volgen".

Het is alsof je als amateur tegen een professionele detective zegt, "heb je er al aan gedacht dat de ex van het slachtoffer de dader zou kunnen zijn?" Waarop de detective bij zichzelf denkt: "ja natuurlijk, dat was gelijk mijn eerste verdachte".

[Nesciyolo]

Kom op mensen relax. Ik til er ook niet heel zwaar aan. Ik wordt geïnspireerd door zo'n video en denk er dan wat over na maar dat maakt het op zich niet belangrijk. Ik zag in die oplossingsmethode vooral een hoop werk. Zoveel dat ik er ook niet veel voor voel om eraan te beginnen. Ook niet omdat men al heeft laten zien dat het werkt voor alle getallen tot 2^68. Dat is een heel hoog getal.
Dat net op grote schaal uitbreiden zou denk ik bijna net zoveel werk zijn als het gewoon voor alle getallen proberen.
In de video werd al aangestipt dat iemand voor een aantal getallen bewezen had dat ze in elk geval tot een uitkomst kwamen die lager was dan het begingetal. Ik denk dat er meer te bereiken valt in die richting. Als elk getal altijd op enig moment naar een lager getal leidt dan moet elk getal ook uiteindelijk op 1 uitkomen.

Ik denk dat Xilvo gelijk heeft dat ik met mijn wiskundeniveau dit probleem niet op kan lossen.

Soms ziet een leek het beter omdat hij onbevangen kijkt en hem of haar iets opvalt dat de wiskundigen over het hoofd zien. Bijvoorbeeld omdat ze te ingewikkeld denken.
Zie bijvoorbeeld de wijzers van de klok thread. Er kwamen allerlei mooie wiskundige principes naar voren maar niemand realiseerde zich kennelijk dat de grote en de kleine wijzer niet 12x maar 11x per 12 uur overlappen. Daardoor zag niemand in dat het eigenlijk een heel eenvoudig rekenkundig probleem was.

Ik persoonlijk zie deze Collatz conjecture eigenlijk meer als een aardig puzzeltje dan als een serieus probleem. 3x+1 bij oneven en delen door 2 bij even lijkt mij eigenlijk een tamelijk arbitraire set. Het had misschien net zo goed 5x+3 kunnen zijn of 7x-5. Ik noem maar wat. Leuk als tijdverdrijf maar totdat iemand ergens deze combinatie in een relevante situatie tegenkomt niet meer dan dat.

[Xilvo]

Dat net op grote schaal uitbreiden zou denk ik bijna net zoveel werk zijn als het gewoon voor alle getallen proberen.

Ik denk dat je iets anders bedoelt dan wat je schrijft. Alle getallen uitproberen is natuurlijk onmogelijk

Ik denk dat Xilvo gelijk heeft dat ik met mijn wiskundeniveau dit probleem niet op kan lossen.

Waarschijnlijk niemand op WSF, hoewel er enkele goede wiskundigen rondlopen. Als het wiskundigen als Paul Erdős al niet lukte...

[Nesciyolo]

Het aardige van een probleem dat je niet op kan lossen is dat je er heel veel van leert als je het toch probeert.
ik denk niet dat ik heel ver kom maar ik heb wel een paar dingetjes gevonden die anderen misschien verder helpen.
We kunnen gebruik maken van het feit dat alle getallen tot 2^68 al zijn geprobeerd.

Ik heb het paper van Lagarias doorgelezen en het viel me op dat er weinig concrete poging gedaan wordt om dichter bij een oplossing te komen. Er wordt getoond hoe het probleem maar een voorbeeld is van grotere klasses van problemen. Heel interessant allemaal, maar dat leidt ons niet op de weg naar de oplossing als we die andere problemen ook niet op kunnen lossen. Sterker nog. Oplossen zal misschien wel moeilijker worden omdat we geconfronteerd kunnen worden met uitzonderingen op andere varianten die voor deze variant helemaal niet van toepassing zijn.

Als (ex)programmeur weet ik dat je om een algoritme goed en efficiënt vorm te geven moet proberen te veralgemeniseren. Als je dat slim doet kan je je code op verschillende plekken handig hergebruiken. Dat scheelt werk en vermindert de kans op fouten. Ik weet ook dat je moet specificeren. Daarmee bedoel ik dat je het probleem moet onderverdelen in stapjes die je één voor één kan zetten zodat je uiteindelijk je doel bereikt. Dat mis ik een beetje in het verhaal van Lagarias. Niet verwonderlijk denk ik, want die stappen zijn onderdeel van een concrete oplossing. En die heeft hij in dit paper gewoon niet behandeld.

Zoals in de al genoemde Veritasium video uitgelegd kunnen we het Collatz probleem oplossen door te bewijzen dat alle reeksen op enig moment een getal bereiken dat lager is dan het begingetal. Daarmee laten we zien dat de sequence waarin we zitten aansluit op een andere sequence die naar 1 toegaat.
Ik denk eigenlijk dat dat voldoende is. Het getal wat we willen bereiken verder naar beneden brengen is voor een concrete oplossing van het probleem zinloos. Het aantal gevallen waarvoor het bewezen kan worden omhoog brengen is zinvoller.

Het is extreem eenvoudig om een programma te schrijven dat 1 voor 1 alle getallen van 1 tot sint juttemis gaat nalopen en proberen. Het nadeel van zo'n programma is dat je niet echt ziet wat er gebeurt en dus ook niet zomaar alle verbanden ziet. En verbanden zijn er wel degelijk. Een heleboel zelfs. Lagarias sprak van volledige chaos en van waarschijnlijkheden. Er is helemaal niet zoveel chaos. Er is zelfs heel veel orde. Zoveel orde zellfs dat er uiteindelijk (bijna?) geen gaten zijn.
De zoektocht naar uitzonderingen lijkt misschien een beetje op de zoektocht naar priemgetallen. De priemgetallen zijn niet heel ordelijk verdeeld. Maar er is wel een hele duidelijke en veelzijdige orde van getallen die geen priemgetal zijn.
In principe alle rekentafels van priemgetallen van n * priemgetal met n = (2,3,4,...,∞) samen vormen het netwerk van de getallen die geen priemgetal zijn. De gaten daartussen zijn wel priemgetallen.

In het 3x+1 probleem werkt het ook een beetje zo. Om het probleem op te lossen hoeven we niet te proberen alle getallen naar 1 te brengen. We hoeven alleen maar te kijken of ze op enig moment leiden tot een lager getal dan het begingetal.
Dat betekent dat we alle even getallen kunnen overslaan. Die worden eerst door 2 gedeeld en komen dus direct op een lager getal uit. Maar er zijn nog veel meer getallen die we niet meer hoeven te beschouwen.

=ALS(J6>1;ALS(IS.ONEVEN(J6);3*J6+1;J6/2);0)
Een spreadsheet maken dat al het rekenwerk eenvoudig en overzichtelijk voor je doet is heel eenvoudig. Met een statement zoals de regel hierboven heb ik een sheet gemaakt waarin ik alle gevallen tot 123 overzichtelijk op een rijtje zet.
Toen ik dat deed viel me op dat er een grote regelmatigheid is in het aantal stappen dat leidt naar een getal dat lager is dan de beginwaarde. 5, 9, 13, 17, 21 enz. halen dat altijd in 3 stappen. Gaat dat tot in het oneindige door?
Ja. Ik zal uitleggen waarom.

Het begint met het getal 1. Doen we even net of dat nog niet op 1 is:
3x+1 = 3x1+1 = 4
4/2 = 2
2/2 = 1

Ik heb mij afgevraagd of ik iets bij 1 kan optellen dat die flow niet verbreekt. Als we 1 op a stellen dan kunnen we dat getal op b stellen.

x=a+b
3(a+b)+1 = 3a+1+3b
(a+b)/2 = a/2+b/2
Het getal moet dus 2x door 2 gedeeld kunnen worden, ook als ik het eerst met een ander getal vermenigvuldig. Dat getal is 2^2 = 4 en ook nog elk veelvoud van 4

vul ik dus voor x = 1+4n in, dan krijgen we:
3(1+4n)+1= 4+4n
(4+4n)/2=2+2n
(2+2n)/2=1+n

(1+n)<(1+4n). Dus voor alle getallen n ∈ (1,2,3,...,∞) geldt dat in hooguit 3 stappen een lager getal bereikt wordt.
Dat is de helft van alle oneven getallen. Dat levert dus een hoop tijdwinst op in een brute force poging.

We kunnen hetzelfde trucje met elk bekend getal doen. Helaas levert het niet altijd zoveel op. De minimum waarde van een 2-macht die we op kunnen tellen is 2^a, waarbij a het aantal keren is dat het basisgetal door 2 gedeeld moet worden om een getal te bereiken lager dan dat basisgetal. Het gaat alleen om het aantal delingen. Het aantal keren vermenigvuldigen maakt niet uit.
Het getal 3 bijvoorbeeld:

3 -> 10, 5, 16, 8, 4, 2

moet 4x door 2 gedeeld worden. We kunnen daar dus alleen veilig n(2^4) bij optellen. De sequence herhaalt zich dus alleen op 19, 35, 51, 67 enz. maar gaat net zoals de 1 serie tot in het oneindige door. Het geldt dus ook voor 15955 (=3 + 997(2^4)).
We kunnen meer gevallen elimineren met bijvoorbeeld 11 en 23 (+n(2^5)).
Er blijven problematische gaten.
27 bijvoorbeeld kan pas in een reeks passen met n(2^59) en 31 met n(2^56). 47 en 63 met n(2^54). Het lijkt erop dat de langste reeksen voorkomen vlak voor 2-machten of veelvouden daarvan.

Het getal 97 dat in de Veritasium video werd genoemd heeft wel 118 stappen nodig om 1 te bereiken maar is in mijn werkwijze niet bijzonder problematisch. Het bereikt na 3 stappen al een getal lager dan 97.

Ik weet niet of ik een spreadsheet kan bijvoegen maar ik zal het proberen.

20230531 3x+1 01

(670 KiB) 77 keer gedownload

Het is een ruwe versie voor eigen gebruik. Ik heb dus nergens commentaar gegeven. Er staan overtollige dingen in die onjuist zijn maar die ik zelf gewoon oversla. Ik zou de statements aan kunnen passen maar dat vind ik teveel werk.