3N+1 Problem in Java
The 3N+1 problem is an abstract mathematical problem that is a conjecture (not yet proven). It is also known as Collatz problem. In this section, we will discuss the 3N+1 problem along with its Java program.
The task is to write a Java program that will read a positive integer from the user and will print the 3N+1 sequence starting from that integer. The program should also count and print the number of terms in the sequence.
Finding the 3N+1 Sequence
Given a positive integer, N, define the 3N+1 sequence starting from N as follows:
- If N is an even number, then divide N by two.
- If N is an odd number, then multiply N by 3 and add 1.
- Continue to generate numbers in this way until N becomes equal to 1.
Mathematically, we can define the 3N+1 problem as follows:
Let’s understand the problem statement through an example.
Suppose, N = 3, which is an odd number. According to the above rule, multiply N by 3 and add 1, we get N = 3*3+1 = 10. Therefore, N becomes an even number. Now, divide N by 2. It gives N = 10/2 = 5. Continue the process until N becomes equal to 1. Hence, the 3N+1 sequence will be 3, 10, 5, 16, 8, 4, 2, 1.
3N+1 Problem Algorithm
In order to compute the next term, the program must take different actions depending on whether N is even or odd. For the same, we required an if statement that will decide N is even or odd.
The one problem that remains is counting. Counting means that we start with zero, and every time we have something to count, we add 1. We need a variable (say counting) to do the counting.
We still have to worry about the very first step. How can we get a positive integer from the user? If we just read in a number, it’s possible that the user might type in a negative number or zero. If we follow what happens when the value of N is negative or zero, we’ll see that the program will go on forever, since the value of N will never become equal to 1 which is not compatible.
In this case, the problem is probably no big deal, but in general we should try to write programs that are foolproof. One way to fix this is to keep reading in numbers until the user types in a positive number.
The first while loop will end only when N is a positive number, as required. If N is not positive, ask the user to input another value. The problem arises if the second number input by the user is also non-positive. The if statement is only executed once, so the second input number is never tested.
With the while loop, after the second number is input, the computer jumps back to the beginning of the loop and tests whether the second number is positive. If not, it asks the user for a third number, and it will continue asking for numbers until the user enters an acceptable input.
Let’s implement the above algorithm in a Java program.
3n+1 Problem Java Program
ThreeNPlusOneProblem.java
Output:
