{"id":225,"date":"2017-09-03T21:45:41","date_gmt":"2017-09-03T21:45:41","guid":{"rendered":"https:\/\/xiaohaionline.com\/?p=225"},"modified":"2017-09-03T21:47:29","modified_gmt":"2017-09-03T21:47:29","slug":"how-many-ways-are-there-to-express-a-positive-integer-as-a-sum-of-more-than-one-consecutive-positive-integers","status":"publish","type":"post","link":"https:\/\/xiaohaionline.com\/index.php\/2017\/09\/03\/how-many-ways-are-there-to-express-a-positive-integer-as-a-sum-of-more-than-one-consecutive-positive-integers\/","title":{"rendered":"How many ways are there to express a positive integer as a sum of more than one consecutive positive integers?"},"content":{"rendered":"<p>    <script src=\"https:\/\/cdn.mathjax.org\/mathjax\/latest\/MathJax.js?config=TeX-AMS_HTML\"><\/script><br \/>\n    <script type=\"text\/x-mathjax-config\">\n    MathJax.Hub.Config({\n        tex2jax: {\n            inlineMath: [ ['$','$'], [\"\\\\(\",\"\\\\)\"] ],\n            displayMath: [ ['$$','$$'], [\"\\\\[\",\"\\\\]\"] ],\n            processEscapes: true,\n            processEnvironments: true\n        },\n        displayAlign: 'center',\n        \"HTML-CSS\": {\n            styles: {'.MathJax_Display': {\"margin\": 0}},\n            linebreaks: { automatic: true }\n        }\n    });\n    <\/script><\/p>\n<div tabindex=\"-1\" id=\"notebook\" class=\"border-box-sizing\">\n<div class=\"container\" id=\"notebook-container\">\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>During one of company meetings, a co-worker raised an interview question that aroused my intense interest. The question goes like this:<\/p>\n<p><b>Given a positive integer N, how many different ways can one express it as a sum of consecutive integers?<\/b><\/p>\n<\/div>\n<\/div>\n<\/div>\n<p><!--more--><\/p>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h2 id=\"The-question\">The question<a class=\"anchor-link\" href=\"#The-question\">&#182;<\/a><\/h2>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>For a naive brute force solution, the complexity of the algorithm is obviously O($N^2$). With some optimization, he was able to get to a O(N) performance improvement.<\/p>\n<p>For me, intuitively, this is a math problem. It immediately aroused my interest in looking at this problem in more details. With a little bit mathematical derivation, it appears that I can solve the question with a complexity of $O(\\sqrt{N})$.<\/p>\n<p>But before I present my algorithm, let me first clarify a couple of edge cases.<\/p>\n<ol>\n<li>The number $N$ can be obviously expressed as a $sum$ of the single number $N$ itself. I would like to exclude this trivial case. <\/li>\n<li>\nFor the set of consecutive integers, we assume the integers will have to be positive.\n<\/li>\n<\/ol>\n<p>Thus the original question can be stated more precisely as:<\/p>\n<p><b>Given a positive integer N, how many different ways can one express it as a sum of more than one consecutive positive integers?<\/b><\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h2 id=\"The-derivation\">The derivation<a class=\"anchor-link\" href=\"#The-derivation\">&#182;<\/a><\/h2>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>Let&#8217;s denote the consecutive numbers summation expression as:<br \/>\n$$ m\\ +\\ (m+1)\\ +\\ &#8230;\\ +\\ (m+n-1) $$<br \/>\nwhere $$ m > 0\\ ,\\ n > 1 $$<br \/>\nthen we have<br \/>\n$$ N\\ = \\ m\\ +\\ (m+1)\\ +\\ &#8230;\\ +\\ (m+n-1) $$<br \/>\nor $$ N\\ =\\ mn + (1\\ +\\ 2\\ +\\ &#8230;\\ +\\ (n-1))\\ =\\ mn+\\frac{n(n-1)}{2}$$<br \/>\nor $$ N=n(m + \\frac{n-1}{2})$$<\/p>\n<p>The question can be now rephrase as:<\/p>\n<p>How many different <i>positive integer pairs<\/i> we can find for $m$ and $n$ satisfying:<br \/>\n$$N=n(m + \\frac{n-1}{2}),\\ \\ \\ \\ \\ m>0,n>1\\ \\ \\ \\ (1)$$<\/p>\n<p>Since $m$ is a positive integer $(m \\ge 1)$, we have<br \/>\n$$ N \\ge n(n+1)\/2$$ or $$ n^2+n-2N \\le 0$$<br \/>\nThis leads to<br \/>\n$$1\\lt n \\le \\frac{\\sqrt{8N+1}-1}{2}\\ \\ \\ \\ \\ (2)$$<br \/>\nInequalities (2) effectively limits the possible values of $n$. We still need to find the value of $m$ given a $n$ satisfying inequalities (2). We will then consider two different cases.<\/p>\n<p><b>If $n$ is an odd number<\/b><br \/>\nthen $\\frac{n-1}{2}$ is an integer. For $n$ to be a solution of equation (1), $n$ MUST be a factor (divisible) of the number $N$. And if $n$ is indeed a factor of $N$, and $n$ satisfy inequalities (2), then a positive integer $m$ is available to satisfy equation (1).<\/p>\n<p><b>If $n$ is an even number <\/b>, then we can rewrite equation (1) as equation (3):<br \/>\n$$ 2N=n(2m+n-1)\\ \\ \\ \\ \\ (3)$$<br \/>\nBecause $n$ is assumed to be an even number, $2m+n-1$ would be an odd number. Thus the number $n$ must be a factor of $2N$ and it MUST contain all the exponents of 2 in $2N$ (so that $\\frac{2N}{n}$ is odd). Again, inequalities (2) must be satisfied to find a viable $m$ given $n$.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h2 id=\"The-algorithm\">The algorithm<a class=\"anchor-link\" href=\"#The-algorithm\">&#182;<\/a><\/h2>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>Summarizing the above two cases, we get the following algorithms:<\/p>\n<ol>\n<li>Let $P=\\lfloor \\frac{\\sqrt{8N+1}-1}{2} \\rfloor$<\/li>\n<li>Find the set <b>$O$<\/b> of all the odd factors of $N$ between 3 and $P$ inclusive<\/li>\n<li>Denote the maximum exponents of 2 in $N$ as $e$, and let $q=2^{e+1}$<\/li>\n<li>Add $q$ into the set <b>$E$<\/b> if $q \\le P$. For each element $o$ in <b>$O$<\/b>, if $oq \\le P$, then add $oq$ into the set <b>$E$<\/b><\/li>\n<li>The number of elements in <b>$O$<\/b> and <b>$E$<\/b> determines the number of summation expressions for $N$.<\/li>\n<li>If we want to further identify the summation expressions: for each element in <b>$O$<\/b> and <b>$E$<\/b>, use $m=\\frac{N}{n}-\\frac{n-1}{2}$ to find corresponding $m$.<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h2 id=\"The-codes\">The codes<a class=\"anchor-link\" href=\"#The-codes\">&#182;<\/a><\/h2>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>Python code would be the following:<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing code_cell rendered\">\n<div class=\"input\">\n<div class=\"prompt input_prompt\">In&nbsp;[1]:<\/div>\n<div class=\"inner_cell\">\n<div class=\"input_area\">\n<div class=\" highlight hl-ipython3\">\n<pre><span><\/span><span class=\"kn\">import<\/span> <span class=\"nn\">numpy<\/span> <span class=\"k\">as<\/span> <span class=\"nn\">np<\/span>\r\n\r\n<span class=\"k\">def<\/span> <span class=\"nf\">get_consecutive_sum_n_values<\/span><span class=\"p\">(<\/span><span class=\"n\">N<\/span><span class=\"p\">):<\/span>\r\n    <span class=\"n\">P<\/span><span class=\"o\">=<\/span><span class=\"nb\">int<\/span><span class=\"p\">(<\/span><span class=\"n\">np<\/span><span class=\"o\">.<\/span><span class=\"n\">floor<\/span><span class=\"p\">((<\/span><span class=\"n\">np<\/span><span class=\"o\">.<\/span><span class=\"n\">sqrt<\/span><span class=\"p\">(<\/span><span class=\"mi\">8<\/span><span class=\"o\">*<\/span><span class=\"n\">N<\/span><span class=\"o\">+<\/span><span class=\"mi\">1<\/span><span class=\"p\">)<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">)<\/span><span class=\"o\">\/<\/span><span class=\"mi\">2<\/span><span class=\"p\">))<\/span>\r\n    <span class=\"c1\"># odd factors of N<\/span>\r\n    <span class=\"n\">n_values<\/span> <span class=\"o\">=<\/span> <span class=\"p\">[<\/span><span class=\"n\">o<\/span> <span class=\"k\">for<\/span> <span class=\"n\">o<\/span> <span class=\"ow\">in<\/span> <span class=\"nb\">range<\/span><span class=\"p\">(<\/span><span class=\"mi\">3<\/span><span class=\"p\">,<\/span> <span class=\"n\">P<\/span><span class=\"o\">+<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"mi\">2<\/span><span class=\"p\">)<\/span> <span class=\"k\">if<\/span> <span class=\"p\">(<\/span><span class=\"n\">N<\/span> <span class=\"o\">%<\/span> <span class=\"n\">o<\/span> <span class=\"o\">==<\/span> <span class=\"mi\">0<\/span><span class=\"p\">)]<\/span>\r\n    <span class=\"c1\"># maximum exponent of 2 in 2N<\/span>\r\n    <span class=\"n\">q<\/span> <span class=\"o\">=<\/span> <span class=\"mi\">1<\/span>\r\n    <span class=\"k\">while<\/span> <span class=\"n\">q<\/span> <span class=\"o\">&lt;=<\/span> <span class=\"n\">N<\/span> <span class=\"ow\">and<\/span> <span class=\"n\">N<\/span> <span class=\"o\">%<\/span> <span class=\"n\">q<\/span> <span class=\"o\">==<\/span> <span class=\"mi\">0<\/span><span class=\"p\">:<\/span>\r\n        <span class=\"n\">q<\/span> <span class=\"o\">&lt;&lt;=<\/span> <span class=\"mi\">1<\/span>\r\n    <span class=\"c1\"># even factors<\/span>\r\n    <span class=\"k\">if<\/span> <span class=\"n\">q<\/span> <span class=\"o\">&lt;=<\/span> <span class=\"n\">P<\/span><span class=\"p\">:<\/span>\r\n        <span class=\"n\">n_values<\/span><span class=\"o\">.<\/span><span class=\"n\">extend<\/span><span class=\"p\">([<\/span><span class=\"n\">q<\/span> <span class=\"o\">*<\/span> <span class=\"n\">o<\/span> <span class=\"k\">for<\/span> <span class=\"n\">o<\/span> <span class=\"ow\">in<\/span> <span class=\"n\">n_values<\/span> <span class=\"k\">if<\/span> <span class=\"p\">(<\/span><span class=\"n\">o<\/span> <span class=\"o\">*<\/span> <span class=\"n\">q<\/span> <span class=\"o\">&lt;=<\/span> <span class=\"n\">P<\/span><span class=\"p\">)])<\/span>\r\n        <span class=\"n\">n_values<\/span><span class=\"o\">.<\/span><span class=\"n\">append<\/span><span class=\"p\">(<\/span><span class=\"n\">q<\/span><span class=\"p\">)<\/span>\r\n    <span class=\"k\">return<\/span> <span class=\"n\">n_values<\/span><span class=\"p\">;<\/span>\r\n\r\n<span class=\"k\">def<\/span> <span class=\"nf\">print_consecutive_sum_expression<\/span><span class=\"p\">(<\/span><span class=\"n\">N<\/span><span class=\"p\">):<\/span>\r\n    <span class=\"n\">n_values<\/span> <span class=\"o\">=<\/span> <span class=\"n\">get_consecutive_sum_n_values<\/span><span class=\"p\">(<\/span><span class=\"n\">N<\/span><span class=\"p\">)<\/span>\r\n    <span class=\"nb\">print<\/span><span class=\"p\">(<\/span><span class=\"s1\">&#39;expressions for:&#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">N<\/span><span class=\"p\">)<\/span>\r\n    <span class=\"k\">for<\/span> <span class=\"n\">n<\/span> <span class=\"ow\">in<\/span> <span class=\"n\">n_values<\/span><span class=\"p\">:<\/span>\r\n        <span class=\"n\">m<\/span> <span class=\"o\">=<\/span> <span class=\"nb\">int<\/span><span class=\"p\">((<\/span><span class=\"mi\">2<\/span><span class=\"o\">*<\/span><span class=\"n\">N<\/span> <span class=\"o\">-<\/span> <span class=\"n\">n<\/span><span class=\"o\">*<\/span><span class=\"p\">(<\/span><span class=\"n\">n<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">))<\/span><span class=\"o\">\/<\/span><span class=\"mi\">2<\/span><span class=\"o\">\/<\/span><span class=\"n\">n<\/span><span class=\"p\">)<\/span>\r\n        <span class=\"k\">if<\/span> <span class=\"n\">n<\/span> <span class=\"o\">==<\/span> <span class=\"mi\">2<\/span><span class=\"p\">:<\/span>\r\n            <span class=\"nb\">print<\/span><span class=\"p\">(<\/span><span class=\"s1\">&#39;  &#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">n<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;integers: (&#39;<\/span><span class=\"p\">,<\/span><span class=\"n\">m<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;+&#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">m<\/span><span class=\"o\">+<\/span><span class=\"n\">n<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;)&#39;<\/span><span class=\"p\">)<\/span>\r\n        <span class=\"k\">else<\/span><span class=\"p\">:<\/span>\r\n            <span class=\"nb\">print<\/span><span class=\"p\">(<\/span><span class=\"s1\">&#39;  &#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">n<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;integers: (&#39;<\/span><span class=\"p\">,<\/span><span class=\"n\">m<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;+ ... +&#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">m<\/span><span class=\"o\">+<\/span><span class=\"n\">n<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;)&#39;<\/span><span class=\"p\">)<\/span>\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>Some testing codes:<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing code_cell rendered\">\n<div class=\"input\">\n<div class=\"prompt input_prompt\">In&nbsp;[2]:<\/div>\n<div class=\"inner_cell\">\n<div class=\"input_area\">\n<div class=\" highlight hl-ipython3\">\n<pre><span><\/span><span class=\"n\">print_consecutive_sum_expression<\/span><span class=\"p\">(<\/span><span class=\"mi\">9<\/span><span class=\"p\">)<\/span>\r\n<span class=\"n\">print_consecutive_sum_expression<\/span><span class=\"p\">(<\/span><span class=\"mi\">15<\/span><span class=\"p\">)<\/span>\r\n<span class=\"n\">print_consecutive_sum_expression<\/span><span class=\"p\">(<\/span><span class=\"mi\">100<\/span><span class=\"p\">)<\/span>\r\n<span class=\"n\">print_consecutive_sum_expression<\/span><span class=\"p\">(<\/span><span class=\"mi\">1000000<\/span><span class=\"p\">)<\/span>\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"output_wrapper\">\n<div class=\"output\">\n<div class=\"output_area\">\n<div class=\"prompt\"><\/div>\n<div class=\"output_subarea output_stream output_stdout output_text\">\n<pre>expressions for: 9\r\n   3 integers: ( 2 + ... + 4 )\r\n   2 integers: ( 4 + 5 )\r\nexpressions for: 15\r\n   3 integers: ( 4 + ... + 6 )\r\n   5 integers: ( 1 + ... + 5 )\r\n   2 integers: ( 7 + 8 )\r\nexpressions for: 100\r\n   5 integers: ( 18 + ... + 22 )\r\n   8 integers: ( 9 + ... + 16 )\r\nexpressions for: 1000000\r\n   5 integers: ( 199998 + ... + 200002 )\r\n   25 integers: ( 39988 + ... + 40012 )\r\n   125 integers: ( 7938 + ... + 8062 )\r\n   625 integers: ( 1288 + ... + 1912 )\r\n   640 integers: ( 1243 + ... + 1882 )\r\n   128 integers: ( 7749 + ... + 7876 )\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h2 id=\"Further-discussions\">Further discussions<a class=\"anchor-link\" href=\"#Further-discussions\">&#182;<\/a><\/h2>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h3 id=\"Simplificatio-of-the-algorithm\">Simplificatio of the algorithm<a class=\"anchor-link\" href=\"#Simplificatio-of-the-algorithm\">&#182;<\/a><\/h3>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>The algorithm above is simple enough, and it has less than 10 lines of codes. However, with further mathematical analysis, it is possible to further simplify the above algorithm.<\/p>\n<p>Let&#8217;s first relax the requirement of $m$ being positive. Let&#8217;s allow $m$ to take value of negative integers or zero. We then have the following observations:<\/p>\n<ol>\n<li>Note: $$ (-p)\\ +\\ (-p + 1)\\ +\\ &#8230;\\ +\\ 0\\ +\\ &#8230;\\ +\\ (p-1)\\ +\\ p\\ +\\ (p + 1)\\ +\\ &#8230;\\ +\\ (p + n &#8211; 1)\\ ==$$ $$(p + 1)\\ +\\ &#8230;\\ +\\ (p + n &#8211; 1)$$ $$where\\ p \\ge 0 $$ We can state that we can convert the summation of a consecutive sequence of integers that starts with a non-positive integer into a summation of the mapping consecutive sequence of integers that starts with a positive integer.<\/li>\n<li>Note: $$(p + 1)\\ +\\ &#8230;\\ +\\ (p + n &#8211; 1)\\ ==$$ $$ (-p)\\ +\\ (-p + 1)\\ +\\ &#8230;\\ +\\ 0\\ +\\ &#8230;\\ +\\ (p-1)\\ +\\ p\\ +\\ (p + 1)\\ +\\ &#8230;\\ +\\ (p + n &#8211; 1)\\ ==$$ $$where\\ p \\ge 0 $$ We can state that we can convert the summation of a consecutive sequence of integers that starts with a positive integer into a summation of the mapping consecutive sequence of integers that starts with a non-positive integer.<\/li>\n<li>Summarizing the above two observations, we come to the conclusion that summation sequences have a one-to-one mapping relationship between those start with positive integers and those start with non-positive integers. Or we can say:<\/li>\n<\/ol>\n<p><b>Relaxing the requirement of $m \\gt 0$, the number of viable sequences that starts with positive integers is the same as the number of viable sequences with non-positive integers. Both are half of the total number of viable sequences.<\/b><\/p>\n<p>Please note that in the above conversions, we added or removed $2p+1$ number of integers. So if the number of elements of the sequence before conversion (think $n$) is odd or even, the number of elements of the sequence after conversion will be even or odd respectively. Thus we have:<\/p>\n<p><b> With the requirement of $m \\gt 0$ relaxed, the number of viable sequences with odd number of elements is the same as the number of viable sequences with even number of elements. Both are half of the total number of viable sequences.<\/b><\/p>\n<p>Combining the above two bold observations, we get:<\/p>\n<p><b>The number of viable sequences starting with positive integers is the same as the number of viable sequences containing odd number of elements. <\/b><\/p>\n<p>So the original questions becomes: <b>Without requiring $m$ to be positive, how many pairs of $m$ and $n$ we can find for the following equation:<\/b> $$N=n(m + \\frac{n-1}{2}),\\ \\ \\ \\ \\ n>1\\ and\\ n\\ is\\ odd\\ \\ \\ \\ (4)$$<\/p>\n<p>It should be easy to see that the answer is exactly: <b>the number of odd factors of the given $N$<\/b>.<\/p>\n<p>Please note once you get a negative $m$ out of the $m=\\frac{N}{n}-\\frac{n-1}{2}$, you need to follow the conversion procedure to get the sequence that starts with a positive integer.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h2 id=\"Simplified-algorithm\">Simplified algorithm<a class=\"anchor-link\" href=\"#Simplified-algorithm\">&#182;<\/a><\/h2>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing code_cell rendered\">\n<div class=\"input\">\n<div class=\"prompt input_prompt\">In&nbsp;[3]:<\/div>\n<div class=\"inner_cell\">\n<div class=\"input_area\">\n<div class=\" highlight hl-ipython3\">\n<pre><span><\/span><span class=\"kn\">import<\/span> <span class=\"nn\">numpy<\/span> <span class=\"k\">as<\/span> <span class=\"nn\">np<\/span>\r\n\r\n<span class=\"k\">def<\/span> <span class=\"nf\">get_consecutive_sum_n_values_simplified<\/span><span class=\"p\">(<\/span><span class=\"n\">N<\/span><span class=\"p\">):<\/span>\r\n    <span class=\"c1\"># odd factors of N<\/span>\r\n    <span class=\"k\">return<\/span> <span class=\"p\">[<\/span><span class=\"n\">o<\/span> <span class=\"k\">for<\/span> <span class=\"n\">o<\/span> <span class=\"ow\">in<\/span> <span class=\"nb\">range<\/span><span class=\"p\">(<\/span><span class=\"mi\">3<\/span><span class=\"p\">,<\/span> <span class=\"n\">N<\/span><span class=\"o\">+<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"mi\">2<\/span><span class=\"p\">)<\/span> <span class=\"k\">if<\/span> <span class=\"p\">(<\/span><span class=\"n\">N<\/span> <span class=\"o\">%<\/span> <span class=\"n\">o<\/span> <span class=\"o\">==<\/span> <span class=\"mi\">0<\/span><span class=\"p\">)]<\/span>\r\n\r\n<span class=\"k\">def<\/span> <span class=\"nf\">print_consecutive_sum_expression_simplified<\/span><span class=\"p\">(<\/span><span class=\"n\">N<\/span><span class=\"p\">):<\/span>\r\n    <span class=\"n\">n_values<\/span> <span class=\"o\">=<\/span> <span class=\"n\">get_consecutive_sum_n_values_simplified<\/span><span class=\"p\">(<\/span><span class=\"n\">N<\/span><span class=\"p\">)<\/span>\r\n    <span class=\"nb\">print<\/span><span class=\"p\">(<\/span><span class=\"s1\">&#39;expressions for:&#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">N<\/span><span class=\"p\">)<\/span>\r\n    <span class=\"k\">for<\/span> <span class=\"n\">n<\/span> <span class=\"ow\">in<\/span> <span class=\"n\">n_values<\/span><span class=\"p\">:<\/span>\r\n        <span class=\"n\">m<\/span> <span class=\"o\">=<\/span> <span class=\"nb\">int<\/span><span class=\"p\">((<\/span><span class=\"mi\">2<\/span><span class=\"o\">*<\/span><span class=\"n\">N<\/span> <span class=\"o\">-<\/span> <span class=\"n\">n<\/span><span class=\"o\">*<\/span><span class=\"p\">(<\/span><span class=\"n\">n<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">))<\/span><span class=\"o\">\/<\/span><span class=\"mi\">2<\/span><span class=\"o\">\/<\/span><span class=\"n\">n<\/span><span class=\"p\">)<\/span>\r\n        <span class=\"k\">if<\/span> <span class=\"n\">m<\/span> <span class=\"o\">&lt;=<\/span> <span class=\"mi\">0<\/span><span class=\"p\">:<\/span>\r\n            <span class=\"n\">n<\/span> <span class=\"o\">-=<\/span> <span class=\"p\">(<\/span><span class=\"o\">-<\/span><span class=\"n\">m<\/span><span class=\"o\">*<\/span><span class=\"mi\">2<\/span><span class=\"o\">+<\/span><span class=\"mi\">1<\/span><span class=\"p\">)<\/span>\r\n            <span class=\"n\">m<\/span> <span class=\"o\">=<\/span> <span class=\"p\">(<\/span><span class=\"o\">-<\/span><span class=\"n\">m<\/span> <span class=\"o\">+<\/span> <span class=\"mi\">1<\/span><span class=\"p\">)<\/span>\r\n        <span class=\"k\">if<\/span> <span class=\"n\">n<\/span> <span class=\"o\">==<\/span> <span class=\"mi\">2<\/span><span class=\"p\">:<\/span>\r\n            <span class=\"nb\">print<\/span><span class=\"p\">(<\/span><span class=\"s1\">&#39;  &#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">n<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;integers: (&#39;<\/span><span class=\"p\">,<\/span><span class=\"n\">m<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;+&#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">m<\/span><span class=\"o\">+<\/span><span class=\"n\">n<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;)&#39;<\/span><span class=\"p\">)<\/span>\r\n        <span class=\"k\">else<\/span><span class=\"p\">:<\/span>\r\n            <span class=\"nb\">print<\/span><span class=\"p\">(<\/span><span class=\"s1\">&#39;  &#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">n<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;integers: (&#39;<\/span><span class=\"p\">,<\/span><span class=\"n\">m<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;+ ... +&#39;<\/span><span class=\"p\">,<\/span> <span class=\"n\">m<\/span><span class=\"o\">+<\/span><span class=\"n\">n<\/span><span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"s1\">&#39;)&#39;<\/span><span class=\"p\">)<\/span>\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>The same testing codes:<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing code_cell rendered\">\n<div class=\"input\">\n<div class=\"prompt input_prompt\">In&nbsp;[4]:<\/div>\n<div class=\"inner_cell\">\n<div class=\"input_area\">\n<div class=\" highlight hl-ipython3\">\n<pre><span><\/span><span class=\"n\">print_consecutive_sum_expression_simplified<\/span><span class=\"p\">(<\/span><span class=\"mi\">9<\/span><span class=\"p\">)<\/span>\r\n<span class=\"n\">print_consecutive_sum_expression_simplified<\/span><span class=\"p\">(<\/span><span class=\"mi\">15<\/span><span class=\"p\">)<\/span>\r\n<span class=\"n\">print_consecutive_sum_expression_simplified<\/span><span class=\"p\">(<\/span><span class=\"mi\">100<\/span><span class=\"p\">)<\/span>\r\n<span class=\"n\">print_consecutive_sum_expression_simplified<\/span><span class=\"p\">(<\/span><span class=\"mi\">1000000<\/span><span class=\"p\">)<\/span>\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"output_wrapper\">\n<div class=\"output\">\n<div class=\"output_area\">\n<div class=\"prompt\"><\/div>\n<div class=\"output_subarea output_stream output_stdout output_text\">\n<pre>expressions for: 9\r\n   3 integers: ( 2 + ... + 4 )\r\n   2 integers: ( 4 + 5 )\r\nexpressions for: 15\r\n   3 integers: ( 4 + ... + 6 )\r\n   5 integers: ( 1 + ... + 5 )\r\n   2 integers: ( 7 + 8 )\r\nexpressions for: 100\r\n   5 integers: ( 18 + ... + 22 )\r\n   8 integers: ( 9 + ... + 16 )\r\nexpressions for: 1000000\r\n   5 integers: ( 199998 + ... + 200002 )\r\n   25 integers: ( 39988 + ... + 40012 )\r\n   125 integers: ( 7938 + ... + 8062 )\r\n   625 integers: ( 1288 + ... + 1912 )\r\n   640 integers: ( 1243 + ... + 1882 )\r\n   128 integers: ( 7749 + ... + 7876 )\r\n<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<h3 id=\"Comparing-the-two-algorithms\">Comparing the two algorithms<a class=\"anchor-link\" href=\"#Comparing-the-two-algorithms\">&#182;<\/a><\/h3>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"cell border-box-sizing text_cell rendered\">\n<div class=\"prompt input_prompt\">\n<\/div>\n<div class=\"inner_cell\">\n<div class=\"text_cell_render border-box-sizing rendered_html\">\n<p>The simplified algorithm in Python only takes one line of codes. However in terms of the computational complexity, the simplified algorithm is actually worse with a performance of $O(N)$.<\/p>\n<p>However, if we are smart in finding the odd factors instead of using the brute force method, the simplified algorithm will be at the same complexity with the algorithm given prior.<\/p>\n<\/div>\n<\/div>\n<\/div><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>During one of company meetings, a co-worker raised an interview question that aroused my intense interest. The question goes like this: Given a positive integer N, how many different ways can one express it as a sum of consecutive integers?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,3],"tags":[41,42,40],"class_list":["post-225","post","type-post","status-publish","format-standard","hentry","category-python","category-software","tag-integer","tag-interview","tag-number"],"_links":{"self":[{"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/posts\/225","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/comments?post=225"}],"version-history":[{"count":5,"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/posts\/225\/revisions"}],"predecessor-version":[{"id":230,"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/posts\/225\/revisions\/230"}],"wp:attachment":[{"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/media?parent=225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/categories?post=225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xiaohaionline.com\/index.php\/wp-json\/wp\/v2\/tags?post=225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}