Collatz Conjecture

[Kyon]

After fiddling around with the Collatz Conjecture model I made in Mathematica, I realized that it can be used to map natural numbers to special coordinates - Collatz Coordinates. These coordinates would consist of two parts: A list of "turns" and a "length".
Turns: We see that in a graph with the properties described by Collatz produces a new series of x*2^n for every x that is uneven. Therefore, every time a number is reached one can choose to take the turn or continue on the regular 2^n pattern. The actual turn coordinate that is added to the list is a number. If you took the x-th turn in the current 2^n pattern (starting with x=0), x is added to the end of the list. For example, to get to 13, you take the 0th turn and then the 1st turn.
Length: Once you've found the pattern in which your number lies (taking all the turns), the number you are mapping to Collatz Coordinates can only be on a 2^n pattern. n is the length.

Example:
13 is mapped to: {0,1,0}
21 is mapped to: {1,1}
32 is mapped to: {5} (there are no turns to take here)

I - having turned into the Mathematica fan that I am - wanted to go on right away with writing a Mathematica function to find Collatz Coordinates and to get the number back. I - not being really proficient with using Mathematica - quickly gave up.
So I made an horribly failed attempt at doing it with C++. (Note: This next code is horribly inefficient. The cout's are only there because I had some loop problems and wanted to see the output directly.)

#include <vector>

#define EVEN(x) (!(x&1))

using namespace std;
void CollatzCoordinates(unsigned x)
{
    cout << x << ":  ";
    std::vector<unsigned> out;

    unsigned n = 0;
    while(EVEN(x)){x/=2;n++;}
    out.push_back(n);

    x=(3*x+1)/2;
    unsigned z=0;
    while(x!=1 && x!=2 && x!=4 && x!=8)
    {
        if(!((x-1)%3)) z++;
        if(EVEN(x))       x/=2;
        else {out.push_back(z); z=0;x=3*x+1;}
    }

    // PRINT
    for(unsigned i=0;i<out.size();i++) cout << out[i] << ((i!=out.size()-1)?" - ":"");
    cout << endl << flush;
    // END_PRINT
}

Do note that the list has to be inverted after the process.

However, every time I execute this code, it seems to throw away a turn. Specifically, it throws away any turn on 2^n. (like 16->5 or 64->21) It also seems to have some strange outputs on other coordinates.

I've worked on this code for God knows how much too long and can't seem to find the problem. Do any of you?

Thanks in advance.


EDIT: Fixed a little typo.

[Kyon]

I figured it out myself. The problem was, well, just about everything. The main problem was that the last turn wouldn't be added, because the loop was exited before doing so (hence the if(x==4) in the next code). The weird behavior was because I forgot the fact that I should only increment n when !((n-1)%3) AND EVEN(n) (I forgot the latter part). (So n would also increment on, for example, 13 (because !((13-1)%3)==TRUE). The final code (with the printing) is:

void CollatzCoordinates(unsigned x)
{
    cout << x << ":  ";
    std::vector<unsigned> out;

    unsigned n = 0;
    while(EVEN(x)){x/=2;n++;}
    out.push_back(n);

    n = 0;
    if(x!=1)
    {
        while(x!=4)
        {
            if(EVEN(x))    {if(!((x-1)%3)) n++;
                            x/=2;
                            if(x==4)       {out.push_back(n);n=0;}}
            else           {out.push_back(n);n=0;x=(3*x+1)/2;}
        }
    }

    // PRINT
    cout << "Length: " << out[0];
    if(out.size()>1){cout<<"\tTurns: ";for(unsigned i=out.size()-1;i>1;i--) cout << out[i] << (i!=2?" - ":"");}
    cout << endl << flush;
    // END_PRINT
}

I don't think anyone even noticed this thread, but if you did and you worked on it. Thanks anyways.

[ceruleus]

what's the difference between

unsigned n = 0;

and

unsigned int n = 0;

?

[Kyon]

None. Both are allowed by the standard. Unsigned is shorter to write, so I tend to use that one. If you want to be entirely clear, you should use unsigned int. But their functionality is the same.

[ceruleus]

I read somewhere that:

char c = 0;
signed char c = 0;
unsigned char c = 0;

are three unique things. TBH if that's true I still don't understand it. (The = 0 is insignificant I just can't not initialize lol). So anyway I was just wondering if the same is true with ints.

[firedraco]

I believe a char by itself is either signed or unsigned, depending on the compiler settings (although I haven't read the standard on that so...)