Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 Answer 1

up vote 0 down vote accepted

$$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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.