The 3n + 1 problem

[stefoka]

The 3n + 1 problem




Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints.

Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
Output

For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input.
Sample Input

1 10
100 200
201 210
900 1000
Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

WHAT AM I DOING WRONG? :)

  #include<iostream>
#include<algorithm>

using namespace std;

int main()
{
	int a;
	cin>>a;
	int b;
	cin>>b;
	int max=INT_MIN;
	int n;
	
	
	for (int d=a;d<=b;d++)
	{	
		
		while (d!=1)
		{
			if (d%2==0)
			{
				d=d/2;
			}	
			else
			{
				d=(d*3)+1;
			}
			n++;
				
		}
		if (n>max)
		max=n;
		
	}
	cout<<"Nomer: "<<n<<endl;
	
	return 0;
}

[hyperfine]

You need to initialize n.

[giblit]

while(n != 1)
{
    if(n & 1) //odd same as n % 2 == 1
        d = d * 3 + 1;
    else //even
        d >>= 1; //divide by  2 same as d /= 2;
}

Notice how I used n and not d. If you modify d it will throw your for loop off.

[stefoka]

I have already initialized it.

[shadowCODE]

#include <iostream>
using namespace std;

int cycleLength(int);
static int n = 1;

int main()
{
	int a,b;
	cin>>a>>b;
	int max = 0;

	for(int i = a; i <= b; i++)
	{
		int length = cycleLength(i);
		if(length > max)
			max = length;
		n = 1;
	}
	cout<<max<<endl;

	system("pause");
	return 0;
}

int cycleLength(int x)
{
	if(x != 1)
	{
		n++;
		if(x%2 == 0)
			cycleLength(x/2);
		else
			cycleLength(x*3 + 1);
	}
	return n;
}

[stefoka]

I need an explanation of my mistakes, not a new better code. But thank you :)

[shadowCODE]

Ok. Every thing in your code looks good except for 3 things that have already been sorted out.

First, you needed to initialize n which you have already done. Assume you know why.
The question is where? Put n = 0 just after the for loop before the while.
So that n is = for every d.

Secondly, after initializing n, you run to an infinite for loop. Lets see why

we know that b >= a,
then, d runs from a to b,

the manipulations in the while loop ensures that d gets smaller to get to 1 after a finite steps.

But then, you have the loop, for (int d=a;d<=b;d++) .
Since d is always getting smaller to 1, it never reaches b. Hence the infinite loop.

insert int x = d inbetween the for and the while .
Then use x instead of d in the while loop.

Lastly, you do the check if (n > max) .
In line 12 , you have max = 2147483647 //INT_MAX
do you think n will ever be greater than that number?

[48T7M4Gy]

You are using d as the the index in the loop but inside the loop you are modifying its value. Change for( d = etc, etc) to for( int j = etc, etc)

... and set d=i in the loop.

ie Same as what giblit wrote!

[stefoka]

Thank you. I finally solved it.