Collatz Conjecture (onopgeloste problemen)

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Bericht 16-01-'14, 11:29

qwer

Berichten: 16

Collatz Conjecture (onopgeloste problemen)

mbt de http://en.wikipedia.org/wiki/Collatz_conjecture ben ik er achter gekomen dat:

op basis van n=1 tot 30,000: # loops i (stopping time) nodig om n naar 1 te brengen:

Gesorteerd op het aantal i nodig (klein naar groot 4,7,9,12,14,17,20,22,..):

- voor alle n waarvoor i = 4 (n= 5,9,13,17,21,...) - gap tussen deze getallen is 4 (log4 = 2)

- voor alle n waarvoor i =7 (19,35,51,...) - gap tussen deze getallen is 16 (log16=4)

- voor alle n waarvoor i = 9 (23,43,55,75,87,107) - gap tussen deze getallen is afwisselend 12 en dan 20, sum = 32 (log 32 = 5)

- voor alle n waarvoor i = 12 (15,59,135,143,187,263,..) - gap tussen deze getallen is afwisselend 8,44,76. sum = 128 (log128= 7)

- i = 14 result in sum = 256 (log256 = 8)

- i = 17 reuslt in sum = 1024 (log1024 = 10)

zelfde voor 20 (log4096) en 22 (log 16384)

Dit zou toch een stap dichter naar een oplossing, of formulering om de i bij elke n te vinden, moeten zijn?
Bijlagen
1 v2 (1).xlsx
(484.56 KiB) 142 keer gedownload
Omhoog

Bericht 16-01-'14, 12:36

317070

Gebruikersavatar
Berichten: 5.609

Re: Collatz Conjecture (onopgeloste problemen)

Dit zou toch een stap dichter naar een oplossing, of formulering om de i bij elke n te vinden, moeten zijn?
Waarom?

1) kun je bovenstaande bewijzen?

2) de clue zit hem net in het bewijzen dat er geen enkele (groep) getallen is dat niet in je rijtjes voorkomt. Je methode bevestigd hoogstens het vermoeden dat het zo moet zijn, maar is geen praktische methode om dat ook effectief aan te tonen.
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-
Omhoog

Bericht 16-01-'14, 13:52

EvilBro

Berichten: 7.068

Re: Collatz Conjecture (onopgeloste problemen)

- voor alle n waarvoor i = 4 (n= 5,9,13,17,21,...) - gap tussen deze getallen is 4 (log4 = 2)
Wat bedoel je hier mee?
Omhoog

Bericht 16-01-'14, 16:18

qwer

Berichten: 16

Re: Collatz Conjecture (onopgeloste problemen)

317070 schreef: ↑do 16 jan 2014, 12:36
Waarom?

1) kun je bovenstaande bewijzen?

2) de clue zit hem net in het bewijzen dat er geen enkele (groep) getallen is dat niet in je rijtjes voorkomt. Je methode bevestigd hoogstens het vermoeden dat het zo moet zijn, maar is geen praktische methode om dat ook effectief aan te tonen.
Als ik het had bewezen zou ik het hier niet posten! :) Ik post het hier zodat een meer intelligent persoon dan ik kan meedenken en dit dichter naar een oplossing kan brengen.

Als we weten (inderdaad op basis van patronen herkennen en niet obv herleiden/deductie) via een formule hoe veel i er voor een willekeurige n nodig zijn, dan zitten we mi redelijk dicht tegen een bewijs aan - i.e. dan weten we in ieder geval waar we heen gaan met het bewijs, momenteel is dat erg mistig.

Uiteraard; dit is uiteindelijk oudhollands prutswerk in een Excelletje, maar ik hoop bij dit soort problemen dat een andere invalshoek (ik ben geen wiskundige; zit zelf in M&A en de hele dag in Excel analyses te bouwen) nieuw licht kan laten schijnen op het probleem

EvilBro - ik kan dat wat lastig uitleggen, helpt de Excel? Daar staat in elke tab (tab naam = loops required i) hoe ik aan die getallen ben gekomen
Omhoog

Bericht 16-01-'14, 16:57

Math-E-Mad-X

Gebruikersavatar
Berichten: 2.906

Re: Collatz Conjecture (onopgeloste problemen)

EvilBro schreef: ↑do 16 jan 2014, 13:52

voor alle n waarvoor i = 4 (n= 5,9,13,17,21,...) - gap tussen deze getallen is 4
Wat bedoel je hier mee?


Volgens mij bedoelt hij dat hij alle getallen n op een rijtje gezet heeft waarvoor de stopping time i gelijk is aan 4.

Dus de getallen 5,9,13,17 en 21 hebben allemaal stopping time 4. Verder merkt hij op dat er steeds een verschil van 4 tussen twee opeenvolgende getallen uit dit rijtje is.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
Omhoog

Bericht 16-01-'14, 17:00

Th.B

Berichten: 546

Re: Collatz Conjecture (onopgeloste problemen)

Daarna merkt hij dan op dat als je kijkt naar de som van alle mogelijke verschillen, dit steeds een tweemacht is. Dan berekent hij de 2log.
Omhoog

Bericht 16-01-'14, 18:29

EvilBro

Berichten: 7.068

Re: Collatz Conjecture (onopgeloste problemen)

Volgens mij bedoelt hij dat hij alle getallen n op een rijtje gezet heeft waarvoor de stopping time i gelijk is aan 4.
Maar wat is dat dan "de stopping time"? Immers:

5 -> 16 -> 8 -> 4 -> 2 -> 1 (5 stappen)

9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (19 stappen)

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (9 stappen)

17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (12 stappen)

Hoe is dit een stopping time van 4?
Omhoog

Bericht 16-01-'14, 19:57

qwer

Berichten: 16

Re: Collatz Conjecture (onopgeloste problemen)

Excuses voor de enorm slechte uitleg! En dank Math-E-Mad en Th B voor jullie hulp

EvilBro je hebt helemaal gelijk - deze file staat al een half jaar stof te verzamelen en ik vergeet compleet te vermelden dat stopping time:

--> 1 hoger is dan gewoonlijk aangezien ik n ook meeneem in de count in cell $C2

--> zoals ik boven aangaf zou ik graag tot een dekkend algoritme komen voor alle n. Dat betekent ook dat als ergens in de loop er een getal x als uitkomst komt waarbij x < n dan betekent dat dat ik dan kan stoppen met de riedel. Dat zie je ook in de formule " =IF(EVEN(A4)=A4,A4/2,A4*3+1)*(A4>=$A$2) " waarbij n op rij2 staat.

Ik zie het dus zo: voor mijn "adjusted stopping time" = 4 is dus de implicatie dat alle getallen 1+4x voldoen aan de stelling (dat moeten we dan nog even bewijzen, maar dat lukt dan wel weer).

Ik hoop dat dit ergens heen gaat - excuus als dit alles een waste of time blijkt te zijn!
Omhoog

Bericht 16-01-'14, 23:02

qwer

Berichten: 16

Re: Collatz Conjecture (onopgeloste problemen)

Ik zou graag ook nog even het volgende delen dat wellicht belangrijk kan zijn:

Ik merkte op dat wanneer een groot genoeg getal in die "adjusted stopping time" = 4 reeks zit (i.e. alle n die voldoen aan 1+4x) op driekwart van n zal uitkomen. Een voorbeeld zou zijn n = 2997:
  • 2997 zit in de "adjusted stopping time" = 4 reeks, want is gelijk aan 1+ 4*749
  • we kunnen al voorspellen dat 'ie uiteindelijk bij Round(2997*0.75) = 2248 uit gaat komen. En dat doet ie dus in 4 stappen:
  1. 2997 =n
  2. 8992
  3. 4496
  4. 2248
Dus:

1: Als ergens in de "loop" uitkomst < n , dan voldoet n aan Collatz

2. Alle n die voldoen aan 0+2x komen in 2 stappen op 0.5*n (dat hoef ik niet uit te leggen)

3. Alle n die voldoen aan 1+4x komen in 4 stappen op 0.75*n (zoals hierboven). Dat is de eerste uitkomst in de "loop" waarbij uitkomst < n, en hierbij voldoet n aan Collatz

Hebben we dus al driekwart van de getallen gedekt :)

Maar dan wordt het leuk:

4. Alle n die in de 7-serie zitten (n voldoet aan 3+16x) komen in 7 stappen uit op 0.5627*n (+/- 0.0002). Wederom: Dat is de eerste uitkomst in de "loop" waarbij uitkomst < n, en hierbij voldoet n aan Collatz. Dit 0.5627 is een getal dat ik niet direct herken maar volgens mij wel te herleiden is - kom ik zo nog wel op terug
  • even een voorbeeld van een 7-serie, neem n=2995 (=3+16*187)
  • We kunnen voorspellen dat 'ie uiteindelijk bij Round(2995*0.5627) = 1685 uit gaat komen. En dat doet ie dus in 7 stappen:
  1. 2995
  2. 8986
  3. 4493
  4. 13480
  5. 6740
  6. 3370
  7. 1685
OK tot zover goed. Nu zet ik even alle Adjusted Stopping Times (AST) en de multipliers zoals hierboven op een rij:

[ ik kon deze niet invoegen, bekijk aub de bijgevoegde excel]

Ik verwijs ook naar de vorige Excel file voor verificatie hiervan obv voorbeelden.

Als je bijv. de A- AST reeks pakt (4,9,14) dan zie je de multiplier steeds groter worden. Dat zie je voor alle AST reeksen. Maar ik herken deze reeks niet (lijkt logaritmisch maar ik krijg het niet voor elkaar de reeks te ontdekken).

- AST lijkt zich op te stellen in reeksen (A+5*i, zoals in de 2e kolom van de tabel)

- De multiplier binnen zo'n AST reeks volgt ook een reeks, die kan ik dus niet ontdekken, maar lijkt zwaar exponentieel. Heb wat zitten vogelen met logaritmes maar lijkt niet te werken.

- als deze reeksen bekend dat zie ik het nog wel voor me dat we dat kunnen linken aan n en dan volgt dus het algoritme wat n kan koppelen aan AST en de multiplier, en dan volgt het bewijs waarom dat zo is - moet allemaal te doen zijn?
Bijlagen
reeks.xlsx
(63.68 KiB) 139 keer gedownload
Omhoog

Bericht 17-01-'14, 00:36

qwer

Berichten: 16

Re: Collatz Conjecture (onopgeloste problemen)

OK ondertussen pruts ik nog even verder:

ik heb de reeks weten te ontdekken, al moet ik het exacte algoritme nog even opstellen:

Voor volgnummer j:

De AST(j) = 1 / 2^j * 3^j / 2^j > iets in die trant. ik weet dat ik dit kan vereenvoudigen maar hij is nog niet helemaal consistent, ik zit er wel redelijk dicht tegenaan in kolom E van bijgevoegde Excel.

Als ik deze formule heb (en dat lijkt prima te doen) dan kan ik, EN als ik weet in welke AST serie n zit (dat deel heb ik nog niet helemaal helder), ook vertellen (1) in hoeveel stappen dat getal bij (2) het multiplier product getal komt, waarbij het multiplier product < n dus n voldoet aan Collatz

Op deze manier komt een algoritme voor Collatz oplossingen snel dichterbij...
Bijlagen
reeks.xlsx
(65.14 KiB) 116 keer gedownload
reeks.xlsx
(65.14 KiB) 81 keer gedownload
Omhoog

Bericht 17-01-'14, 00:44

317070

Gebruikersavatar
Berichten: 5.609

Re: Collatz Conjecture (onopgeloste problemen)

Ja, je ondervindingen zijn bovendien vrij gemakkelijk te bewijzen met modulo-rekentechnieken ;)

Je Excel-file werkt trouwens niet als je formules gebruikt als:
=VLOOKUP(A3,'file:///Users/rvanmazijk/Documents/Math/1 v3 (1).xlsm'#$Sheet1.$D$1000:$G$1500,4,0)
Zie je wat er mis gaat als ik je excel op mijn pc wil openen?

Maar, op die manier kom je er niet. Je kunt inderdaad van extreem veel patronen van de vorm a*n+b bewijzen dat ze in i(n) stappen naar 1 gaan. Het probleem is dat je moet bewijzen dat ALLE getallen naar 1 gaan.

Er is een reden waarom met vermoedt dat het Collatz-probleem niet bewijsbaar is met ons huidige stelsel van axioma's. ;) But have fun, ik heb vroeger ook al heel veel plezier gehad met het uitwerken van een aantal methode's om het te bewijzen :)

Ik heb bijvoorbeeld gezocht naar een invariant in de binaire notatie van de getallen, een getal dat bij beide operaties afneemt, en zo een maximum zou leggen op hoe ver een getal kan groeien voor ze naar beneden moet gaan. (ik heb ze nog niet gevonden ;) ) Ik heb vervolgens gezocht naar een methode om te bewijzen dat iedere groep van operaties waaronder getallen convergeren naar een limiet-cycle zo een invariant zouden hebben, maar ik heb daar ook daar nog niets gevonden. :mrgreen:
What it all comes down to, is that I haven't got it all figured out just yet

And I've got one hand in my pocket and the other one is giving the peace sign

-Alanis Morisette-
Omhoog

Bericht 17-01-'14, 01:04

qwer

Berichten: 16

Re: Collatz Conjecture (onopgeloste problemen)

Erg veel dank 317070 - het Excel filetje was niet zo belangrijk

Ik zie inderdaad wel hoeveel patronen er te ontdekken vallen, en ik blijf er in geloven dat ik alle n ook in een formule kan vatten, ook al heb ik daar wellicht niets aan in een bewijs. Waarschijnlijk zijn dit soort basale nummer-problemen aansprekend dankzij hun eenvoud. Ik ga er in ieder geval nog even mee doorprutsen

Nogmaals dank voor je reactie
Omhoog
Reageer

Terug naar “Wiskunde”