+1 Daumen
1,1k Aufrufe

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?

Avatar von

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.

1 Antwort

0 Daumen
Avatar von 5,7 k

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)

Bild Mathematik

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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community