A simple calculator – 4

Number Theory Level 3

Since 2 simple functions are not enough for calculators, we can now giva a calculator any number of functions, but we still want the calculators to be as simple as possible.

A calculator always starts with 0 and then executes one or more functions. The result of one function is always the input of the next.

Which of the following sets of functions allow a calculator to calculate every positive integer?

$A: \begin{cases} f(x)=x+2 \\ g(x)=x\cdot 3 \\ h(x)=x\cdot 6 \end{cases}$
$B: \begin{cases} f(x)=F_x \\ g(x)=x+8 \end{cases}$
$C: \begin{cases} f(x)=x-5\\ g(x)=x\cdot 7 \end{cases}$
$D: \begin{cases} f(x)=2^x \\ g(x)=\sqrt[4]{x} \\ h(x)=x+2 \end{cases}$

$F_n$ is the $n$ -th Fibonacci number

A D C B

2 solutions

Henry U
Dec 26, 2018

The only reasonable first step is $x+2$ , which leads to 2, an even number. No matter what we do now, we will always get even numbers as a result, so we can not get any odd numbers.

Let's look at the Fibonacci numbers' remainders under division by 8

$1,1,2,3,5,0,5,5,2,7,1,0,1,1,\ldots$

We see that there is no 4, so with $F_x$ alone, we can't get numbers of the form $8k+4, k \in \mathbb{N}$ . We could add 8 at any time, but that doesn't help.

The only reasonable first step is $x-5$ , but then we're at –5 and neither $x-5$ nor $x \cdot 7$ can make the result positive again.

If we want to reach an even number, we just add 2 as many times as necessary. If we need an odd number, we first calculate $2^x$ , which gives 1 and then add a few 2's.

So, D is correct.

Geoff Pilling
Dec 28, 2018

For A you can't get 1.

For B you can't get 4.

For C you can only get negative numbers.

However, for D you can get $2^0 = 1$ and $2^1 = 2$ . Then you can get any odd number by continually adding 2 to 1. And you can get any even number by continually adding 2 to 2.

A simple calculator – 4

2 solutions

0 pending reports