Collatz conjecture of 3x+1 probleem

[Xilvo]

Hij heeft het over een verzameling oneven getallen, dus als k'=2m dan is m een geheel getal plus 1/2
En dan is k inderdaad 6m+1. Geen idee waarom je dat zo zou doen, maar goed. Verwarrend is het in ieder geval wel

Maar hij heeft het ook over k = 6m + 1 omdat hij hier getallen behandelt die rest 1 geven bij deling door 6. Dan moet m wél geheel zijn. Laten we maar concluderen dat z'n verhaal hier al ontspoord is

[HansH]

Misschien is deze auteur ook iemand die vindt dat anderen maar door de typ- en andere fouten heen moeten lezen omdat het immers om de gedachtengang gaat.

Andermans werk afkraken zonder zelf iets toe te voegen bedoel je?
omdat ik aanneem dat jouw opmerking refereert aan mijn eerdere opmerking.
heb je je al verdiept in het vervolg van van wat ik had laten zien? Dat geeft denk ik een betere onderbouwing van mijn gedachtengang. Verder krijgen we er allemaal niet voor betaald, dus je mag blij zijn dat mensen hun nek uitsteken toch?
de zaak positief benaderen en opbouwend discussieren heet dat volgens mij.

[wnvl1]

Je hebt volgens mij twee soorten van mensen. (1) mensen die plezier vinden in het zelf zoeken naar oplossingen van problemen (2) mensen die kicken op geniale oplossingen van anderen. Zelf behoor ik zonder twijfel tot de tweede categorie. In dat geval is dit soort van papers natuurlijk niet heel verrijkend, maar ik kan zeker begrip opbrengen voor mensen van de andere categorie.

[HansH]

Je hebt volgens mij twee soorten van mensen. (1) mensen die plezier vinden in het zelf zoeken naar oplossingen van problemen (2) mensen die kicken op geniale oplossingen van anderen. Zelf behoor ik zonder twijfel tot de tweede categorie. In dat geval is dit soort van papers natuurlijk niet heel verrijkend, maar ik kan zeker begrip opbrengen voor mensen van de andere categorie.

In mijn eigen vakgebied als ingenieur moet je beide eigenschappen hebben om niet in de valkuil te lopen om het wiel opnieuw uit te gaan vinden. Punt is alleen dat zoeken en uitpuzzelen van andermans oplossingen veel tijd en energie vraagt en vaak eindigt in het verstrikt raken in gebrek aan kennis of gebrek aan gave van de schrijver om iets zodanig op te schrijven dat het door anderen stap voor stap te volgen is. (dus het weglaten van essentiele tussen stappen die wel in het hoofd zitten van de schrijver, maar niet in het hoofd van de ontvanger waardoor die dan de draad kwijt raakt). Voordeel van het wiel opnieuw uitvinden is dat je het dan in ieder geval zelf goed snapt daarna.

[HansH]

Even terug naar de inhoud:
vanaf het moment dat je een macht van 2 bereikt is het zeker dat je daarna de eindsituatie gaat bereiken.
om aan te kunnen tonen dat je ooit eindigt op een macht van 2 moet je dus aantonen dat je dat altijd lukt vanuit elke beginsituatie.
Dus moet je snappen hoe steeds een volgende stap 3x+1 uit een vorige situatie ontstaat.
als ik kijk hoe een 1 op een geisoleerde plek zich ontwikkelt dan is dat bv alsvolgt:

som.gif (3.36 KiB) 665 keer bekeken

dus de 1 die op bit 0 stond vanwege het oneven zijn vertaalt zich naar een 1 op bit 2 samen met de 1 die er op bit 0 altijd bijkomt.
de 1 op bit 5 vertaalt zich naar een 1 op bit 5 en bit 6.
dat proces geldt dus voor elke 1 op een bepaalde bit positie.
daarnaast heb je nog het proces van 2 bits die elkaar beinvloeden en een carry opleveren.

ik denk dus dat je die processen verder moet analyseren en dan kijken of je daarmee kunt voorspellen of zich dat voortzet tot uiteindelijk een enkel bit=1 op positie n.

[HansH]

hier dezelfde situatie maar dan doorgetrokken tot er een macht van 2 ontstaat.
(helaas werkt het niet handig in Excel omdat de uitlijning niet naar rechts gebeurt)

[HansH]

alleen nu nog het begrip waarom je uiteindelijk op 16 uitkomt= 10000bin

[HansH]

Weer zo'n eigenaardigheid van Excel die niet te doorgronden is.
In mijn Engelse versie van Excel geeft
=BASE(43688;2)
als resultaat:
1010101010101000
terwijl
=DEC2BIN(43688)
ook jouw #NUM! error geeft.

In de Nederlandse versie zou het moeten lukken met
=BASIS(43688,2)
of iets wat hierop lijkt.

in office 365 werkt dit. helaas in de 2010 versie die ik nog heb draaien op mijn oude computer niet. die herkent het hele commando Base niet en ook geen Basis of iets dergelijks.

[wnvl1]

In de marge als aanmoediging. Soms kan een amateur wel eens een probleem oplossen waar toppers zoals Roger Penrose in dit geval niet in slaagden. Dit artikel stond vandaag (achter de betaalmuur) in De Standaard, daarom kan ik het hier niet helemaal zetten.

Eindelijk gevonden: dit is de eerste tegel zonder terugkerend patroon
Met zijn ‘hoed’ en ‘spook’ klaarde een Britse gepensioneerde een wiskundige klus waar zelfs Nobelprijswinnaars hun tanden op stuk beten. Voor het eerst kan een vlak bedekt worden met één figuur, zonder dat een patroon zich herhaalt.
Dries De Smet

Vrijdag 9 juni 2023 om 3.25 uur


Met één tegel kun je een eindeloos vlak vullen zonder terugkerend patroon. De tegel kreeg de naam ‘het spook’. courtesy of Dave Smith

Het zou nooit lukken, voorspelde de Chinees-Amerikaanse wiskundige en filosoof Hao Wang in 1961. Met een beperkte set van tegels kun je nooit een vlak helemaal bedekken zonder dat het patroon zich herhaalt.

Zijn eigen student Robert Berger gaf hem meteen lik op stuk: met een set van 20.426 verschillende tegels kon het wel. Met minder ook, toonde de Brit Roger Penrose, die in 2020 de Nobelprijs fysica kreeg voor zijn onderzoek naar zwarte gaten. Twee tegels (een vlieger en een pijl) volstaan.

Maar hoe hard Penrose en andere wiskundigen ook zochten: de heilige graal vonden ze niet. Dat is een ‘einstein’, één tegel waarmee je een vlak kan vullen zonder terugkerend patroon. Tot een Britse gepensioneerde zonder wiskundige achtergrond aan het puzzelen sloeg.

[Nesciyolo]

Als je met binaire getallen rekent dan is 3x+1 inderdaad makkelijker dan 1,5x+0,5. Maar voor analyse is dat laatste soms meer geschikt.

Ik vroeg me af hoeveel stappen ik kan doen voordat de grootte van het basisgetal belangrijk wordt.
ik neem een binair getal a en plaats daar nog 4 cijfers achter.ik krijg dan een getal a0000 bijvoorbeeld of 10000a bin.
Wat gebeurt er als ik dat getal ga bewerken en wat blijft er over als ik zover ben dat a van invloed wordt?
Het blijkt dat ik 4 stappen (1,5x+0,5 of x/2) kan doen zonder dat ik enige informatie over a nodig heb.

Om te bepalen wat er overblijft heb ik het berekend voor 10000a+0 t/m 10000a+1111 (alles binair)
Hieronder heb ik per getal de berekening gegeven. Ik schrijf het zonder verder commentaar als a0000 binair of a0 hexadecimaal. Daaronder staan berekeningen die je volledig binair moet interpreteren. Ik kijk ook naar even getallen, zodat het herhaalbaar wordt:

a0000 a0
10000a
10000a/10000=a

a0001 a1
10000a+1
(10000a+100000a+1+10+1)/10=(10000a+100000a+100)/10=1000a+10000a+10
1000a+10000a+10)/10= 100a+1000a+1
(100a+1000a+1000a+10000a+1+10+1)/10=(100a+2(1000a)+10000a+100)/10=(100a+100000a+100)/10=10a+10000a+10
(10a+10000a+10)/10=a+1000a+1

a0010 a2
10000a+10
(10000a+10)/10=1000a+1
(1000a+10000a+1+10+1)/10=100a+1000a+10
(100a+1000a+10)/10=10a+100a+1
(10a+100a+100a+1000a+1+10+1)/10=(10a+10000a+100)/10=a+1000a+10

a0011 a3
10000a+11
(10000a+100000a+11+110+1)/10=1000a+10000a+101
(1000a+10000a+10000a+100000a+101+1010+1)/10=100a+100000a+1000
(100a+100000a+1000)/100=a+1000a+10

a0100 a4
10000a+100
(10000a+100)/100=100a+1
(100a+1000a+1+10+1)/10=10a+100a+10
(10a+100a+10)/10=a+10a+1

a0101 a5
10000a+101
(10000a+100000a+101+1010+1)/10=1000a+10000a+1000
(1000a+10000a+1000)/1000=a+10a+1

a0110 a6
10000a+110
(10000a+110)/10=1000a+11
(1000a+10000a+11+110+1)/10=100a+1000a+101
(100a+1000a+1000a+10000a+101+1010+1)/10=10a+10000a+1000
(10a+10000a+1000)/10=a+1000a+100

a0111 a7
10000a+111
(10000a+100000a+111+1110+1)/10=1000a+10000a+1011
(1000a+10000a+10000a+100000a+1011+10110+1)/10=100a+100000a+10001
(100a+1000a+100000a+1000000a+10001+100010+1)/10=10a+100a+10000a+100000a+11010
(10a+100a+10000a+100000a+11010)/10=a+10a+1000a+10000a+1101

a1000 a8
10000a+1000
(10000a+1000)/1000=10a+1
(10a+100a+1+10+1)/10=a+10a+10

a1001 a9
10000a+1001
(10000a+100000a+1001+10010+1)/10=1000a+10000a+1110
(1000a+10000a+1110)/10=100a+1000a+111
(100a+1000a+1000a+10000a+111+1110+1)/10=10a+10000a+1011
(10a+100a+10000a+100000a+1011+10110+1)/10=a+10a+1000a+10000a+10001

a1010 aA
10000a+1010
(10000a+1010)/10=1000a+101
(1000a+10000a+101+1010+1)/10=100a+1000a+1000
(100a+1000a+1000)/100=a+10a+10

a1011 aB
10000a+1011
(10000a+100000a+1011+10110+1)/10=1000a+10000a+10001
(1000a+10000a+10000a+100000a+10001+100010+1)/10=100a+100000a+11010
(100a+100000a+11010)/10=10a+10000a+1101
(10a+100a+10000a+100000a+1101+11010+1)/10=a+10a+1000a+10000a+10100

a1100 aC
10000a+1100
(10000a+1100)/100=100a+11
(100a+1000a+11+110+1)/10=10a+100a+101
(10a+100a+100a+1000a+101+1010+1)/10=a+1000a+1000

a1101 aD
10000a+1101
(10000a+100000a+1101+11010+1)/10=1000a+10000a+10100
(1000a+10000a+10100)/100=10a+100a+101
(10a+100a+100a+1000a+101+1010+1)/10=a+1000a+1000

a1110 aE
10000a+1110
(10000a+1110)/10=1000a+111
(1000a+10000a+111+1110+1)/10=100a+1000a+1011
(100a+1000a+1000a+10000a+1011+10110+1)/10=10a+10000a+10001
(10a+100a+10000a+100000a+10001+100010+1)/10=a+10a+1000a+10000a+11010

a1111 aF
10000a+1111
(10000a+100000a+1111+11110+1)/10=1000a+10000a+10111
(1000a+10000a+10000a+100000a+10111+101110+1)/10=100a+100000a+100011
(100a+1000a+100000a+1000000a+100011+1000110+1)/10=10a+100a+10000a+100000a+110101
(10a+100a+100a+1000a+10000a+100000a+100000a+1000000a+110101+1101010+1)/10=a+10000a+1000000a+1010000

dus na 4 stappen hou ik over:

a0000 a0
a
=1/16

a0001 a1
a+1000a+1
=9/16

a0010 a2
a+1000a+10
=9/16

a0011 a3
a+1000a+10
=9/16

a0100 a4
a+10a+1
=3/16

a0101 a5
a+10a+1
=3/16

a0110 a6
a+1000a+100
=9/16

a0111 a7
a+10a+1000a+10000a+1101
=27/16=1+11/16

a1000 a8
a+10a+10
=3/16

a1001 a9
a+10a+1000a+10000a+10001
=27/16=1+11/16

a1010 aA
a+10a+10
=3/16

a1011 aB
a+10a+1000a+10000a+10100
=27/16=1+11/16

a1100 aC
a+1000a+1000
=9/16

a1101 aD
a+1000a+1000
=9/16

a1110 aE
a+10a+1000a+10000a+11010
=27/16=1+11/16

a1111 aF
a+10000a+1000000a+1010000
=5

Het is duidelijk dat een getal bewerkt wordt vanaf de laatste cijfers en naar voren werkt. Zoals HansH ook al opmerkte.

Het valt op dat er een grote regelmaat is in de eindwaardes. Opmerkelijk is dat getallen die eindigen op 0010 en 0011 na 4 stappen op dezelfde waarde komen. Hetzelfde geldt voor 0100 en 0101 en 1000 en 1010 en ook voor andere getalcombinaties.
Het aardige is dat na 4 stappen de meeste getallen een waarde lager dan het basisgetal bereikt hebben. Ik heb erbij gezet met welke factor de eindwaarde verschilt van het basisgetal (in decimale getallen). Daarvoor heb ik alleen gekeken naar het getal a. Niet naar de binaire getallen die ook over blijven, omdat het binaire restgetal dat ook overblijft verwaarloosbaar klein is bij heel grote getallen.

De factoren en het aantal keren dat ze voorkomen:
1/16 -- 1x
3/16 - - 4x
9/16 -- 6x
27/16 -- 4x
5 -- 1x

Je ziet al een normaalverdeling opdoemen. Misschien is dit de oorzaak van de random lijkende verdeling van het aantal stappen dat nodig is.
In een groot getal zullen verschillende van deze blokken achter elkaar uitgevoerd worden en het resultaat van de eerste is de beginwaarde van de volgende.

Hoeveel neemt de waarde gemiddeld af per 4 stappen? Om dat te berekenen ga ik niet optellen maar vermenigvuldigen.
Ik ga alle stappen met elkaar vermenigvuldigen en daar de 16e-machts wortel uit trekken.
Dus:

((1/16)^1 * (3/16)^4 *(9/16)^6 * (27/16)^4 * 5)^1/16A

De uitkomst komt heel dicht in de buurt van 9/16 (8,99301504443764/16) De afwijking kan komen door afrondingsproblemen van Excel.

Gemiddeld genomen wordt dus al na 4 stappen een waarde ver onder het basisgetal bereikt en hebben elke volgende 4 stappen datzelfde resultaat.
Een doorsnee getal zal dus vrij snel naar 1 bewegen, zelfs als er misschien een pad gevolgd wordt dat eerst een heel andere kant op lijkt te gaan.
Ook getallen die aanvankelijk extreem de hoogte in gaan zullen uiteindelijk teruggaan naar 1.

Een volgende stap die ik kan gaan zetten is proberen een getal samen te stellen dat zichzelf zo gaat herhalen dat het niet terug kan komen naar 1. Maar gezien de grote snelheid waarmee getallen uiteindelijk kleiner worden lijkt het me eigenlijk onmogelijk dat zo'n getal kan bestaan.
Door een dergelijke poging te doen hoop ik te leren begrijpen en misschien zelfs te kunnen verklaren waarom een uitzondering niet kan bestaan.

[HansH]

ik neem een binair getal a en plaats daar nog 4 cijfers achter.ik krijg dan een getal a0000 bijvoorbeeld of 10000a bin.

voor ik jouw lange analyse induik moet ik denk ik eerst snappen wat je doet.
Je zegt ''en plaats daar nog 4 cijfers achter'', dus aan de rechterkant?
ik zie uit jouw text echter dat je er 4 nullen achter plaatst (dus rechts) maar daarna 10000 ervoor plaatst. Dan ben ik lost.

[Nesciyolo]

ik neem een binair getal a en plaats daar nog 4 cijfers achter.ik krijg dan een getal a0000 bijvoorbeeld of 10000a bin.

voor ik jouw lange analyse induik moet ik denk ik eerst snappen wat je doet.
Je zegt ''en plaats daar nog 4 cijfers achter'', dus aan de rechterkant?
ik zie uit jouw text echter dat je er 4 nullen achter plaatst (dus rechts) maar daarna 10000 ervoor plaatst. Dan ben ik lost.

Het is eenvoudiger dan het lijkt. Inderdaad plaats ik er eerst 4 cijfers achter. Ik krijg dan vanuit a iets in de vorm: a####. Dan verander ik dat naar een meer conventionele notatie.
Bijvoorbeeld stel a=110. Ik plaats er 4 cijfers achter, laten we zeggen 1011. Het resulterende getal wordt 1101011.
Die bewerking is hetzelfde als a met 10000 vermenigvuldigen en er 1011 bij optellen. Dus: a1011 = 10000*a + 1011.
Om de berekeningen leesbaarder te maken voor buitenstaanders ben ik overgegaan naar die notatie. Ik moet bekennen dat ik tijdens het rekenen steeds a0000, a000, a00 etc. gebruikte. Die notatie is misschien niet eenduidig maar wel overzichtelijker.
Ik heb de berekeningen omgezet naar een gewone simpele algebra notatie maar met binaire getallen.

[Nesciyolo]

Korte samenvatting van mijn ("lange" analyse ):

1. een binair getal x =( 10000a + ####) kan 4x bewerkt worden zonder dat informatie nodig is over a
2. Getallen worden "cijfer voor cijfer" bewerkt van rechts naar links. De uitkomst van de bewerking van een cijfer heeft een bepaalde invloed op de volgende cijfers die aan de beurt komen.
3. In 11 van de 16 gevallen komen getallen na 4 bewerkingen lager uit dan het basisgetal
4. Gemiddeld genomen komen getallen na 4 bewerkingen uit op 9/16 van het basisgetal.
5. Al na 4 bewerkingen tekent zich het begin van een normale verdeling af. (misschien zelfs al eerder)
6. Gezien deze snelle gemiddelde afname lijkt het mij bijzonder onwaarschijnlijk dat er uitzonderingen zijn die niet uiteindelijk 1 bereiken.
7. Opmerkelijk genoeg komen verschillende getallen na 4 bewerkingen uit op dezelfde waarde.

De berekeningen in de post zijn belangrijk maar je hoeft ze niet allemaal te analyseren. Het zijn maar tussenstappen.

Dan nog een kleine correctie:

((1/16)^1 * (3/16)^4 *(9/16)^6 * (27/16)^4 * 5)^1/16A

moet natuurlijk zijn:
((1/16)^1 * (3/16)^4 *(9/16)^6 * (27/16)^4 * 5)^(1/16)

[RedCat]

hier dezelfde situatie maar dan doorgetrokken tot er een macht van 2 ontstaat.
(helaas werkt het niet handig in Excel omdat de uitlijning niet naar rechts gebeurt)

Uitlijning naar rechts zetten:
1. Markeer de kolom met de binaire getallen
2. klik op de "uitlijning naar rechts"-knop = rood gemarkeerd in dit plaatje:

[Nesciyolo]

Nog een kleine correctie op de getallen in mijn berekeningen.
Ingeval van x=(10000a+1111)binair is het getal na 4 stappen niet 5x zo groot als het basisgetal maar 81/16x

Aardig is dat nu mijn berekening van de gemiddelde afname van het getal na 4 stappen niet ongeveer maar exact 9/16 is (volgens Excel/LibreOffice Calc).

Hier zijn de uitkomsten wat overzichtelijker gepresenteerd:

tabel: 1e kolom: #### binair, 2e kolom hetzelfde getal hexadecimaal, 3e kolom resultaat na 4 stappen.

x=(10000a + ####) bin
.bin | hex | x' na 4 stappen
0000 | 0 | a
0001 | 1 | a+1000a+1
0010 | 2 | a+1000a+10
0011 | 3 | a+1000a+10
0100 | 4 | a+10a+1
0101 | 5 | a+10a+1
0110 | 6 | a+1000a+100
0111 | 7 | a+10a+1000a+10000a+1101
1000 | 8 | a+10a+10
1001 | 9 | a+10a+1000a+10000a+10001
1010 | A | a+10a+10
1011 | B | a+10a+1000a+10000a+10100
1100 | C | a+1000a+1000
1101 | D | a+1000a+1000
1110 | E | a+10a+1000a+10000a+11010
1111 | F | a+10000a+1000000a+1010000

.bin | hex | x'/x
0000 | 0 | 1/16
0001 | 1 | 9/16
0010 | 2 | 9/16
0011 | 3 | 9/16
0100 | 4 | 3/16
0101 | 5 | 3/16
0110 | 6 | 9/16
0111 | 7 | 27/16
1000 | 8 | 3/16
1001 | 9 | 27/16
1010 | A | 3/16
1011 | B | 27/16
1100 | C | 9/16
1101 | D | 9/16
1110 | E | 27/16
1111 | F | 81/16