0
$\begingroup$

Let $m,n, N$ be $3$ natural numbers. I want to know how many ordered pairs $(m,n)$ are possible such that $2^m\cdot 3^n< 10^N$.

My attempt: Taking $\log$ base $10$ on both sides, we have $m \log2 + n\log 3 < N$ Which is kind of a Diophantine inequality. How do I proceed now?

Also, can this approach be generalised for more than 2 primes?

$\endgroup$
0
3
$\begingroup$

Assuming your natural numbers start at $0$, an exact expression would be $$\sum_{m=0}^{\left\lfloor\dfrac N{\log 2}\right\rfloor}\left\lfloor1+\dfrac {N-m\log 2}{\log 3}\right\rfloor.$$

We're basically letting $m$ assume all possible values, then for each $m$ calculating the range of possible $n$ values. This approach can be extended to multiple primes, e.g. $$\sum_{x_2=0}^{\left\lfloor\dfrac N{\log 2}\right\rfloor}\sum_{x_3=0}^{\left\lfloor\dfrac {N-x_2\log2}{\log 3}\right\rfloor}\sum_{x_5=0}^{\left\lfloor\dfrac {N-x_2\log2-x_3\log3}{\log 5}\right\rfloor}\left\lfloor1+\dfrac {N-x_2\log 2-x_3\log3-x_5\log5}{\log 7}\right\rfloor.$$

This is all a bit messy. If only $\log 2$ and $\log 3$ were integers, then we could use Pick's Theorem!

A fairly accurate approximation is $\dfrac12 \left(\left\lfloor\dfrac N{\log 2}\right\rfloor+1.5\right)\left(\left\lfloor\dfrac N {\log 3}\right\rfloor+1.5\right)$. This approximates the number of lattice points (points with integer coordinates) under the line $m \log 2 + n \log 3 = N$ by halving an (almost) average of what we'd get if we rounded down the intercepts vs. rounding up.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your answer. I have few questions, which are as follows: How did you get 1 in summand? Can we do it in similar way by letting n assume all possible values, if yes what is the explanation that it will lead to the same answer? How do you apply Pick's theorem in case of only 2 primes? How did you get the approximate value for the sum? $\endgroup$ – SARTHAK GUPTA Dec 23 '19 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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