Not sure what this exercise is asking for - Help

[Arslan7041]

Take a look at EXERCISE 20 at this link: https://en.wikibooks.org/wiki/C%2B%2B_Programming/Exercises/Iterations

I've reproduced it below:

EXERCISE 20

u(n) is defined with:

u(0) = a (a is an integer)
if u(n) is even then u(n+1)=u(n)/2, else u(n+1)=3*u(n)+1

Conjecture: For all value of a, there exists a value N such that u(N)=1.

a)Write a program that asks the user to type the value of an integer a and writes all the values of u(n) from n=1 to n=N.


I understand everything up until the conjecture. Im not exactly sure how N is possible if a is NOT even. How can u(n) (where n=N and a is odd) be 1 when each successive number in the pattern is multiplied by 3 and then incremented by one?


I know the solutions are given but I purposely did not look at them yet. I want to try to do this myself. I just need to understand the question first.

[Arslan7041]

There's also a part b) to this problem (check the link), but lets not worry about that yet.

[Ganado]

I'll admit it, the notation of that wikibook problem confused me and looks a bit strange.

But basically, you start off with any number, the wikibook calls this number "a".
Let's say a = 6.
So, since u(0) = 6, then u(1) = u(0)/2, in other words u(1) = 6/2 = 3.
Then you apply this again, u(1) = 3, so u(2) = 3*u(1) + 1 = 3*3+1 = 10.
Then you'd apply it again for u(3)... etc etc.

So the first 3 terms in the sequence are [6, 3, 10]. Keep going this process until the next term in the sequence is 1, then you can stop. (Until it becomes one, however, you are not allowed to eat or sleep, so you better work fast!)

If you want an explanation in English, look at this excerpt from https://en.wikipedia.org/wiki/Collatz_conjecture :

Wikipedia wrote:

Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called "Half Or Triple Plus One", or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness.

Edit: Attempted my own explanation using the Wikibook terminology (see top of post)

How did this Collatz guy even come up with this? Look at the fractal on the wiki page, amazing... it looks like a Mandelbrot fractal... BUT IT'S NOT!!11
PS: Mandatory xkcd link: https://xkcd.com/710/

[Arslan7041]

Ah, now I see.

While we're here, can you also explain part b to me:

b) Write a program that asks the user to type a value M and computes the value of a from 2 and M that maximizes the value of N. This value is called A. The program must write the value of A and N.

Totally lost with this one.

[Arslan7041]

Ok, here's what I got for part a (still haven't looked at solutions).

#include <iostream>

using namespace std;

int u(int a, int n)
{
    if(a<=1)
    {
         cout << "u(" << n <<  ") = " << a << endl;
    }
    else if (a%2==0)
    {
        cout << "u(" << n <<  ") = " << a << endl;
        n++;
        u(a/2, n);
    }

    else if (a%2!=0)
    {
        cout << "u(" << n <<  ") = " << a << endl;
        n++;
        u(3*a + 1, n);
    }

}

int main()
{
    int a, n=0;

    cout << "Enter an integer: " << flush;
    cout << endl;
    cin >> a;

    u(a, n);

   cin.get();

}

[Arslan7041]

Now, can someone explain to me what part b is asking for.

I've reproduced it below:


b) Write a program that asks the user to type a value M and computes the value of a from 2 and M that maximizes the value of N. This value is called A. The program must write the value of A and N.

[Ganado]

I think it's asking you to iterate from u(2) to u(M), and see which value between 2 and M produces the longest chain of the u(a?) functions.

For example, for a = 6, the process has to be repeated 8 times (9 times if you count the end) for the result to get back to the 1, and the highest number that n becomes is 16.

For a number higher than 6, it might take more or less iterations to get to 1 (a = 27 requires 111 steps to get to 1, apparently). The program wants you to keep track of which number from a = range[2, M] requires the most iterations to get back to 1, and track the highest value that sequence achieves.

The same concept as finding the biggest element in an array should apply here.

[Arslan7041]

Ok, here's part b below for anyone who is interested:

#include <iostream>

using namespace std;

int u1(int, int);
void u2(int, int);

int main()
{
    double a, M, N, A;
    int iterations = 0;

    cout << "Enter an integer 'a' greater than or equal to 0: " << flush;
    cin >> a;
    while(a<0 || !cin)
    {
        cin.clear();
        cin.ignore(1000, '\n');
        cout << "Error! Please enter an integer greater than or equal to 0: " << flush;
        cin >> a;
    }

    //cout << endl;

    cout <<  "Enter an integer 'M' greater than or equal to " << a << ": " << flush;
    cin >> M;
    while(M<a || !cin)
    {
        cin.clear();
        cin.ignore(1000, '\n');
        cout << "Error! Please enter an integer greater than or equal to " << a << ": " << flush;
        cin >> M;
    }

    cout << endl;

    for(int i=a; i<=M; i++)
    {
        N = u1(i, 0);
        if(N==0)
            A==i;

        if(N > iterations)
        {
            iterations = N;
            A = i;
        }
    }

    u2(A, 0);

    cout << "\n";
    cout << "Number that requires the most iterations to return to one: " << A << endl;
    cout << "The number of iterations " << A << " took to return to one: " << iterations << " iterations" << endl;

   cin.get();

}

int u1(int a, int n)
{
    if(a==1 || a==0)
    {
        return n;
    }
    else if (a%2==0)
    {
        n++;
        u1(a/2, n);
    }

    else if (a%2!=0)
    {
        n++;
        u1(3*a + 1, n);
    }

}

void u2(int a, int n)
{
    if(a==1 || a==0)
    {
        cout << "u(" << n <<  ") = " << a << endl;
    }
    else if (a%2==0)
    {
        cout << "u(" << n <<  ") = " << a << endl;
        n++;
        u2(a/2, n);
    }

    else if (a%2!=0)
    {
        cout << "u(" << n <<  ") = " << a << endl;
        n++;
        u2(3*a + 1, n);
    }

}