1

This is an interesting question i came across but am unable to find a solution to it.

Given $N$, $k$, we need to find $M$ such that $M+\left\lfloor \dfrac{M}{k} \right\rfloor+ \left\lfloor \dfrac{M}{k^2} \right\rfloor + \ldots + \left\lfloor \dfrac{M}{k^p} \right\rfloor=N$ where $\left\lfloor \dfrac{M}{k^p} \right\rfloor=0$. One thing that can be done is use brute force by taking different values of M. Is there any method by which we can generalize it or a better solution?

George V. Williams
  • 5,213
Aman Agarwal
  • 113
  • 1
    Of course there does not always exist a solution (e.g. $k=N=3$). What is to say against a binary search starting with $N/2$ and $N$? – Hagen von Eitzen Jan 19 '13 at 16:08

1 Answers1

0

$$N=M+[M/k]+[M/k^2]+\cdots+[M/k^p]\le M+(M/k)+(M/k^2)+\cdots+(M/k^p)\le M(1+(1/k)+(1/k^2)+\cdots)=Mk/(k-1)$$ so $M\ge N(k-1)/k$. Also, $$N\ge M+(M/k)+(M/k^2)+\cdots+(M/k^p)-p$$ How big is $p$? Well, $$M/k^p\lt1\le M/k^{p-1}$$ so $$M\lt k^p\le Mk$$ and $$\log M/\log k\lt p\le1+(\log M/\log k)$$ If you put all of this together, you may get some useful upper bound on $M$, to go along with the lower bound $M\ge N(k-1)/k$, and then you'll have a range to search.

Gerry Myerson
  • 179,216