{"id":1811,"date":"2014-05-04T18:58:12","date_gmt":"2014-05-04T17:58:12","guid":{"rendered":"http:\/\/www.blopig.com\/blog\/?p=1811"},"modified":"2014-05-15T10:28:13","modified_gmt":"2014-05-15T09:28:13","slug":"opig-algorithm-club-problem-1-the-3n1-problem","status":"publish","type":"post","link":"https:\/\/www.blopig.com\/blog\/2014\/05\/opig-algorithm-club-problem-1-the-3n1-problem\/","title":{"rendered":"OPIG Algorithm Club Problem #1: The 3n+1 problem"},"content":{"rendered":"<p>In the first meeting of the OPIG Algotirhm Club, we tackled the problem <a title=\"Problem 3*n+1\" href=\"http:\/\/www.spoj.com\/problems\/PROBTNPO\/\" target=\"_blank\">3n+1<\/a> from the Sphere Online Judge (<a title=\"Sphere Online Judge\" href=\"http:\/\/www.spoj.com\/\" target=\"_blank\">SPOJ<\/a>).<\/p>\n<p style=\"text-align: center\"><strong>\u00a0&#8212;Background &#8212;<\/strong><\/p>\n<p>The problem relates to the <a title=\"Collatz Conjecture\" href=\"http:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture\" target=\"_blank\">Collatz conjecture<\/a>. Before describing the conjecture, let us define a very simple recursive relation:<\/p>\n<ul>\n<li>If a number is odd, multiply it by 3 and add 1 (hence 3n+1).<\/li>\n<li>If a number is even, divide it by 2.<\/li>\n<\/ul>\n<p>The Collatz conjecture states that for any given integer, you can repeat this recursion indefinetely and you will always reach the number 1.<\/p>\n<p>The 3n+1 problem requires yet another concept which is the cycle length (i.e. the number of times you have to repeat the recursion for a given number until you reach 1).<\/p>\n<p style=\"text-align: center\"><strong>&#8212; Goal &#8212;<\/strong><\/p>\n<p>The aim of the problem is: given 2 integers\u00a0<strong>i\u00a0<\/strong>and\u00a0<strong>j<\/strong>, find the number with the highest cycle length that lies in the interval comprised between the 2 integers (them included).<\/p>\n<p style=\"text-align: center\"><strong>&#8212; Important Issues &#8212;<\/strong><\/p>\n<p>Two things are worth mentioning before attempting to implement this problem:<\/p>\n<ul>\n<li>\u00a0<strong>i\u00a0<\/strong>could be either greater than or lesser than\u00a0<strong>j<\/strong>.<\/li>\n<li>Despite the fact that the description of the problem states that all operations can be performed using\u00a0<em>int<\/em>, there are certain inputs between 100,000 and 1,000,000 that violate that statement.<strong>\u00a0<\/strong><strong><br \/>\n<\/strong><\/li>\n<\/ul>\n<p style=\"text-align: center\"><strong>&#8212; Implementation &#8212;<\/strong><\/p>\n<p>A simple solution can be implemented by using a recursive function to compute the cycle length:<\/p>\n<pre class=\"lang:c decode:true\" title=\"Recursion for the Cycle Length\">int Cycle_Length (unsigned int n) \/* Note the unsigned precision *\/\r\n{\r\n    \tunsigned int aux;\r\n\r\n        \/* Stopping Condition - Don't want the recursion to run for forever *\/\r\n        if (n == 1) return 1;\r\n\r\n        \/* Here is the recursion, if n is odd  else     if n is even   *\/\r\n\t    aux = (n%2) ? (1 + Cycle_Length(3*n+1) ) : (1+Cycle_Length(n&gt;&gt;1));\r\n        \/* Note that division by two is performed by shifitng a bit to the right *\/\r\n\t    return aux;\r\n}<\/pre>\n<p>Now, there are two ways we can optimise this function and make it more\u00a0<strong>efficient<\/strong>.<\/p>\n<p>The first one relates to a certain property of odd numbers: we know that if n is odd, than 3*n+1 is going to be even. Therefore we can simply skip one iteration of the cycle:<\/p>\n<pre class=\"lang:c decode:true\">aux = (n%2) ? (2+Cycle_Length((3*n+1)&gt;&gt;1)) : (1+Cycle_Length(n&gt;&gt;1)) ;<\/pre>\n<p>We can further optimise our code by using Dynamic Programming. We can store the Cycle Lengths we already computed so we don&#8217;t need to compute them ever again.<\/p>\n<p>Using dynamic programming and the tricks above, we can get to the final solution (which runs pretty fast on the Online Judge platform):<\/p>\n<pre class=\"lang:c decode:true crayon-selected\" title=\"PROBTNPO\">#include&lt;stdio.h&gt;\r\n#include&lt;stdlib.h&gt;\r\n\r\nint CycleLength[100001];\r\n\r\nint Cycle_Length (unsigned int n)\r\n{\r\n\tint aux;\r\n\tif(n&gt;100000)\r\n\t{\r\n\t\taux = (n%2) ? (2+Cycle_Length((3*n+1)&gt;&gt;1)) : (1+Cycle_Length(n&gt;&gt;1)) ;\r\n\t\treturn aux;\r\n\t}\r\n\tif(!CycleLength[n]) \t\r\n\t\tCycleLength[n] = (n%2) ? (2+Cycle_Length((3*n+1)&gt;&gt;1)) : (1+Cycle_Length(n&gt;&gt;1)) ;\r\n\treturn CycleLength[n];\r\n}\r\n\r\nint findmax(int a, int b)\r\n{\r\n\tint max=0,aux,i;\r\n\tfor(i=a;i&lt;=b;i++)\r\n\t{\r\n\t\taux=Cycle_Length(i);\r\n\t\tif(max&lt;aux)\r\n\t\t\tmax=aux;\r\n\t}\r\n\treturn max;\t\r\n}\r\n\r\nint main()\r\n{\r\n\tint a,b;\r\n\tCycleLength[1]=1;\r\n\twhile(scanf(\"%d %d\",&amp;a,&amp;b)!=EOF)\r\n\t\ta&lt;b?printf(\"%d %d %d\\n\",a,b,findmax(a,b)):printf(\"%d %d %d\\n\",a,b,findmax(b,a));\r\n\treturn 0;\r\n}<\/pre>\n<p>Ta daam!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the first meeting of the OPIG Algotirhm Club, we tackled the problem 3n+1 from the Sphere Online Judge (SPOJ). \u00a0&#8212;Background &#8212; The problem relates to the Collatz conjecture. Before describing the conjecture, let us define a very simple recursive relation: If a number is odd, multiply it by 3 and add 1 (hence 3n+1). [&hellip;]<\/p>\n","protected":false},"author":11,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","wikipediapreview_detectlinks":true,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"ngg_post_thumbnail":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[29],"tags":[84,81,88,82,87,86,85,83],"ppma_author":[505],"class_list":["post-1811","post","type-post","status-publish","format-standard","hentry","category-code","tag-3n1","tag-algorithm","tag-c","tag-club","tag-code-2","tag-probtnpo","tag-sphere-online-judge","tag-spoj"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"authors":[{"term_id":505,"user_id":11,"is_guest":0,"slug":"saulo","display_name":"Saulo Pires de Oliveira","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/5f63aaf111511b89e2975aad0ccbd7c0160152b90b2df36425f2db14218cdd13?s=96&d=mm&r=g","0":null,"1":"","2":"","3":"","4":"","5":"","6":"","7":"","8":""}],"_links":{"self":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/1811","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/comments?post=1811"}],"version-history":[{"count":11,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/1811\/revisions"}],"predecessor-version":[{"id":1887,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/posts\/1811\/revisions\/1887"}],"wp:attachment":[{"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/media?parent=1811"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/categories?post=1811"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/tags?post=1811"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.blopig.com\/blog\/wp-json\/wp\/v2\/ppma_author?post=1811"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}