A simple calculator – 2

Number Theory Level 3

A simple calculator only has 2 functions.

It always starts at 0 and then does one of the following

add $a \in \mathbb{N}$ to the number
multiply the number by $b \in \mathbb{N}$

It can do multiple operations in a row, the result of the last operation is always the input for the next one.

This calculator is then named $(a,b)$ .

Does there exist a calculator $(a,b)$ with $a>1$ that can calculate almost all positive integers?

More formally:

Let $|S_n(a,b)|$ count the number of positive integers less than or equal to $n$ that can be calculated using this calculator. Then, does there exist a calculator $(a,b), a>1$ such that

$\displaystyle \lim_{n \to \infty} \frac {|S_n(a,b)|}{n} = 1$ ?

No Yes

1 solution

William Allbritain
Dec 26, 2018

Every number that can be generated by $(a, b)$ is divisible by $a$ ; indeed, any such number can be obtained by repeated addition of $a$ . Therefore the proportion of positive integers that can be so calculated is $\frac{1}{a} < 1$ for $a > 1$ , so the answer is $\boxed{\text{no}}$ . More formally:

$|S_n(a, b)| = \left\lfloor \dfrac{n}{a} \right\rfloor \implies \lim_{n \to \infty} \dfrac{|S_n(a, b)|}{n} = \lim_{n \to \infty} \dfrac{1}{n} \left\lfloor \dfrac{n}{a} \right\rfloor = \dfrac{1}{a} < 1.$

A simple calculator – 2

1 solution

0 pending reports