Het vermoeden van Collatz is één van de simpelste open problemen in de wiskunde. De vraag is of startend van eender welk natuurlijk getal \(n\), het herhaaldelijk toepassen van een zekere procedure je altijd bij het getal 1 zal brengen. De procedure wordt beschreven door de functie \(f(n) = n/2\) als \(n\) even is, of \(3n+1\) als \(n\) oneven is. Er is veel numerieke evidentie dat dit vermoeden juist is, maar het is niet bewezen. Als er getallen zouden zijn die nooit bij 1 terechtkomen, moeten deze dan ofwel in een cykel terechtkomen, of ze moeten divergeren naar oneindig.
Aangezien het vermoeden van Collatz al veel bestudeerd is, gaan we hier een variant bekijken. Meer specifiek beschouwen we de functie \(f(n) = \left\{ \begin{array}{lr} n/3& \text{ als $n\equiv 0 \pmod 3$}\\ 5n + 1 & \text{ als $n\equiv 1 \pmod 3$}\\ n + 2 & \text{ als $n\equiv 2 \pmod 3$} \end{array} \right.\)
Vertrekkend van bijvoorbeeld 1 vinden we dan achtereenvolgens \(1 \rightarrow 6 \rightarrow 2 \rightarrow 4 \rightarrow 21 \rightarrow \dots\). Wij willen nu weten of deze procedure soms in lussen terechtkomt door een graaf te maken van het proces: voor een waarde \(i\) is er in de graaf een boog van de top met nummer \(i\) naar de top met nummer \(f(i)\).
Implementeer de interface GraphMaker1 in een klasse genaamd CollatzGraphMaker. Hiervoor schrijf je een methode public UndirectedGraph<Long> makeCollatzGraph(long maxStart) die de graaf maakt met longs als toppen, en waarbij twee toppen met elkaar verbonden zijn als \(f\) de waarde van de ene top op de andere top afbeeldt. De toppen zijn alle waarden die je kan bereiken door het proces van \(f\) te starten op alle longs tussen 1 en maxStart (inclusief). Daarnaast schrijf je een methode public <T> T connectedComponents(UndirectedGraph<T> graph), die een ongerichte graaf als argument heeft. Deze methode geeft terug hoeveel samenhangscomponenten de graaf heeft. Dat is: hoeveel verschillende ‘eilanden’ van toppen zijn er, waarbij het onmogelijk is om van een eiland naar een ander te gaan door bogen van de graaf te volgen.
Bijvoorbeeld: onderstaande graaf heeft 2 samenhangscomponenten.
We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib2. Deze bevat onder meer de klassen UndirectedGraph en Node. De API van deze bibliotheek vind je hier3. Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.
Opmerking: pas de graaf uit de input van de methode niet aan in je algoritme. Indien je dit wel doet, zullen de testen falen.
Gebruik eventueel de testklasse SimpleTest4 om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.
Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in IntelliJ, moet je het bestand graphlib.jar5 toevoegen aan je project. Hiervoor ga je naar File -> Project Structure…. Vervolgens kies je Libraries en klik je op de knop met het plusteken (+). Kies voor Java en navigeer naar het gedownloade bestand graphlib.jar.