Can You Make Something out of Nothing?

Take the two functions $f(n) = 2n + 1$ and $g(n) = 4n$, and apply them in any combination, starting from $0$. For example $f(0) = 1$, $f(f(0)) = 3$, $g(f(0)) = 4$, $f(f(f(0))) = 7$, $f(g(f(0))) = 9$ and $g(g(f(0))) = 16$. How many of the whole numbers from $1$ to $1{,}024$ inclusive can be produced this way?

The Fiddler, Zach Wissner-Gross, July 28, 2023(original post)

The official solution appeared in the post of August 4, 2023 and gives $144$ for the main puzzle and $234$ for the Extra Credit. Both agree with the answers below; the $234$ counts $0$ itself, which $g$ produces from $0$.

Solution

The upper limit $1{,}024 = 2^{10}$ is a hint to write numbers in binary. There, doubling a number appends a $0$ to its digits, just as multiplying by ten does in decimal. So $f$, which doubles and adds one, appends the digit $1$, and $g$, which multiplies by four, appends the two digits $00$.

Starting from $0$, applying $g$ changes nothing, and the first $f$ produces $1$. From then on each step appends a block, either $1$ or $00$. So the numbers that can be produced, apart from $0$, are exactly those whose binary digits are a leading $1$ followed by a string of the blocks $1$ and $00$. Different strings of blocks give different numbers, because reading the digits from the left splits them back into blocks in only one way: a $1$ is a block, and a $0$ must start a $00$.

How many such numbers have exactly $L$ binary digits? After the leading $1$ there are $L - 1$ digits to fill with blocks of length $1$ and $2$. Call the number of ways $k_L$. The last block is either a $1$, leaving $L - 2$ digits before it, or a $00$, leaving $L - 3$, so $$k_L \;=\; k_{L-1} + k_{L-2}, \qquad k_1 = 1, \quad k_2 = 1 .$$ These are the Fibonacci numbers:

Every number with at most ten binary digits lies between $1$ and $1{,}023$, so those contribute $1 + 1 + 2 + \dots + 55 = 143$. An eleven-digit number is at least $2^{10} = 1{,}024$, and only $1{,}024$ itself is in range; it is $1$ followed by five blocks $00$, which is $g^5(f(0))$. The total is $$\boxed{\ 143 + 1 \;=\; 144 \text{ numbers}. \ }$$ That $144$ is itself a Fibonacci number is no accident: the first $n$ Fibonacci numbers add up to one less than the $(n + 2)$th, here $143 = F_{12} - 1$.

The computation

The check makes no use of binary. It applies the functions over and over, starting from $0$, and collects everything it reaches in the range. Neither function ever makes a nonzero number smaller in size, so a number that leaves the range can never come back, and the search can stop at the boundary.

def reachable(functions, low, high):
    """Numbers in [low, high] reachable from 0. No function
    shrinks a nonzero number, so nothing outside the range
    leads back into it and the search stops at the edge."""
    seen, todo = {0}, [0]
    while todo:
        n = todo.pop()
        for fn in functions:
            m = fn(n)
            if low <= m <= high and m not in seen:
                seen.add(m)
                todo.append(m)
    return seen

f = lambda n: 2*n + 1
g = lambda n: 4*n
h = lambda n: 1 - 2*n

main = reachable([f, g], 0, 1024)
print("main:", len([n for n in main if 1 <= n <= 1024]))

It prints

main: 144

Extra Credit

Now use $g(n) = 4n$ together with $h(n) = 1 - 2n$. How many integers from $-1{,}024$ to $1{,}024$ inclusive can be produced from $0$?

Solution

In binary, $h$ misbehaves: it can lose digits as well as gain them, since $h(4) = -7$ has the same number of binary digits as $4$. The cure is to change the base. Write $h(n) = (-2)\,n + 1$ and $g(n) = (-2)^2\,n$. In base $-2$, where the place values are $1, -2, 4, -8, 16, \dots$, multiplying by $-2$ appends a $0$, so $h$ appends the digit $1$ and $g$ appends $00$. This is the main puzzle again, with base $2$ replaced by base $-2$.

Base $-2$ is a perfectly good number system. Every integer, positive or negative, has exactly one representation using the digits $0$ and $1$ with no minus sign. For example $-7 = 1 - 8$ is written $1001$, and $3 = 4 - 2 + 1$ is written $111$. The sign of a number is the sign of its leading place value, because the lower places can never outweigh it: below a leading $(-2)^p$, the places of the opposite sign add up to at most $\frac23\bigl(2^p - 1\bigr)$ in size, which is less than $2^p$.

So the reachable integers, apart from $0$, are again exactly the strings made of a leading $1$ followed by blocks $1$ and $00$, and there are $k_L$ of them with $L$ digits. What changes is which lengths fit the range. The $L$-digit numbers lie between these bounds:

Every reachable number of up to ten digits is in range, and there are $143$ of them, as before. The eleven- and twelve-digit numbers need a closer look.

Eleven digits. Such a number is $1{,}024$ plus a ten-digit tail made of blocks, and it is in range exactly when the tail is zero or negative. The tail’s highest $1$ is the first $1$ block, which sits after some number $j$ of $00$ blocks, at position $9 - 2j$ counting from $0$ on the right. That position is always odd, so its place value is negative, and so is the tail. All $k_{11} = 89$ of these numbers are in range.

Twelve digits. Such a number is $-2{,}048$ plus an eleven-digit tail, and it is in range only if the tail is at least $1{,}024$. Now the tail’s highest $1$ is at an even position $10 - 2j$, and the tail reaches $1{,}024$ only if that position is $10$, so that the tail is $1{,}024$ plus a ten-digit tail of the kind just seen, which is zero or negative. So the tail is exactly $1{,}024$ and the number is $-1{,}024$ itself, written $11$ followed by ten $0$s, which is $g^5(h(h(0)))$: one number.

The total. Adding $0$, which $g(0) = 0$ produces, $$\boxed{\ 1 + 143 + 89 + 1 \;=\; 234 \text{ integers}. \ }$$ If $0$ is not counted as produced, the count is $233$.

The computation

The same search, now with $g$ and $h$ and the range $-1{,}024$ to $1{,}024$, also reports whether the two ends of the range were reached.

extra = reachable([g, h], -1024, 1024)
print("extra credit:", len(extra), "including 0,",
      len(extra - {0}), "without it")
print("extremes reached:", 1024 in extra, -1024 in extra)

It prints

extra credit: 234 including 0, 233 without it
extremes reached: True True