number of integer solutions for $2^x\cdot 3^y$

Question

Can someone help me figure out how to calculate the number of integer solutions to the equation: $N\ge2^x3^y|x,y\in\Bbb Z+$

For example if $N$ is $30$ we have $2\cdot 3$, $2^2\cdot 3$, $2^3\cdot 3$, $2\cdot 3^2$ so $4$ solutions

I know the number of integer solutions to $N\ge2^x$ is just $\left \lfloor \ln{N}/\ln{2} \right \rfloor $ So I was thinking something along the lines of taking the sum of $\log_2\left(\frac{N}{3^i}\right)$ from $i=1..(\log_3(N))$

Any help is greatly appreciated

Answer 1

The problem $2^x 3^y \le 30$ can be solved graphically as follows.

Taking the logarithm of both sides and simplifying, we get

\begin{align} 2^x 3^y &\le 30 \\ (\ln 2)x + (\ln 3)y &\le \ln 30 \\ \end{align}

The line above is the line described by $(\ln 2)x + (\ln 3)y = \ln 30$. The indicated lattice points are the $(x,y)$ solutions to $ 2^x 3^y \le 30$

Answer 2

You want to count all the points with positive integer coordinates which lie on or below the line

$$ y=-x\log_3(2)+N\log_3(N)\tag{1}$$

which one obtains by taking $\log_3$ of both sides of

$$ 2^x3^y=N $$

and solving for $y$.

A formula for computing the number $C(N)$ of points having positive integer coordinates and lying on or below the line given by $(1)$ is

$$ C(N)=\sum_{k=1}^{\left\lfloor\log_2(N/3)\right\rfloor}\left\lfloor\log_3\left(\frac{N}{2^k}\right)\right\rfloor\tag{2} $$

For example, for $N=243$ this gives

$$ C(243)=\sum_{k=1}^{6}\left\lfloor\log_3\left(\frac{243}{2^k}\right)\right\rfloor=4+3+3+2+1+1=14 $$ Here is a GeoGebra link with a slider where you can change the value of $N$.

Below is a static illustration.