The 3n+1 Problem | Learn Collatz Conjecture

The 3n+1 Problem is known as Collatz Conjecture.

Consider the following operation on an arbitrary positive integer:

If the number is even, divide it by two.
If the number is odd, triple it and add one.

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!

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:

It may occur a particular value occurs repeatedly i.e. after some time the sequence starts repeating. We define the last non-repeating digit to be the Terminating Number. The total number of numbers in the sequence until the terminating number is called the Length of the Sequence. For eg: For 5 the Terminating Number is 1 and the Length of the sequence is 6.
We may never end the sequence. In that case, the sequence never terminates.

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:-

Zonal Computing Olympiad 2018 Solutions-I

Here is the part 1 of solutions of Zonal Computing Olympiad 2018 of International Informatics Olympiad held in Tsukuba, Japan.

Problem 1: BIRTHDAY-CAKES

Before going to the solution/hints, it's always good if you re-read ( assuming you've already encountered the problem ) the problem statement once. And if you aren't aware of the problem statement, then it's only logical that you read it.
In any case, if you need to see the statement of the problem, you can find it here:

Zonal Computing Olympiad 2018 Questions.

Now, let us deal with the cases that constitute the problem. They are precisely k=0 and k=1

Case-I (k=0)
This case is pretty trivial. It can be solved with a bit of thought.
The algorithm we follow for this is:

Take each pair [a,b] denoting the permissible ranges of the cakes which a child can enjoy.
If a!=b, we append elements in range (a,b) { both inclusive } to an empty array declared beforehand.
If a==b, we append only a to the array.
Then we check if the array has any duplicate elements or not.
If it does, we print "BAD" , else we print "GOOD".

Case-II (k=1)
This case can be a lot simplified, the moment we realize the fact that INTERSECTIONS of the permissible ranges in which a child enjoys cakes can occur only in TWO ways.
ONE way being when the destination ( last element ) of a permissible range, is equal to the source ( first element ) of another permissible range.
{ In terms of interpretation in code, we will have a function dupli_1(arr) that returns 1 if any two consecutive elements in an array are equal. We will check if we have dupli_1(arr) = 1 for the array that contains all pairs (a,b) appended to it. }
ANOTHER way we can have fights is when an entire permissible range of cakes for some child is CONTAINED in the permissible range of cakes for another child, that is, for eg, the string "6" is 'entirely contained' in the array "567". ( In other words "6" is a substring of "567" ).

{ We use the contiguous substring concept here, and have a function dupli_2(array) that returns 1 if a string in the array is a contiguous substring of any other string in the same array.}
Now if both of the aforementioned functions return 1, we break and output "BAD" immediately, because the question gives us the liberty to move at max one child.
If anyone of those functions return 1, we act accordingly.
If dupli_1(arr)==1, we find out the particular element ; and take the minimum of the lengths of the two strings it occurs in, Assume this length to be g. Let w be the no. of elements, which are IN [1,..9] but NOT IN arr. ( These checks take linear time ).
If w >=g : we print "GOOD" , else we print "BAD"
Alternatively, if dupli_2(array)==1, we take g to be the length of the substring. And the deciding factor stays the same.

Hence, done.

Another approach to k=1:

We find any pair which intersects and let's think them to be i and i+1 and check if we can place i+1 in vacant places without overlaps via brute-force.

Zonal Computing Olympiad 2018 Questions.

These are the Questions from Zonal Computing Olympiad 2018 Exam of International Infromatics Olympiad held in Tsukuba, Japan.

Problem 1 : BIRTHDAY-CAKES
In a birthday party, there are C cakes and N children. There is also an integer k, given.
But since eating too much of cakes can give you toothache, each of the children have been prescribed by doctors to eat cakes that fall only within a specific interval (a,b) both inclusive.

If k = 0, you have answer if any of the students' ranges clash or not.
That is print "GOOD" ( without quotes ) if ranges do not clash and "BAD" ( without quotes ) if they will fight over their share of cakes.

If k=1, then you have a chance to stop them to stop them from fighting. You are allowed to move at max 1 child from his place and allot him a different range, PROVIDED THAT HE IS STILL ABLE TO HAVE THE SAME NUMBER OF CAKES AS HE WOULD HAVE HAD IN HIS PREVIOUS RANGE.
If you can prevent all the fights among the children, by 'moving' only one child , print "GOOD" ( without quotes ) , else print "BAD" ( without quotes ).

Input Format

A single line containing an integer t, denoting the number of test cases.
For each test case, input 3 space separated integers denoting N, C and k
For each test cases, C lines follow, denoting the ranges within which the children can enjoy cakes.

Output Format
t lines.
Each line containing either "GOOD" or "BAD" , as applicable.

Sample Testcases

Input

3
5 2 0
2 2
3 5
5 2 1
2 2
2 5
5 2 1
2 3
2 5

Output
GOOD
GOOD
BAD

Explanation

In the second test case, the child at [2,2] can be moved to [1,1] so that there are no fights anymore. Also, note that the child can still enjoy 1 cake as he would have done, had his position not been 'moved'.

Problem 2: IMPORTANT STRINGS

After having cakes at the birthday, you've got to study some English.
You may feel strings are a random collection of characters, but no they are important, and this is how.
Suppose you have a string S of length N consisting of X, Y, and Z .
A string is 'good' if it starts with a 'X' , ends with a 'Z' and has a length divisible by 3. ( That is permissible lengths are 3, 6, 9....and so on )

The importance of a string is the number of good string it intersects with.

Given the string S and a length k, find a string of length exactly k and minimize it's importance.
Your job is to print the minimum importance.

Input Format

The first line contains a single integer t, denoting the number of test cases.
Each test case contains two lines.
The first line of each test case contains two space separated integers denoting N and k.
The second line of each test case contains the string S.

Output Format
t lines.
Each line contains a single integer denoting the required minimum importance.

Sample Testcases

Input
2
9 3
X Y Z Z Y X X Y Z
4 2
Y X Y Z

Output
1
1

Explanation
In the first testcase, the good strings are in the ranges [0,2] [0,8] and [6,8]. ( 0-based indexing has been used )
Now consider the string at [5,8]. It is of length k=3. It intersects with only one good string [0,8] ; ( the entire one ).
That's the best we can do. So it has importance 1, and that's our desired output.

You may visit this link to see the solutions:- https://cheenta.com/zonal-computing-olympiad-2018-solutions-i/