Thread: Help a noob. :(

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.[/SIZE]

I just need help with understanding the problem. What does "maximum cycle length over all numbers between i and j, including both endpoints" mean? X_X

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's with the output?

It means you do
for ( loop = i ; loop <= j ; loop++ )

Then for each value of loop, you count how many iterations it takes for 3n+1 to reach 1

You keep the maximum, and print it out at the end.

So if you've got the code to do it once, in main, then make a function out of it where you specify the endpoints as parameters.
A development process

Then add another bit of code to main to loop reading from a file/stdin to get more end points.

Originally Posted by CommonTater

Ok... post your code... lets see what you've got...

Code:

int get_int()
{
	int x;
	scanf("%d", &x);
	return x;
}

int even(num)
{
	num = num/2;
	return num;
}

int  odd(num)
{
	num = (3*num) + 1;
	return num;
}

int cycle(i, j, count)
{
	if(i==j)
		return count;
	else if(j%2==0)
		return cycle(i, even(j), count + 1);
	else
		return cycle(i, odd(j), count + 1);
}

main()
{
	int i = get_int();
	int j = get_int();
	int x = cycle(i, j, 1);
	printf("%d %d %d", i, j, x);
}

The output I receive doesn't match the output in the examples. When I input 1 and 10, I get 7. But when I input 1 and 22, I get 16, which is truly the cycle of 22. Now I reckon "maximum cycle length for integers between andincluding i and j" must mean another thing. But when I try getting the maximum cycle length of the numbers between i and j, I get a very big number which doesn't match the examples either. What must I do?

Firstly, the basic shell for a C program is

Code:

int main( void ) {
   /* your code goes here */
   return 0;
}

because main has to be a function that returns an integer. See this explanation.

Now, you've solved the problem for one integer. What you need to do now is to loop through all the integers in the range and solve for all of them in turn.

The output I receive doesn't match the output in the examples. When I input 1 and 10, I get 7. But when I input 1 and 22, I get 16, which is truly the cycle of 22. Now I reckon "maximum cycle length for integers between andincluding i and j" must mean another thing. But when I try getting the maximum cycle length of the numbers between i and j, I get a very big number which doesn't match the examples either. What must I do?

Ah, I see where you're going wrong. You've misunderstood the question.

Let's say you do the 3n+1 process just on the number 7. You'll go 7 - 22 - 11 - 34 - 17 - 52 - 26 - 13 - 40 - 20 - 10 - 5 - 16 - 8 - 4 - 2 - 1. That's a cycle length of 17. What you want to know is, if you do the 3n + 1 problem for all the numbers between 1 and 10 in turn, which of those numbers gives you the longest cycle length. Those should be your "i" and "j" variables. You need to loop from 1 to 10 (or whatever your i and j will be), calculate the cycle length for all of those and keep track of the longest.