The 3n+1 Problem is known as Collatz Conjecture.
Consider the following operation on an arbitrary positive integer:
The conjecture is that no matter what value of the starting number, the sequence will always reach 1.
Observe that once it reaches 1, it will do like the following oscillation
1 -> 4 -> 2 -> 1-.> 4 ->2 ....
So, we see when it converges to 1, or does it?
We will investigate the problem in certain details as much as possible with occasional exercises and some computer problems ( python ).
Let's start by playing with some numbers and observe what is happening actually.
We will need this frequently. So let's make a little piece of code to do this.
n = 12
print(n)
while n > 1:
if n % 2 == 0 :
n = n//2
print (n)
else:
n = 3*n+1
print (n)This will give the output :
12 6 3 10 5 16 8 4 2 1
Now depending on the input of "n" you can get different sequences.
Exercise: Please copy this code and changing the input value of "n", play around with the sequences here. (Warning: Change it to python before implementing the code.) Eg: Do it for 7.
If you observe that different numbers requires different time to converge and that is the unpredictable which makes the problem so hard.
There are in total two possibilities:
Exercise: Find out the length of the sequence for all the numbers from 1 to 100 by a computer program. I will provide you the code. Your job is to find a pattern among the numbers.
c = 1
for n in range(2,101):
i = n
while i > 1:
if (i % 2 == 0):
i = i//2
c = c + 1
if i == 1 :
print( "The length of the sequence of {} is {}".format(n, c) )
c = 1
else:
i = 3*i+1
c = c + 1 Exercise: Consider the length of a sequence corresponding to a starting number "n' as L(n). Consider numbers of the form n = (8k+4) and n+1 = (8k+5), then find the relationship between L(n) and L(n+1). Try to observe the sequence of lengths for the numbers till 100 and predict the conjecture..
Exercise: Prove the conjecture that you discovered.
Hint:
8k+4 -> 2k+1 -> 6k+4 -> 3k+2
8k+5 -> 24k+ 16 -> 3k+2
Exercise: Prove that if n = 128k + 28, then L(n) = L(n+1) =L(n+2)
Hint:
128k+28 -> 48k+11 -> 81k+20
128k+29 -> 48k+11 -> 81k+20
128k+30 -> 81k+20
Exercise: Try to generalize the result for general k consecutive elements. Maybe you can take help of the computer to observe the pattern. Modify the code as per your choice.
You can try to do an easier problem and get the intuition as an exercise.
Exercise: Try to understand the behavior and the terminating number of the sequence if the rule is the following:
Consider the following operation on an arbitrary positive integer:
1. If the number is even, divide it by two.
2. If the number is odd, add 1.
Exercise: Try to understand the behavior and the terminating number of the sequence if the rule is the following:
Consider the following operation on an arbitrary positive integer:
1. If the number is even, divide it by two.
2. If the number is odd, add any 3.
Exercise: Try to understand the behavior and the terminating number of the sequence if the rule is the following:
Consider the following operation on an arbitrary positive integer:
1. If the number is even, divide it by two.
2. If the number is odd, add ANY ODD NUMBER.
Eager to hear your approaches and ideas. Please mention them in the comments.
Other useful links:-
