Number of positive integers $k$ such that there exists a nonnegative integer $m$ with $k + k^m = n$

Question

Let $a(n)$ be the number of positive integers $k$ such that there exists a nonnegative integer $m$ with $k + k^m = n$.

The sequence begins $$0, 1, 1, 2, 1, 3, 1, 2, 1, 3, 1, 3, 1, 2, 1, 2, 1, 3, 1, 3$$ Let $$b(n)=\sum\limits_{i=1}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\left\lfloor\log_{i+1}(n-i)\right\rfloor$$

Also $$c(n)=b(n)-b(n-1)+1$$

I conjecture that $c(n)=a(n+1)$ for $n>0$.

Is there a way to prove it? If the conjecture is true, is it possible to use it to answer the questions posed in A309978? The questions are:

• Does there exist $n$ such that $a(n) \geqslant 5$?
• Do there exist examples besides $30$ and $130$ such that $a(n) = 4$?

Answer 1

The formula $c(n)=a(n+1)$ is pretty much straightforward, noticing that $$\lfloor \log_{i+1}(n-i)\rfloor - \lfloor\log_{i+1}(n-1-i)\rfloor=1\quad\text{iff}\quad n-i=(i+1)^m\text{ for some }m.$$ The latter condition means that $n+1=k+k^m$ with $k:=i+1$.