\n
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
\n
Applying $f(n)=2n+1$ has the net effect of tacking on a \u201c1\u201d 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 \u201c00\u201d 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<\/li><\/ul>\n
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\u2019s consider the more general problem of asking how many numbers between $1$ and $2^n$ we can reach. Let\u2019s call this number $a_n$. Let\u2019s look at the reachable numbers that have $k$ digits, and organize them in a table (in base 2):
\n\\[
\n\\begin{array}{c|l}
\n\\text{digits} & \\text{reachable numbers} \\\\ \\hline
\n1 & 1 \\\\
\n2 & 11 \\\\
\n3 & 111, 100\\\\
\n4 & 1111, 1001, 1100\\\\
\n5 & 11111, 10011, 11001, 11100, 10000\\\\
\n\\end{array}
\n\\]The number of entries in row $k$ is simply $F_k$, the $k^\\text{th}$ 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 \u201c$1$\u201d to the end), or we can start with the entries from row $k-2$ and apply $g$ (add a \u201c$00$\u201d 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,\u2026).<\/p>\n
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\u2019s clear from the pattern that this number is reachable whenever $n$ is even. Therefore, the reachable numbers $a_n$ is given by:
\n\\[
\na_n = F_1+\\cdots+F_{n} + \\begin{cases}
\n1 & n\\text{ is even} \\\\
\n0 & n\\text{ is odd}
\n\\end{cases}
\n\\]We can simplify this sum further. To see how, write:
\n\\begin{align}
\nF_n &= F_{n+2}-F_{n+1}\\\\
\nF_{n-1} &= F_{n+1}-F_n \\\\
\nF_{n-2} &= F_n-F_{n-1} \\\\
\n\\vdots\\,\\, &= \\,\\,\\vdots\\\\
\nF_2 &= F_4-F_3\\\\
\nF_1 &= F_3-F_2
\n\\end{align}Summing both sides, we get cancelations on the right-hand side:
\n\\[
\nF_1+\\cdots+F_{n} = F_{n+2}-F_2 = F_{n+2}-1
\n\\]Therefore, we can simplify our formula and write:
\n\\[
\na_n = F_{n+2}-1+\\frac{1}{2}\\left( (-1)^n+1 \\right)
\n\\]Further simplification gets us our final answer:<\/p>\n
$\\displaystyle
\na_n = F_{n+2}+\\frac{1}{2}\\left( (-1)^n-1 \\right)
\n$<\/span><\/p>\n
We can also find a closed-form expression if we use Binet\u2019s formula<\/a>:<\/p>\n
$\\displaystyle
\na_n = \\frac{\\phi^{n+2}-\\psi^{n+2}}{\\sqrt{5}}+\\frac{(-1)^n-1}{2}
\n$<\/span><\/p>\n
where $\\phi=\\frac{1+\\sqrt{5}}{2}$ and $\\psi=\\frac{1-\\sqrt{5}}{2}$ are the golden ratio<\/a> and its conjugate, respectively. The first several values of $a_n$ are:
\n\\[
\n\\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}
\nn & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\\ \\hline
\na_n & 1 & 1 & 3 & 4 & 8 & 12 & 21 & 33 & 55 & 88 & 144 \\\\
\n\\end{array}
\n\\]<\/p>\n
The original problem asked about numbers up to $1024 = 2^{10}$, so we have:
\n\\[
\na_{10} = F_{12} = 144
\n\\]<\/p>\n
Extra credit<\/h3>\n
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
\n
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<\/li><\/ul>\n
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:
\n\\[
\n\\begin{array}{c|l}
\n\\text{row} & \\text{reachable numbers} \\\\ \\hline
\n0 & 1 \\\\
\n1 & -1 \\\\
\n2 & 11, 100 \\\\
\n3 & -101, -111, -100 \\\\
\n4 & 1011, 1111, 1001, 1100, 10000 \\\\
\n5 & -10101, -11101, -10001, -11001, -11111, -10100, -11100, -10000 \\\\
\n\\end{array}
\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
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:
\n\\[
\nb_n = F_1+\\cdots+F_{n+1} + 1 + \\begin{cases}
\n1 & n\\text{ is even} \\\\
\n0 & n\\text{ is odd}
\n\\end{cases}
\n\\]Similarly to the previous case, we obtain the solution:<\/p>\n
$\\displaystyle
\nb_n = F_{n+3}+\\frac{1}{2}\\left( (-1)^n+1 \\right)
\n$<\/span><\/p>\n
or, using Binet\u2019s formula,<\/p>\n
$\\displaystyle
\nb_n = \\frac{\\phi^{n+3}-\\psi^{n+3}}{\\sqrt{5}}+\\frac{(-1)^n+1}{2}
\n$<\/span><\/p>\n
The first several values of $b_n$ are:
\n\\[
\n\\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c}
\nn & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\\ \\hline
\nb_n & 3 & 3 & 6 & 8 & 14 & 21 & 35 & 55 & 90 & 144 & 234 \\\\
\n\\end{array}
\n\\]The original problem asked about numbers between $-1024$ and $1024$, so since $1024=2^{10}$, we have:
\n\\[
\nb_{10} = F_{13}+1 = 234
\n\\]<\/p>\n<\/div>\n<\/body>","protected":false},"excerpt":{"rendered":"
This week\u2019s 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 … Continue reading “Making something out of nothing”<\/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}]}}