Can any $n \in \mathbb{N}$ be reached from 1 by doubling and summing digits?

94 Views Asked by At

For $n \in \mathbb{N}$, let $f(n) = 2n$ and let $g(n)$ equal the digit sum (in base ten) of $n$.

Can any $n \in \mathbb{N}$ be reached from $1$ after a finite series of applications of $f$ and $g$?

2

There are 2 best solutions below

0
On BEST ANSWER

Neither operation can ever produce a number divisible by $3$ from a number not divisible by $3$.

0
On

Just to explain a bit about another answer given: The sum of digits of a number gives the same remainder when divided by $3$ as the number divided by $3$, and the reason why is that $999\ldots9$ is divisible by $3$ so $10^k$ always gives a remainder of $1$ when divided by $3$ for any $k$. Thus if you add up the remainders from the digits, this is the same as calculating the remainder given the digits if you consider it to be a base-10 number.