Collatz Problem-longest chain under 1mil

Slabic

Hallo, folgendes versuche ich zu lösen:

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 40 20 10 5 16 8 4 2 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

Ich habe dazu folgendes Programm geschrieben.
Wenn ich es mit dem Debugger durchlaufe für einige Zahlen, scheint alles richtig zu laufen, aber bei etwas mehr als 200000, bzw. auch bei anderen größeren Zahlen um die 300k, 900k scheint es auch in eine endlos-schleife zu gelangen...ich sehe aber nicht, wo das Problem ist.
Ist es vielleicht eine zu lange Kette, wofür mein Prog zu lahm ist?
Kann ich mir eigentlich nicht vorstellen, da die Zahlen bis 200k recht schnell angegeben werden.

#include<iostream>
#include<fstream>

using namespace std;

int main (){
	ofstream fout("Zahlen.txt");
	int x,i=1;
	int j;
	for(x=300000;x<1000000;x++){

		if(x%2==0){
			j=x;
		while(x%2==0){
			while(x>1 &&x%2==0){
				x=x/2;
				i++;
			}

			while(x>1 &&!(x%2==0)){
				x=3*x+1;
				i++;
			}

		}
		if(i>1){
		fout<<"Zahl:"<<j<<"Length:"<<i<<endl;
		cout<<"Zahl:"<<j<<"Length:"<<i<<endl;
		}
		i=1;
		x=j;
		} else {
			j=x;
			while(!(x%2==0) && x>1){
						while(x>1 &&!(x%2==0)){
							x=3*x+1;
							i++;
						}

						while(x>1 &&x%2==0){
							x=x/2;
							i++;
						}

		}
			if(i>1){
			fout<<"Zahl:"<<j<<"Length:"<<i<<endl;
			cout<<"Zahl:"<<j<<"Length:"<<i<<endl;
			}
			i=1;
			x=j;

		}
	}
	return 0;
}

grüße,
Slabic

Hallo Slabic,

Sobald der Wert für x in dem Programm oben 302354 erreicht, ergibt sich daraus nach 124 Schritten der Collatz-Folge der Wert 2482111348. Dies ist aber größer als das maximal darstellbare int (bei 32Bit) - nämlich std::numeric_limits< int >::max() == 2147483647. Das heißt, Du bekommst einen overflow. Das lässt das Programm zwar nicht crashen, aber die resultierende Folge ist dann nicht mehr die Collatz-Folge, sondern irgendwas anderes, was ggf. in einer Endlos-Loop landet.

Gruß
Werner

Slabic

Ok, danke.

Ich könnte die Zahlen als double einlesen, aber wie lässt sich für doubles am einfachsten bestimmen, ob gerade oder ungerade?
Ich könnte mir evtl. was zusammenbasteln, aber gibt's da vielleicht 'ne einfache Möglichkeit?

Oder du benutzt einfach 64 Bit Integers. Falls auch das nicht ausreicht benutzt du http://sourceforge.net/projects/cpp-bigint/ . Damit kannst du beliebig große Zahlen erstellen, allerdings dauert das Rechnen ein bischen länger.

knivil

Du kannst eine BigInteger-Bibliothek (z.B. gmp) nutzen, double koennten ungeeignet sein. Ich weiss aber nicht wie gross die Zahlen tatsaechlich werden. Btw: Meine laengste Kette ist 525 lang. (Ich habe weder C noch C++ genutzt.)

Slabic

Ah, danke.
Mit unsigned long int hat's geklappt.

Ja, 525 bekam ich auch, ist auch die richtige Antwort.