The 3n + 1 Problem From UVa Online Judge - Help Needed in Understanding It

[DragonOsman]

Here's the link to the problem's page on the online judge site: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=36

Firstly, I need help in understanding two things here:
1. Do I have to try to determine what type of algorithm it is? Like how it says that the property of the algorithm isn't known and we're meant to analyze and say what the property is?
2. Given inputs i and j, how do I tell what n is? Is it the current number in a given sequence of numbers being printed in a while loop that has to stop once the printed number is 1? And I have to take inputs i and j and figure out the length of the cycle of n by continuously printing out numbers until a 1 is encountered? Also, do I check if the current number in i is odd or even and then either multiply it by 3 and add 1 (if it's odd) or divide it by 2 (if it's even)?

The reason I want to do this is that I want to get better at solving problems using code and also so I can get better at thinking algorithmically. And debugging isn't exactly my strong suit, so I'd like to fix that as well. Getting a better understanding of loops so I know when and how to write a for loop, for example, would also be good. So please help a fellow programmer (though I'm still learning) out here. Thanks in advance.

[ne555]

1. No. That's just context.
2. n in range(i,j)

> Is it the current number in a given sequence of numbers being printed in a
> while loop that has to stop once the printed number is 1?
¿what? explain yourself.

> by continuously printing out numbers until a 1 is encountered?
Look under `The Output', that's the only thing that you ought to print.
You should not print the sequence, but the maximum cycle length.
For example
i = 1, j = 4
the sequences are
n = 1 -> 1 -> length = 1
n = 2 -> 2, 1 -> length = 2
n = 3 -> 3, 10, 5, 16, 8, 4, 2, 1 -> length = 8
n = 4 -> 4, 2, 1 -> length = 3

As you can see, the maximum length is 8, for n=3. So you'll print
1 4 8

[DragonOsman]

If I don't print them, how will I know what the cycle-length of n is or what all of the numbers in the sequence are? Loop over them while putting them all into a vector, and then seeing what the elements of the vector are? I'd print them temporary just to see, and then take the printing code out to output only i, j, and the cycle-length of n.

So given the numbers the user inputs, we just take all of the numbers that fall within that range to be n, including the numbers themselves? And am I right in thinking that once you do 3n + 1 or n / 2 depending on whether n is odd or even, and then go into the loop, the said loop will continue until a 1 comes up?

[Arslan7041]

Here's the pseudocode for what the loop will look like to calculate cycle-length for a number n:

cycle length = 1; // set initial cycle-length to 1 as the number itself starts the cycle
while (n is not equal to 1)
{
     if(n is odd)
     {
          n is 3*n + 1;
          cycle-length++;
     }
     
    else
     {
         n is n/2;
         cycle-length++;
     }
}

By the end of the loop, you'll have the cycle length for n.

You have to do this for all n between i and j (including i and j), so the above while loop should be wrapped in a for loop going from i to j. As you do this, you need to find which n gives the greatest cycle-length. To do this, simply make a new variable called 'max_cycle_length" and set it to 0 outside the loops. Every time you encounter a cycle-length bigger than 'max_cycle_length', make that the new 'max_cycle_length' .

[ne555]

> what all of the numbers in the sequence are?
you don't need to know that.

> If I don't print them, how will I know what the cycle-length of n is
...
you may count them.

> Loop over them while putting them all into a vector
again, you don't need to know the sequence. However, if you think that you may solve the problem that way, you should simply try it.

> take all of the numbers that fall within that range to be n, including the
> numbers themselves?

determine the maximum cycle length over all integers between and including i and j.

> And am I right in thinking that once you do 3n + 1 or n / 2 depending on
> whether n is odd or even, and then go into the loop, the said loop will
> continue until a 1 comes up?
I can't figure out what are you asking.

¿are you worried that maybe you won't reach 1?

It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)

For the other part, it will be easier to understand you if you just write some code.

[DragonOsman]

I think I might be doing something wrong, since for me, maximum cycle-length of n is 9 when i is 1 and j is 4 (and ne555 said it'd be 8).

Here's my code:

// Osman Zakir
// 10 / 16 / 2016
// Program to determine the maximum cycle length of n
// for the 3n+1 problem

#include <iostream>

int get_value_i();
int get_value_j();
int determine_cycle_length_n(int i, int j);
void keep_window_open();

int main()
{
	int i = get_value_i();
	int j = get_value_j();
	int cycle_length_n = determine_cycle_length_n(i, j);
	std::cout << i << ", " << j << ", " << cycle_length_n << "\n";
	keep_window_open();
}

int get_value_i()
{
	using namespace std;
	cout << "Enter an integer: ";
	int num = 0;
	cin >> num;
	cin.ignore(32767, '\n');
	return num;
}

int get_value_j()
{
	using namespace std;
	cout << "Enter another integer: ";
	int num = 0;
	cin >> num;
	cin.ignore(32767, '\n');
	return num;
}

int determine_cycle_length_n(int i, int j)
{
	int cycle_length = 1, max_cycle_length = 0, n = 0;
	for (int index = i; index < j; index++)
	{
		n = index;
		while (n != 1)
		{
			if (n % 2 != 0)
			{
				n = (3 * n) + 1;
				cycle_length++;
			}
			else
			{
				n /= 2;
				cycle_length++;
			}
			if (cycle_length > max_cycle_length)
			{
				max_cycle_length = cycle_length;
			}
		}
	}
	return max_cycle_length;
}

void keep_window_open()
{
	using namespace std;
	cin.clear();
	cout << "Please enter a character to exit:\n";
	char ch;
	cin >> ch;
}

Here's my output for each run of the program (note: I'm running it directly from the command-line, and when I saw that the maximum cycle length was 9 for i = 1 and j = 4, I made a little change and recompiled it, but then I got the same result again):

C:\Users\Osman\programming\3n+1_problem\3n+1_problem>3n+1_problem
Enter an integer: 1
Enter another integer: 10
1, 10, 62
Please enter a character to exit:
l

C:\Users\Osman\programming\3n+1_problem\3n+1_problem>clang++ -std=c++14 -Wall -pedantic 3n+1_problem.cpp -o 3n+1_problem.exe

C:\Users\Osman\programming\3n+1_problem\3n+1_problem>3n+1_problem
Enter an integer: 1
Enter another integer: 100
1, 100, 3118
Please enter a character to exit:
l

C:\Users\Osman\programming\3n+1_problem\3n+1_problem>3n+1_problem
Enter an integer: 1
Enter another integer: 4
1, 4, 9
Please enter a character to exit:
l

C:\Users\Osman\programming\3n+1_problem\3n+1_problem>clang++ -std=c++14 -Wall -pedantic 3n+1_problem.cpp -o 3n+1_problem.exe

C:\Users\Osman\programming\3n+1_problem\3n+1_problem>3n+1_problem
Enter an integer: 1
Enter another integer: 4
1, 4, 9
Please enter a character to exit:
l

[ne555]

you need to reset `cycle_length' for each number.

int maximum_cycle_length(int start, int end) //use meaningful names for variables
	int max = 0;
	for(int K=start; K<=end; ++K){ //all integers between and including i and j. (¿didn't you asked me precisely that?)
		int cycle_length = determine_cycle_length(K); //¡yay, functions!
		if(cycle_length>max)
			max = cycle_length;
	}
	return max;
}

int determine_cycle_length(int n){
	int cycle_length = 1
	while( n!=1 ){
		//...
	}
	return cycle_length;
}

iirc, you'll get Time Limit Exceeded. Here's a tip: when you calculate the cycle length of 3, you also calculate the cycle length of 10, 5, 16, 8, 4, 2, 1, i.e., of all the numbers in its sequence.


Apart

int get_value_i(); //¿are you serious? ¿what's the difference between these two functions?
int get_value_j();

void keep_window_open(); //I thought you say that you were «running it directly from the command-line»... 

[DragonOsman]

I hope you didn't have to help me that much since I'm the one trying to solve it, but thanks anyway. I got it to work.

The reason I used separate functions to get the inputs for i and j was that I don't know how to return a value by reference and had to call those functions to get the values for i and j.

And as for the function for keeping the window open; that's really just in case I run the program by double-clicking the .exe file. Without that function there, when I run a program like that, I can't see the full output before the window closes. In a program that only prints to the screen, the console window would just flash on my screen and I won't get to see a thing. In a program like this one, I won't be able to see the result before the window closes.

And yeah, the time limit is 3 seconds. But when does it start? They shouldn't know I'm trying to solve it, should they? Or does the site know somehow?

Here's the updated code:

// Osman Zakir
// 10 / 16 / 2016
// Program to determine the maximum cycle length of n
// for the 3n+1 problem

#include <iostream>

int get_value_i();
int get_value_j();
int determine_cycle_length_n(int n);
int maximum_cycle_length_n(int start, int end);
void keep_window_open();

int main()
{
	int i = get_value_i();
	int j = get_value_j();
	int cycle_length_n = maximum_cycle_length_n(i, j);
	std::cout << i << ", " << j << ", " << cycle_length_n << "\n";
	keep_window_open();
}

int get_value_i()
{
	using namespace std;
	cout << "Enter an integer: ";
	int num = 0;
	cin >> num;
	cin.ignore(32767, '\n');
	return num;
}

int get_value_j()
{
	using namespace std;
	cout << "Enter another integer: ";
	int num = 0;
	cin >> num;
	cin.ignore(32767, '\n');
	return num;
}

int maximum_cycle_length_n(int start, int end)
{
	int maximum_length = 0;
	for (int i = start; i < end; i++)
	{
		int cycle_length = determine_cycle_length_n(i);
		if (cycle_length > maximum_length)
		{
			maximum_length = cycle_length;
		}
	}
	return maximum_length;
}

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

void keep_window_open()
{
	using namespace std;
	cin.clear();
	cout << "Please enter a character to exit:\n";
	char ch;
	cin >> ch;
}

By the way, for C programs, when I compile using Clang (I found a good way to not get a Linker error about the iostream header, so I can do it from the Command Prompt now), it gives me a warning about a newline missing at the end the file (after the last closing brace). Why does it want a newline at the end of the file?

Edit: I submitted it just now.

But I'm worried about the compiler and ISO Standard version they're using for C++. Mine was generated by Clang using the 2014 standard, but they have GNU GCC with the 2011 standard as the highest. I also used Microsoft's Visual C++ compiler to do it once or twice as well, but mainly I used Clang for it. What'll happen with this?

Edit2: I submitted it, but it was rejected for being incorrect. Should I ask them what went wrong?

[Arslan7041]

Edit2: I submitted it, but it was rejected for being incorrect. Should I ask them what went wrong?

Maybe they want the input-output format to be EXACTLY as shown in the instructions.

[Arslan7041]

If n is odd, you can actually do two steps at once. Since 3*n+1 is guaranteed to result in an even number, you can divide by 2 immediately, and increment 'cycle_length' by 2.

if (n % 2 != 0)
{
	n = (3*n+ 1)/2
	cycle_length += 2;
}

[ne555]

> But I'm worried about the compiler and ISO Standard version they're using for C++.
use the -std=c++11 flag
they will tell you if the code doesn't compile, depending on the case, you may need to go back to -std=c++98

> And yeah, the time limit is 3 seconds. But when does it start? They shouldn't
> know I'm trying to solve it, should they? Or does the site know somehow?
they do compile and run your program, and later compare its output with a correct one.
http://stackoverflow.com/questions/5161193/bash-script-that-kills-a-child-process-after-a-given-timeout

> Edit2: I submitted it, but it was rejected for being incorrect. Should I ask
> them what went wrong?
>> Maybe they want the input-output format to be EXACTLY as shown in the
>> instructions.
precisely. No commas (,) between the numbers, not asking the user for input.
Besides that, you are only processing one test case.

while( std::cin>>i>>j ){
	//solve the case
}

Also

The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

you need to consider the case were i>j. For example, for 10 1 input, you need to output 10 1 20



> it gives me a warning about a newline missing at the end the file
it doesn't matter
http://stackoverflow.com/questions/72271/no-newline-at-end-of-file-compiler-warning

> The reason I used separate functions to get the inputs for i and j was that I
> don't know how to return a value by reference and had to call those functions
> to get the values for i and j.

i = get_value();
j = get_value();

[DragonOsman]

Oh, okay, thanks for this.

I took care of the case where n would become even after doing 3n+1, but I'm not sure how to handle a case where i > j.

And I guess it should go inside the for loop in maximum_cycle_length_n();

This is the code I have right now:

// Osman Zakir
// 10 / 16 / 2016
// Program to determine the maximum cycle length of n
// for the 3n+1 problem

#include <iostream>

int determine_cycle_length_n(int n);
int maximum_cycle_length_n(int start, int end);
void keep_window_open();

int main()
{
	using namespace std;
	int i = 0, j = 0;
	while (cin >> i >> j)
	{
		int cycle_length_n = maximum_cycle_length_n(i, j);
		cout << i << " " << j << " " << cycle_length_n << "\n";
	}
	keep_window_open();
}

int maximum_cycle_length_n(int start, int end)
{
	int maximum_length = 0;
	for (int i = start; i < end; i++)
	{
		int cycle_length = determine_cycle_length_n(i);
		if (cycle_length > maximum_length)
		{
			maximum_length = cycle_length;
		}
	}
	return maximum_length;
}

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

void keep_window_open()
{
	using namespace std;
	cin.clear();
	cout << "Please enter a character to exit:\n";
	char ch;
	cin >> ch;
}

Edit:
What's meant by sorting an array in one integer field, by the way?

And I was getting the warning about the missing newline at the end of the file from Clang when compiling a C program. Not with Clang++ when compiling a C++ program.

[ne555]

> What's meant by sorting an array in one integer field, by the way?
¿ah? ¿what are you talking about?


> I'm not sure how to handle a case where i > j.
In that case you may call the function as maximum_cycle_length_n(j, i);

[DragonOsman]

For the one integer field thing, I was talking about this:

Create an array of records and write some code to sort that array on one integer field.

From How To Stuff Works - C. I'm also taking Harvardx's CS course, and on there, they recommend that as one of three recommended readings.

As for the max cycle length function, I should like it in main in code like this if i > j?

if i > j
    determine max cycle length of n with j and i in passed to it in reverse order

Edit: I added that while loop in main() and I even took out the keep_window_open() function because I felt that maybe that could be causing part of the problem, but Uva still says it's the wrong answer. What do I do? Just give up?