The "3N + 1" problem
Task
Start with a positive whole number N.
If N is even, compute N/2→N.
If N is odd and greater than 1, compute 3N + 1→N.
Repeat this process until you get N = 1, and then stop.
Investigate what happens. Count how many steps you took to reach 1.
Remark.
It is not known whether this process stops for every whole number N. But within the range you will be working in, it always gets down to one.
Part 1
Investigate small numbers doing computations mentally.
Examples.
3 10 5 16 4 2 1 (7 steps)
4 2 1 (2 steps)
5 16 8 4 2 1 (5 steps)
Part 2
Write a calculator program on the TI-83/84 to carry out each step by pressing ENTER. Investigate bigger numbers.
Example of a program.
Variables,
N the number you work with;
C is 1 when N is odd and 0 when it is even;
S counts the steps.
Start with choosing a value of N and press,
0→S:0→C:value→N ENTER
Then press,
N-2int(N/2)→C:S+
1→S:C(3N+1)+(1-C
)N/2→N repeat ENTER until you see 1
Then in order to see the number of steps, press
S ENTER
Start with 7, and then with 23. Which number smaller than 100 requires the most steps?
Explanation of
the program above:
int(N) gives the
biggest integer in N.
We want C to
equal 1 when N is odd, and C to equal 0 when N is
even. What is the value of N-2int(N/2)?
If N is odd, N-2int(N/2)= N-(N-1) = 1
If N is even, N-2int(N/2)= N-N = 0
Here is a program for the 3N + 1 problem for the TI-83/84. To run it, select THREEN from PRGM, and enter a starting number N at the prompt. Wait, and you will see your number N together with the number of steps it took to reach 1.
PROGRAM:THREEN
:0→S
:Input N:N→M
:While N>1
:N-2int(N/2)→C
:C(3N+1)+(1-C)N/
2→N:S+1→S
:End
:Disp {M,S}
For more about the 3N+1 problem, see http://en.wikipedia.org/wiki/Collatz_conjecture: