Lösung: Das 3n+1 Problem

Stand: 28.11.2021

Es gibt so mathematische Spielereien, mit denen sich hochbezahlte Köpfe Ihr Leben lang beschäftigen ohne zum Ende zu kommen. Weil es angeblich spannende Fragen sind. Weil die Fragen nicht gelöst werden können, lobt man dafür sogar Belohnungen aus. Eins der Probleme schauen wir uns kurz an und lösen dann mal auf:

Lösung: Das 3n+1 Problem

Die Funktion um die es heute geht ist ein Algorithmus, weniger eine Funktion: f(x)=3x+1 ? x/2

In Worten: Wenn x ungerade ist, gilt x=3x+1. Wenn x gerade ist, dann gilt x = x/2 .

Die Behauptung:

Für alle Ganzzahlen n>0 gilt, daß am Ende des Algorithmusses eine Zahlenschleifen von 4,2,1 rauskommt. Es gibt keine anderen Schleifen. Was zu beweisen ist.

Beispiele:

Ausgabeformat:  Anfangszahl: X-Wert big = größte Zahl in der Kette

1: x=4 big=4
1: x=2 big=4
1: x=1 big=4
1: x=4 big=4
1: x=2 big=4
1: x=1 big=4

Erklärt:

1 ist ungerade => 1*3+1 = 4
4 ist gerade => 4/2 = 2
2 ist gerade => 2/2 = 1

Man sieht, daß hier eine Schleife 4,2,1 rauskommt, weil bei x=1 das Ergebnis wieder 4 ist. In der Programmierung ist das eine Endlosschleife, weil die Abbruchbedingung fehlt. Deswegen stoppen alle nachfolgenden Ausgaben auch bei 1.

Anfangszahl 2:

2: x=1 big=1

Da muß man nicht viel erklären, weil steht oben schon 😉

3: x=10 big=10
3: x=5 big=10
3: x=16 big=16
3: x=8 big=16
3: x=4 big=16
3: x=2 big=16
3: x=1 big=16

Auch hier 4,2,1

4: x=2 big=2
4: x=1 big=2

Oh.. eine 4.. wie in 4,2,1.. ähm ja. siehe oben

5: x=16 big=16
5: x=8 big=16
5: x=4 big=16
5: x=2 big=16
5: x=1 big=16
6: x=3 big=3
6: x=10 big=10
6: x=5 big=10
6: x=16 big=16
6: x=8 big=16
6: x=4 big=16
6: x=2 big=16
6: x=1 big=16
7: x=22 big=22
7: x=11 big=22
7: x=34 big=34
7: x=17 big=34
7: x=52 big=52
7: x=26 big=52
7: x=13 big=52
7: x=40 big=52
7: x=20 big=52
7: x=10 big=52
7: x=5 big=52
7: x=16 big=52
7: x=8 big=52
7: x=4 big=52
7: x=2 big=52
7: x=1 big=52
8: x=4 big=4
8: x=2 big=4
8: x=1 big=4
9: x=28 big=28
9: x=14 big=28
9: x=7 big=28
9: x=22 big=28
9: x=11 big=28
9: x=34 big=34
9: x=17 big=34
9: x=52 big=52
9: x=26 big=52
9: x=13 big=52
9: x=40 big=52
9: x=20 big=52
9: x=10 big=52
9: x=5 big=52
9: x=16 big=52
9: x=8 big=52
9: x=4 big=52
9: x=2 big=52
9: x=1 big=52

Das läßt sich beliebig für jede Ganzzahl n > 0 wiederholen.

Diese Auflistungen hier zeigen schon den Grund für das Verhalten und das ist wenig mystisch und noch weniger unerklärlich.

Die Auflösung:

Die Frage war: Wieso kommt am Ende immer eine Schleife mit ( 4,2,1 ) raus?

Das ist ganz leicht, weil 3x+1 für jedes Start-x irgendwann auf 2^n trifft. 2^n ist die folgende Operation : 2*2*2*2*2*2*2….*2 . Das ist genau das Gegenteil von der Berechnung für gerade Zahlen in dem Algorithmus ( x=x/2 ) . Wenn ich also z.b. 2^6 treffe, was 64 ist, und dies ständig durch 2 teile, kommt am Ende ohne Zweifel 1 raus. Es ist egal wie groß n ist, das gilt immer. Der Algorithmus endet also immer in der Sequenz ( 2^n , 2^(n-1) … 2^(n-n) und 2^(0) = 1 . Da 1*3+1 = 2^2 ist, terminiert der Algorithmus nicht und es kommt zur Endlosschleife.

Das ist absolut kein Wunder.

Die nächste Behauptung ist: es gibt keine anderen Schleifen.

Da 3x+1 ausschließlich bei ungeraden Zahlen angewendet wird und bei der Berechnung garantiert immer eine gerade Zahl herauskommt und nicht jede gerade Zahl eine Potenz von 2 ist, kann es keine anderen Schleifen geben, da bei jedem Schritt nach einer ungeraden Zahl die Teilung durch 2 solange stattfindet, bis wieder eine ungerade Zahl kommt.

Da es für jede Potenz 2^n für n > 1 eine ungerade Zahlen x gibt, die x = (2^n -1) / 3 erfüllt, kann es keine andere Schleife geben, denn jede gerade Zahl geteilt durch 2 trifft am Ende der Teilung gerader Zahlen immer auf eine ungerade Zahl und sobald diese ungerade Zahl 1 ist, ist die Schleifenbedingung erfüllt. Da eine ungerade Zahl verdreifacht wird(+1), aber eine gerade Zahl nur halbiert, wächst x über die Zeit im Schnitt an, bis x = 2^n ist, also eine 2er Potenz getroffen wird. QED.

Negative Startwerte

Bei negativen Startwerten kommt es ganz schnell zu Zahlenschleifen. Das liegt nach Analyse des Algorithmuses an einem BUG. Wenn das ein Programm wäre, würde ich dafür eine 6 vergeben und es dem Entwickler um die Ohren hauen 😉

Die Formel ist ja „3x+1“. Diese Formel kann für einige Ganzzahlen keine 2er Potenzen im negativen Zahlenstrahl finden. Der „Bug“ liegt im „+“ Zeichen, daß im negativen Zahlenraum zum „Fehlerfall“ führt. Es müßte nämlich eigentlich „3x-1“ lauten. Damit erreicht man im negativen Zahlenbereich eine exakte Spiegelung des positiven Zahlenraumes, weil alle oben genannten Bedingungen dann erfüllt sind.

Das liegt an der Verletzung der Gleichungsregel, daß wenn ich auf der einen Seite der Gleichung etwas abziehe, ich es zum Ausgleich auf der anderen Seite hinzufügen muß:

2 = 5-3 => 2+3 = 5

Der Algorithmus „verletzt“ dies beim Übergang von positiven zu negativen Startzahlen. Das ist sprach-mathematisch natürlich inkorrekt, beschreibt aber das Problem sehr gut.

Beispiel:

x = -21

x = -63 / 3

x*3 = -63 = -62 -1

x*3+1 = -62

Wenn man das jetzt für +21 macht, gilt:

21*3+1 = 64

64 = 2^6 also durch 2 bis zur 1 teilbar. Für -62 gilt das nicht, da kommt bei unserem Algorithmus -31 raus, statt -32 wie es nötig wäre um zu terminieren.

Fazit

Das der Algorithmus im Negativen Zahlenbereich „mysteriöse Schleifen“ bildet, im positiven Bereich aber nicht, ist also ein Fehler im Algorithmus und nicht „mysteriös“, wie einige Youtuber das andeuten. Er ist einfach schlecht gemacht worden 😀

Kommentare sind erlaubt, also tobt Euch aus 😉

Wieviel Zeit und Energie in das angebliche Problem eines defekten Algorithmuses verplempert wird und wurde, könnt Ihr hier nachlesen:

https://en.wikipedia.org/wiki/Collatz_conjecture#Iterating_on_all_integers

oder lasst es Euch hier „erklären“:

Ich kann mich den Matheprofs nur anschließen: Verplempert keine Zeit damit, es ist einfach nur ein kaputter Algorithmus.

Nicht „3x+1“ ist das Problem, sondern der Algorithmus an sich ist defekt. Wie man sich daran so aufgeilen kann wie im obigen Beitrag ist mir persönlich ein Rätsel. Solche Fehler kommen in der Programmierung laufend vor, weil einer bei der Umsetzung oder der Planung geschlafen hat.

Hier ein kleines Programm für Java, das bei evtl. doch stattfindenden Versuchen hilfreich sein kann. Der BUG ist darin aber schon behoben worden 😉



public class ThreeXPlusOne {


	static public void main(String[] args) {
	
		long x = 0;
		long max = 99;
		
		for(long n=-max;n<max;n++) { x = n; long big = 0; if ( n != 0 ) do { if ( (x/2)*2 == x ) { x = x/2; } else { if ( n > 0 ) {
						x = 3*x+1;
					} else  x = 3*x-1; // Korrektur für n<0 weil, mit +1 kann man nie 2^n treffen } if ( n > 0 && x > big ) big = x;
				if ( n < 0 && x < big ) big = x; if ( args.length > 0 ) System.out.println( n+": x="+x+" big="+big);

			} while ( x != -1 && x != 1 && x!=n );
			
			if ( args.length == 0 ) System.out.println( n+": x="+x+" big="+big);
		}	
	}
}

Ihr werdet den Code noch einem Beautyfier übergeben müssen, weil WordPress den unbedingt umformatieren muß ( und ich keine Lust habe, deswegen in der WordPressdatenbank den Code direkt einzutragen ).

Linux am Dienstag – Programm für den 23.11.2021

Auch heute Abend werden wir uns wieder ausführlich über IT- und Linuxthemen austauschen. Da man es nicht oft genug erzählen kann, hören wir uns heute an, wieso bei Passwörtern „Länger“, besser ist.

Linux am Dienstag – Programm für den 23.11.2021

Diesen Dienstag, wie immer ab 19 Uhr, haben wir u.a. im Programm:

  • Cybercrime – Wieviel Schaden Cyberverbrecher anrichten
  • Cybercrime – Emotet kehrt zurück
  • Sicherheitslücke – Hikvision Sicherheitskameras mit Remote-Code-Execution(RCE) Lücke
  • Gnome – Über die Unmöglichkeit des DE Wechsels
  • Vortrag – Sie und Ihr Passwort

Wie jede Woche per Videokonferenz auf https://meet.cloud-foo.de/Linux .

Kleine Anmerkung: Die bisherigen Vorträge findet man jetzt unter https://linux-am-dienstag.de/archiv/ .

Meteo, der fallende Stern am Pinephonehimmel

Wetter Apps gibt es ja viele, aber Meteo hat etwas, das andere nicht haben: Karten!

Meteo, der fallende Stern am Pinephonehimmel

Jetzt weiß ich genau, daß sich die meisten über den Beitragstitel aufregen werden. Bevor Ihr das tut, haltet einen Moment inne, lest bis ans Ende und dann lasst Euren Frust raus 😉

Neulich habe in einer Updatemeldung Meteo entdeckt und sofort ausprobiert, weil mir die neue Gnome-Wetter-App nicht wirklich gefällt. Ich fand die Version von Gnome 3.38 optisch viel besser. Deswegen habe ich auch Meteo ausprobiert und war begeistert. Ok, ein paar Übersetzungsfehler sind noch drin, aber das ist nicht wild.

Meteo auf dem Pinephone

Die nachfolgenden Bilder stammen alle von den Bugreports für das Pinephone, insofern wißt Ihr jetzt, daß es auch dort funktioniert, wenn auch mit Abstrichen (deswegen die Bugreports). Geht einfach davon aus, daß es auf dem Desktop, bis auf den Mondphasenübersetzungsbug, problemlos funktioniert.

Auf dem Pinephone sieht das für Meteo leider etwas anders aus, ist aber immer noch brauchbar. Neben den üblichen Tagesvorhersagen, die man im Screenshot oben nicht ganz sieht, scheint auch die Anzeige der Stadt für die man die Vorhersagen haben will, nicht ganz korrekt zu sein. aber auch das ist eher nebensächlich.

Jetzt der Knaller der App, weswegen ich die überhaupt erwähne: Es hat eine Kartenfunktion wie Windy \o/

Neben Temperaturen, Niederschlag und Wind, gibt es auch eine Wolkenbedeckung, was nützlich ist, wenn man schauen möchte, ob Regenwolken im Anmarsch sind. Noch ist die zeitliche Auflösung nicht vorhanden, aber das wird bestimmt kommen.

Der fallende Stern

Jetzt fragt Ihr Euch bei den Features zurecht, wo ist denn da der fallende Stern am Apphimmel aus dem Titel des Artikels. Tja, wie soll ich sagen… die Kartenfunktion gibt es nur noch bis Dezember 🙁 Der Kartenlieferant Dark Sky liefert kein Kartenmaterial mehr aus oder will Geld haben ( mein Favorit ). Es kann sein, daß die Kartenfunktionen dann komplett rausfliegen und damit wäre die App dann nichts besonderes mehr. Dabei hatte ich mich so gefreut.

Aus dem Pinephone muß man bei den Karten auch viel Geduld haben, weil die GPU nicht zum Verarbeiten der Bilder genommen wird, ist das zäh bis kurz vor auskristallisiert. Die Karte hat auch diverse Bugs, z.b. klappt das mit dem Zoomen mit zwei Fingern nicht, war fairerweise auch nicht vorgesehen, und das Koordinatensystem ist gespiegelt: Klickt man oben, scrollt es nach unten und umgekehrt.

Jetzt die guten Nachrichten: Es soll auf Libhandy umgestellt werden, was diverse Probleme inkl. Zooming beheben wird, falls es dann noch etwas zu zoomen gibt.

Auf dem Desktop könnt Ihr auch derweil an einer sehr zu empfehlenden Wetteranwendung erfreuen.