The following operations are performed to the natural numbers $x$: $x\to x+2$ or $x\to x+n$, $x\to x\cdot 2$ or $x\to x\cdot n$. Additions and multiplications are performes alternatively (adding $2$ or $n$ and multiplying by $2$ or by $n$ one can choose as he wishes for each step). The number $m$ is called attainable if it can be obtained from $1$ by a sequence of such operations, otherwise $m$ is called unattainable. Prove that if $n=5$ or $n=7$, then there are infinitely many unattainable numbers.
Problem
Source: 2017 Belarus Team Selection Test 3.3
Tags: number theory, combinatorics
Pathological
01.04.2019 01:14
Notice that $5$ is unattainable.
$\mathbf{Claim.}$ If $x \equiv 3, 5,$ or $13$ (mod $14$) is unattainable, then so is $2x+7.$
$\mathbf{Proof.}$ Assume, for contradiction, that $2x+7$ was attainable. Notice that $2, 7 \nmid 2x+7,$ so that if it were attainable the number before it must have been $2x+5$ or $2x.$
As $2, 7 \nmid 2x+5$, we must have reached $2x$ and then $2x+7.$ As $7 \nmid 2x,$ we know that we must have reached $x$, then $2x$, then $2x+7.$ However, we know that $x$ is unattainable, contradiction.
$\blacksquare$
Using the claim, we can easily generate an infinite sequence of unattainable numbers $5, 17, 41, 89, 185, \cdots.$
$\square$
Nymoldin
03.05.2021 22:38
Bump for n=5
Infinityfun
06.03.2023 10:05
For n = 5 Bump!