Collatz Conjecture

Intro

The Collatz Conjecture or 3x+1 problem can be summarized as follows:

Take any positive integer n. If n is even, divide n by 2 to get n / 2. If n is odd, multiply n by 3 and add 1 to get 3n + 1. Repeat the process indefinitely. The conjecture states that no matter which number you start with, you will always reach 1 eventually.

Examples

Starting with n = 12, the steps would be as follows:

1. 12
2. 6
3. 3
4. 10
5. 5
6. 16
7. 8
8. 4
9. 2
10. 1

Resulting in 9 steps. So for input n = 12, the return value would be 9.

Task

Given a number n, return the number of steps required to reach 1.

The Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include "collatz_conjecture.h"
#include <stdexcept>

namespace collatz_conjecture {
int steps(int test) {
if(test<=0)throw std::domain_error("error");

int tmp{};
int tmp2{};
for (tmp = test; tmp > 1;) {
    if (tmp & 0x01) {
    tmp *= 3;
    tmp += 1;
    } else {
    tmp /= 2;
    }
    tmp2++;
}
return tmp2;
}
} // namespace collatz_conjecture

1
2
3
4
5
6
7
8

#if !defined(COLLATZ_CONJECTURE_H)
#define COLLATZ_CONJECTURE_H

namespace collatz_conjecture {
    int steps(int);
}  // namespace collatz_conjecture

#endif // COLLATZ_CONJECTURE_H

Comments