Question

X_(n+1)→X_(n)/2       ,wenn X gerade

X_(n+1)→X_(n)*3+1   ,wenn X ungerade

Aufgabe:

A = Welche Startnummer unter 1.000.000.000 (eine Milliarde) produziert die längste Folge?

B = Wie lang ist die längste Folge?

Comments

Gibt es denn eine Abbruchbedingung für die Folge ?

Aber vielleicht verstehe ich die Aufgabe auch gerade komplett falsch.

---

Also es geht darum welche Zahl X die längste Folge produziert, wenn die Startzahl zwischen 1 und 1.000.000.000 (eine Milliarde) ist. Bei A: ist gesucht welche Zahl X genau das ist und bei B: sucht man wie viele Folgen es produziert.

Beispiel 1 A: x= 53  und  B: 12 Folgen

X = 53:

53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Man kann sehen, dass die Folge (Start bei 53 und Ende bei 1) aus 12 Schritten besteht.

Beispiel 2 A: X= 1360  und  B: 14 Schritte

X = 1360:

1360 → 680 → 340 → 170 → 85 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

Man kann sehen, dass die Folge (Start bei 1360 und Ende bei 1) aus 14 Schritten besteht.

---

Zur Erklärung:

Also es geht darum welche Zahl X die längste Folge produziert, wenn die Startzahl zwischen 1 und 1.000.000.000 (eine Milliarde) ist. Bei A: ist gesucht welche Zahl X genau das ist und bei B: sucht man wie viele Folgen es produziert.

Beispiel 1 A: x= 53  und  B: 12 Folgen

X = 53:

53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Man kann sehen, dass die Folge (Start bei 53 und Ende bei 1) aus 12 Schritten besteht.

Beispiel 2 A: X= 1360  und  B: 14 Schritte

X = 1360:

1360 → 680 → 340 → 170 → 85 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1

Man kann sehen, dass die Folge (Start bei 1360 und Ende bei 1) aus 14 Schritten besteht.

Kann mir da jemand helfen? Hab gerade so die Aufgabe verstanden :/

---

Damit soll 1 offenbar die Abbruchbedingung sein. Sowas sollte auch immer im Aufgabentext formuliert sein. Denn nach der 1 kann ich ja noch weitere Folgenglieder berechnen. Aber wie dir schon gesagt worden ist, ist das ein bekanntes Problem.

Wie darf das Problem gelöst werden ?

Man kann sich da ja ein kleines Programm schreiben, die sich zu jedem Startwert, den Anzahl der Folgeglieder ermittelt.

Man kann auch ausgehend von der 1 anfangen rückwärts zu rechnen

x(n + 1) → x(n) / 2 wenn x(n) gerade

x(n + 1) → x(n)·3 + 1 wenn x(n) ungerade

das bedeutet umgekehrt:

x(n) → 2·x(n + 1)

x(n) → (x(n + 1) - 1)/3, wenn hier eine ganze ungerade zahl heraus kommt.

1 <-- 2 <-- 4 <-- 8 <-- 16 <-- 5 <-- ...

Ich sehe aber momentan keinen anderen Weg als das automatisiert zu machen.

---

Damit soll 1 offenbar die Abbruchbedingung sein. Sowas sollte auch immer im Aufgabentext formuliert sein. Denn nach der 1 kann ich ja noch weitere Folgenglieder berechnen. Aber wie dir schon gesagt worden ist, ist das ein bekanntes Problem.

Wie darf das Problem gelöst werden ?

Man kann sich da ja ein kleines Programm schreiben, die sich zu jedem Startwert, den Anzahl der Folgeglieder ermittelt.

Man kann auch ausgehend von der 1 anfangen rückwärts zu rechnen

x(n + 1) → x(n) / 2 wenn x(n) gerade 

x(n + 1) → x(n)·3 + 1 wenn x(n) ungerade 

das bedeutet umgekehrt:

x(n) → 2·x(n + 1) 

x(n) → (x(n + 1) - 1)/3, wenn hier eine ganze ungerade zahl heraus kommt.

1 <-- 2 <-- 4 <-- 8 <-- 16 <-- 5 <-- ...

Ich sehe aber momentan keinen anderen Weg als das automatisiert zu machen.

---

Leider besitze ich diese Fähigkeit leider nicht solch ein Programm zu schreiben. Deswegen meinte ich ja auch ich hätte liebend gerne die Antworten darauf :(

---

Ist das eine Aufgabe die Ihr bekommen habt ? Und wenn ja in welchem Fach ? Habt ihr dafür irgendwelches Vorwissen euch angeeignet ?

---

Das habe ich gefunden ABER wie erstelle ich solch ein Programm?

max = [1 1];
 
for it = 1 : 1000000000 
    coll = it;
    count = 1;
    while coll ~= 1
        if mod(coll, 2) == 0
            coll = coll / 2;
        else
            coll = coll * 3 + 1;
        end
        count = count + 1;
    end
    if count > max(1)
        max(1) = count;
        max(2) = it;
    end
end
 
max

---

Das ist nicht aus dem Unterricht. Das gehört zu einem Spiel was man lösen muss. Ich habe keinerlei Fachwissen darüber geschweige denn Vorwissen. Leider...

---

Aus Neugier, um was für ein Spiel handelt es sich?

---

Geocaching heißt es. Ist bestimmt bekannt.

Answer 1

Hier steht alles dazu:

https://de.wikipedia.org/wiki/Collatz-Problem  

http://mathworld.wolfram.com/CollatzProblem.html

Comments

Das beantwortet leider immer noch nicht die Frage A und B.

---

Der Iterationsrechner kann das auch kostenlos ohne langen Code:

http://www.gerdlamprecht.de/Roemisch_JAVA.htm##@Na=670617270;b=1;c=0;@N@Bi]=Iter(1,i+a,0,'x%3E1','x=x%252%3C1?x/2:x*3+1;','IT');if(@Bi]%3Eb){b=@Bi];c=i+a;}@Ni%3E1000@N1@N0@N#

(LINK endet mit N# und beinhaltet den Code)

Startnummer steht in Variable c und

Iterationstiefe NT ("längste Folge") in Variable b.

Die Zahlenfolge ist so bekannt, dass man nicht mal rechnen braucht:

http://www.oeis.org/A006877/b006877.txt  

Der Index 66 ist gerade noch kleiner als 1 Mrd.

Achtung: bei Geocaching ist manchmal bei uneindeutigen Fragen wie "längste Folge" fraglich, ob die erste Iteration (Index i=0) mitgezählt wird, oder nicht. (d.h. b könnte um 1 variieren)

---

Vielen Dank hab die Seite dann auch noch gefunden.

Beste Grüße