Tuesday, January 11, 2022

3N+1 Problem

     This topic is very different than many of my previous topics. It is about math!! First I am not a mathematician and not a big fan of fan. It is hard.


The story started here when I saw this video. I love this channel and I have watched most of its video.


I was excited to know that such simple problem has not been solved. So I decided to start to play with it.
No No I have not solved it. But I came with nice graph that it might be useful.



First let's mention the rule here, take any positive integer number:

        if number is odd then multiply it by 3 and add 1. 

            N>3N+1

        if number is even then divide it by two.

  let us take some examples:

        7 :  22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
       11:  34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 

 easy !

  Now let us focus only on the last digit of any number not the whole number. Let's rewrite the above number again:

        7 :  22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
       11:  34, 17, 52, 26, 13, 40, 20, 105, 168421 
       

  

We can deduce a sequence here:

    A digit ends with 1 will always gives a digit ends with 4. because 



  We can apply same technique to other odd numbers and we get the following table:


1x3 + 14
3x3 + 10
5x3 + 16
7x3 + 12
9x3 + 18

   

  For even numbers; we can deduce them using the following tables:


2/21
126
2211
3216
4221
5226
6231
7236
8241
9246
10251


4/22
147
2412
3417
4422
5427
6432
7437
8442
9447
10452


6/23
168
2613
3618
4623
5628
6633
7638
8643
9648
10653


8/24
189
2814
3819
4824
5829
6834
7839
8844
9849
10854


0/20
105
2010
3015
4020
5025
6030
7035
8040
9045
10050


Now we have all the information we need to draw a state machine diagram for these numbers:





you can verify this with any number generated by the 3N+1 problem and the sequence will always be valid.


What can we see in this graph:

    1- The blue lines are where we divide by 2 hence reduce the value. The red lines are where we multiply by 3 and add 1 hence increase the value.

    2- Blue lines are 10 and red lines are only 5. That means overall the value should decrease even if it is increased for sometime.




    3- Loops with same number of arrows of different colors leads to increase in values. for example loop {6,3,0,5,6,3,0,5,6...} but the loop will break as divide by two at a moment will give a number ended by 8.

   4- Loops {6,3,0,5,6,...} can never be broken except at number 6 only. Loops {9,8,9,8...} can be broken at number 8 only. Loops can only be broken at even numbers only.

   
   5- Loop {1,4,2,1,4,2,....} there are two blue lines and one red line. The result is 1 when n =1 that is why it loops forever.

   


 6- If someone can prove that loop {6,3,0,5,6} can be repeated forever which I do not believe it is possible, as each time you multiply you get the following assuming you do not loop in the Zero loop.

which is
The number will either loop in Zero or get out in 6 to 8 because incrementing by 10/4 is 2.5 

 Similar rules is applied to {8,9} and {4,7,2,1} loops. remember only balanced loop is {4,2,1} when n is {4,2,1}.   



7- If you get out of a loop then to get in again you pass one or more blue lines. if you are in loop 6 and move to loop 8 and come back to 6 using worst path you need to move on {6, 8, 9, 4, 7, 2, 6} which is 2 red lines and five blue lines. The number is ALWAYS reduce.


So you have thre main rules guide the behavior here.


A- You cannot loop in one loop forever except {4,2,1}.

B- Jumping from one loop to another reduces the value.

C- Moving back and forth from loop 6 to loop 8 requires passing on loop 4. It is a Must.


So as value gets smaller and passes via 4 from 8 that explains the 4 ,2 ,1.




I know this is NOT a scientific mathematical proof. But it explains to certain extend the behavior of this formula.









No comments:

Post a Comment