{"id":3677,"date":"2023-07-30T21:53:33","date_gmt":"2023-07-31T02:53:33","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3677"},"modified":"2023-08-01T10:44:19","modified_gmt":"2023-08-01T15:44:19","slug":"making-something-out-of-nothing","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/making-something-out-of-nothing\/","title":{"rendered":"Making something out of nothing"},"content":{"rendered":"<p>This week&#8217;s <a href=\"https:\/\/thefiddler.substack.com\/p\/can-you-make-something-out-of-nothing\">Fiddler<\/a> is a problem about composing functions. Here it goes:<\/p>\n<blockquote><p>\nConsider $f(n) = 2n+1$ and $g(n) = 4n$. It\u2019s possible to produce different whole numbers by applying combinations of $f$ and $g$ to $0$. How many whole numbers between $1$ and $1024$ (including $1$ and $1024$) can you produce by applying some combination of $f$&#8217;s and $g$&#8217;s to the number $0$?<\/p>\n<p><em>Extra Credit:<\/em> Now consider the functions $g(n) = 4n$ and $h(n) = 1\u22122n$. How many integers between $-1024$ and $1024$ (including $-1024$ and $1024$) can you produce by applying some combination of $g$&#8217;s and $h$&#8217;s to the number $0$?\n<\/p><\/blockquote>\n<p>My solution:<br \/>\n<a href=\"javascript:Solution('soln_something_nothing','toggle_something_nothing')\" id=\"toggle_something_nothing\">[Show Solution]<\/a><\/p>\n<div id=\"soln_something_nothing\" style=\"display: none\">\n<p>Initially, we must start by applying $f$, otherwise we would just stay at zero. So for all intents and purposes, we can assume we start at $1$. At this point, it helps to write numbers out in binary (base two).<\/p>\n<ul>\n<li>Applying $f(n)=2n+1$ has the net effect of tacking on a &#8220;1&#8221; to the end of the number in binary form, For example, if we start at $12$ (which is $1100$ in binary), then $f(12)=25$, which is $11001$ in binary.\n<li>Applying $g(n)=4n$ has the net effect of tacking on a &#8220;00&#8221; to the end of the number in binary form, so for example, if we start at $3$ (which is $11$ in binary), then $g(3)=12$, which is $1100$ in binary.\n<\/ul>\n<p>Now back to the original problem. Our goal is to count how many numbers between $1$ and $1024$ we can reach using compositions of $f$ and $g$. Since $1024=2^{10}$, let&#8217;s consider the more general problem of asking how many numbers between $1$ and $2^n$ we can reach. Let&#8217;s call this number $a_n$. Let&#8217;s look at the reachable numbers that have $k$ digits, and organize them in a table (in base 2):<br \/>\n\\[<br \/>\n\\begin{array}{c|l}<br \/>\n\\text{digits} &#038; \\text{reachable numbers} \\\\ \\hline<br \/>\n1 &#038; 1 \\\\<br \/>\n2 &#038; 11 \\\\<br \/>\n3 &#038; 111, 100\\\\<br \/>\n4 &#038; 1111, 1001, 1100\\\\<br \/>\n5 &#038; 11111, 10011, 11001, 11100, 10000\\\\<br \/>\n\\end{array}<br \/>\n\\]The number of entries in row $k$ is simply $F_k$, the $k^\\text{th}$ <a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_sequence\">Fibonacci number<\/a>. To see why, observe that to get to row $k$, we can start with the entries from row $k-1$ and apply $f$ (add a &#8220;$1$&#8221; to the end), or we can start with the entries from row $k-2$ and apply $g$ (add a &#8220;$00$&#8221; to the end). Since the first two rows each have one entry, we get the standard Fibonacci sequence (1,1,2,3,5,8,13,&#8230;).<\/p>\n<p>Counting the reachable numbers up to $2^n-1$ means including all numbers with up to $n$ digits, so summing $F_1+F_2+\\cdots+F_{n}$. However, we also want to include $2^n$. It&#8217;s clear from the pattern that this number is reachable whenever $n$ is even. Therefore, the reachable numbers $a_n$ is given by:<br \/>\n\\[<br \/>\na_n = F_1+\\cdots+F_{n} + \\begin{cases}<br \/>\n1 &#038; n\\text{ is even} \\\\<br \/>\n0 &#038; n\\text{ is odd}<br \/>\n\\end{cases}<br \/>\n\\]We can simplify this sum further. To see how, write:<br \/>\n\\begin{align}<br \/>\nF_n &#038;= F_{n+2}-F_{n+1}\\\\<br \/>\nF_{n-1} &#038;= F_{n+1}-F_n \\\\<br \/>\nF_{n-2} &#038;= F_n-F_{n-1} \\\\<br \/>\n\\vdots\\,\\, &#038;= \\,\\,\\vdots\\\\<br \/>\nF_2 &#038;= F_4-F_3\\\\<br \/>\nF_1 &#038;= F_3-F_2<br \/>\n\\end{align}Summing both sides, we get cancelations on the right-hand side:<br \/>\n\\[<br \/>\nF_1+\\cdots+F_{n} = F_{n+2}-F_2 = F_{n+2}-1<br \/>\n\\]Therefore, we can simplify our formula and write:<br \/>\n\\[<br \/>\na_n = F_{n+2}-1+\\frac{1}{2}\\left( (-1)^n+1 \\right)<br \/>\n\\]Further simplification gets us our final answer:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\na_n = F_{n+2}+\\frac{1}{2}\\left( (-1)^n-1 \\right)<br \/>\n$<\/span><\/p>\n<p>We can also find a closed-form expression if we use <a href=\"https:\/\/en.wikipedia.org\/wiki\/Fibonacci_sequence#Binet's_formula\">Binet&#8217;s formula<\/a>:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\na_n = \\frac{\\phi^{n+2}-\\psi^{n+2}}{\\sqrt{5}}+\\frac{(-1)^n-1}{2}<br \/>\n$<\/span><\/p>\n<p>where $\\phi=\\frac{1+\\sqrt{5}}{2}$ and $\\psi=\\frac{1-\\sqrt{5}}{2}$ are the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Golden_ratio\">golden ratio<\/a> and its conjugate, respectively. The first several values of $a_n$ are:<br \/>\n\\[<br \/>\n\\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}<br \/>\nn   &#038; 0 &#038; 1 &#038; 2 &#038; 3 &#038; 4 &#038; 5  &#038; 6  &#038; 7  &#038; 8  &#038; 9  &#038; 10  \\\\ \\hline<br \/>\na_n &#038; 1 &#038; 1 &#038; 3 &#038; 4 &#038; 8 &#038; 12 &#038; 21 &#038; 33 &#038; 55 &#038; 88 &#038; 144 \\\\<br \/>\n\\end{array}<br \/>\n\\]<\/p>\n<p>The original problem asked about numbers up to $1024 = 2^{10}$, so we have:<br \/>\n\\[<br \/>\na_{10} = F_{12} = 144<br \/>\n\\]<\/p>\n<h3>Extra credit<\/h3>\n<p>This problem is similar to the first part, but we have to take a bit more care with edge cases. In particular, the first part had the nice feature that applying $f$ always added one digit, and applying $g$ always added two digits (in base 2). This is (almost) still true. Applying $g$ still adds two digits, but applying $h$ does the following:<\/p>\n<ul>\n<li> If the number is negative, it adds a one and flips the sign. For example: $h(-10)=21$ i.e., $-1010\\mapsto 10101$.\n<li> If the number is positive, it adds a zero, flips the sign, then subtracts $1$. For example: $h(6)=-11$, i.e., $110\\mapsto -1011$.\n<\/ul>\n<p>It can happen that applying $h$ will not increase the number of digits. For example, $h(4)=-7$, i.e., $100\\mapsto -111$. Nevertheless, we can still make a table similar to how we did before, except we will not arrange numbers by digits. Instead, arrange them in such a way that the Fibonacci pattern remains true, like this:<br \/>\n\\[<br \/>\n\\begin{array}{c|l}<br \/>\n\\text{row} &#038; \\text{reachable numbers} \\\\ \\hline<br \/>\n0 &#038; 1 \\\\<br \/>\n1 &#038; -1 \\\\<br \/>\n2 &#038; 11, 100 \\\\<br \/>\n3 &#038; -101, -111, -100 \\\\<br \/>\n4 &#038; 1011, 1111, 1001, 1100, 10000 \\\\<br \/>\n5 &#038; -10101, -11101, -10001, -11001, -11111, -10100, -11100, -10000 \\\\<br \/>\n\\end{array}<br \/>\n\\]Note that the rows alternate positive and negative numbers. Also, row $k$ for $k\\geq 1$ contains numbers with $k$ binary digits, except the even rows, which also contain the number $2^{k}$, which has $k+1$ digits. The reason for this discrepancy is so that we maintain the Fibonacci pattern. Now, we can see that row $k$ is formed by applying $h$ to row $k-1$, or applying $g$ to row $k-2$. Therefore, row $k$ contains $F_{k+1}$ numbers.<\/p>\n<p>Now, we can see that summing rows $0$ through $k$ will give us reachable numbers between $-(2^{k}-1)$ and $2^{k}$. To make sure we include $-2^{k}$, we should also add one whenever $k$ is even. So far, we counted positive and negative reachable numbers, but what about zero? Since $g(0)=0$, zero is also reachable, so we should add one more to include it. Therefore, we find that:<br \/>\n\\[<br \/>\nb_n = F_1+\\cdots+F_{n+1} + 1 + \\begin{cases}<br \/>\n1 &#038; n\\text{ is even} \\\\<br \/>\n0 &#038; n\\text{ is odd}<br \/>\n\\end{cases}<br \/>\n\\]Similarly to the previous case, we obtain the solution:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nb_n = F_{n+3}+\\frac{1}{2}\\left( (-1)^n+1 \\right)<br \/>\n$<\/span><\/p>\n<p>or, using Binet&#8217;s formula,<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\nb_n = \\frac{\\phi^{n+3}-\\psi^{n+3}}{\\sqrt{5}}+\\frac{(-1)^n+1}{2}<br \/>\n$<\/span><\/p>\n<p>The first several values of $b_n$ are:<br \/>\n\\[<br \/>\n\\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}<br \/>\nn   &#038; 0 &#038; 1 &#038; 2 &#038; 3 &#038; 4  &#038; 5  &#038; 6  &#038; 7  &#038; 8  &#038; 9   &#038; 10  \\\\ \\hline<br \/>\nb_n &#038; 3 &#038; 3 &#038; 6 &#038; 8 &#038; 14 &#038; 21 &#038; 35 &#038; 55 &#038; 90 &#038; 144 &#038; 234 \\\\<br \/>\n\\end{array}<br \/>\n\\]The original problem asked about numbers between $-1024$ and $1024$, so since $1024=2^{10}$, we have:<br \/>\n\\[<br \/>\nb_{10} = F_{13}+1 = 234<br \/>\n\\]<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>This week&#8217;s Fiddler is a problem about composing functions. Here it goes: Consider $f(n) = 2n+1$ and $g(n) = 4n$. It\u2019s possible to produce different whole numbers by applying combinations of $f$ and $g$ to $0$. How many whole numbers between $1$ and $1024$ (including $1$ and $1024$) can you produce by applying some combination &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/making-something-out-of-nothing\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Making something out of nothing&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[42],"tags":[6,43,36,15],"class_list":["post-3677","post","type-post","status-publish","format-standard","hentry","category-the-fiddler","tag-counting","tag-fiddler","tag-number-theory","tag-recursion"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3677","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=3677"}],"version-history":[{"count":13,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3677\/revisions"}],"predecessor-version":[{"id":3680,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3677\/revisions\/3680"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3677"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3677"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3677"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}