The 3n + 1 algorithm for a range

Question

Essentially the Collatz Conjecture.

Challenge requirements are here.

And here is my implementation in Java:

/* User: [email protected] Date: 21/03/15 Time: 19:40 */
public class ThreeNOneForRangeSolver {
 public int solveFor(int inputOne, int inputTwo) {
 int maximumCycleLength = 0;
 do {
 if (threeNOneValueFor(inputTwo) > maximumCycleLength) {
 maximumCycleLength = threeNOneValueFor(inputTwo);
 }
 inputTwo = inputTwo - 1;
 } while (inputTwo >= inputOne);
 return maximumCycleLength;
 }
 private static int threeNOneValueFor(int inputNumber) {
 int counter = 1;
 while (inputNumber != 1) {
 if (inputNumber % 2 == 0)
 inputNumber = inputNumber / 2;
 else
 inputNumber = 3 * (inputNumber) + 1;
 counter++;
 }
 return counter;
 }
}

and the test class:

/* User: [email protected] Date: 21/03/15 Time: 20:54 */
public class TestClass {
 public static void main(String[] args) {
 int one = 1;
 int two = 10;
 int result = new ThreeNOneForRangeSolver().solveFor(one, two);
 System.out.println(one + " " + two + " " + result);
 }
}

Any feedback is welcome.

• rolfl: As an exercise in Java 8 options, I also implemented your challenge in this question here: Streaming Collatz

Answer 1

Looks pretty good over all, but I have a few suggestions.

---

Don't call threeNOneValueFor twice when you could store it in a variable instead (or you can use Math.max). There's a chance that the compiler will optimize that, but that's a risky thing to assume.

---

The do-while seems a bit odd and unintuitive. I would go with a for loop instead.

int maxCycleLength = 0;
for (; inputOne <= inputTwo; ++inputOne) {
 maxCycleLength = Math.max(threeNOneValueFor(inputOne), maxCycleLength);
}
return maxCycleLength;

---

inputOne and inputTwo are pretty bad names. If you didn't already know what they were, the names would really mean much to you. Something like minimumValue, rangeBegin, etc might be better.

---

inputNumber is a pretty meh name as well. Considering the problem domain, I'd probably just call it n since that has a well defined meaning in this context and inputNumber could mean pretty much anything (it's an int parameter -- of course it's an input number).

---

I would call solveFor maximumCycleLength. solveFor has the same problem as inputNumber. You could be solving for pretty much anything that takes two inputs.

public int maximumCycleLength(int minN, int maxN) {

Seems significantly clearer as to what the method does. Couple that with a javadoc and it becomes very well explained:

/**
 * Calculate the maximum cycle length for the {@code 3n + 1} sequence over every {@code n} such that 
 * {@code minN <= n <= maxN}. Note that {@code maxN} must be greater than or equal to {@code minN}.
 * @param minN The beginning (inclusive) of the range over which to find the maximum cycle length.
 * @param maxN The end (inclusive) of the range over which to find the maximum cycle length.
 * @return The maximum cycle length of the {@code 3n + 1} sequence for all {@code n} in the provided range.
*/
public int maximumCycleLength(int minN, int maxN) {

(I would probably omit the @param and @return parts if I were to write this javadoc for my own code, but people tend to vehemently disagree with that.)

---

I'm probably getting pretty annoying at this point, but I don't much like the name threeNOneValueFor either. It doesn't find the valueFor; it finds the cycle length.

public int threeNOneCycleLength(int n) {

Considering it's on a class that already mentions the 3n + 1 problem, I would probably name it just cycleLength.

---

In it's current form, I would probably make solveFor static. There's no state, so there's no real reason in having it be an object. Typically I lean far more towards non-static than static, since it's much better to regret something being non-static than it is to regret having made it static, but in this case, since it's pretty much a mathematic function, I doubt it's ever going to manipulate state (hopefully not anyway).

In fact, I'd probably take this a step farther and have threeNOneCycleLength be public. It could be useful on it's own, and since both methods are static utility-like methods, there's not too much concern about having the class do too many things.

---

All in all (woo boring Saturday afternoons!), I might do something like this:

/**
 * Provides methods related to the {@code 3n + 1} sequence. 
 * 
 * @see <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>.
*/
public class ThreeNPlusOne {
 /**
 * Calculate the maximum cycle length for the {@code 3n + 1} sequence over every {@code n} such that 
 * {@code minN <= n <= maxN}. Note that {@code maxN} must be greater than or equal to {@code minN}.
 * 
 * @param minN The beginning (inclusive) of the range over which to find the maximum cycle length.
 * @param maxN The end (inclusive) of the range over which to find the maximum cycle length.
 * @return The maximum cycle length of the {@code 3n + 1} sequence for all {@code n} in the provided range.
 */
 public static int maximumCycleLength(int minN, int maxN) {
 int maxCycleLength = 0;
 for (; minN <= maxN; ++minN) {
 maxCycleLength = Math.max(maxCycleLength, cycleLength(minN));
 }
 return maxCycleLength;
 }
 /**
 * Calculates the cycle length for the provided {@code n}.
 * 
 * @param n The value of {@code n} for which the 
 * @return The cycle length for the provided {@code n}.
 */
 public static int cycleLength(int n) {
 int cycles = 1;
 while (n != 1) {
 n = (n % 2 == 0) ? n / 2 : 3*n + 1;
 cycles += 1;
 }
 return cycles;
 }
}

I'm not very happy with some of my namings (is "Collatz sequence" a recognized thing? I don't know what to call all of this), and some of the javadocs could use some better wording and whatnot, but hopefully this shows the structure and approach well enough.

Answer 2

• Save results of expensive calls. Currently, you calculate threeNOneValueFor twice in some cases when once would be enough.
• It is customary to write inputTwo--; instead of inputTwo = inputTwo - 1;.
• It is also customary to use curly brackets even for one line statements.
• You don't need brackets here: 3 * (inputNumber) + 1;. If you do want to add them for clarity, do it like this: (3 * inputNumber) + 1;
• Why is threeNOneValueFor static, but not solveFor? This seems inconsistent.

• Koray Tugay: I would assume compiler would optimize it. Actually I will check the byte code generated. I forgot it static, thanks for the great feedback.