A good way to find $a_{50000}$ where $a_n$ is a number in the form of $2^j\cdot 3^k$

Question

Letting $A=\{2^j\cdot 3^k| j,k \ \text{are non-negative integers} \}$, let us define $a_n$ as the $n$-th element of $A$ in ascending order.

We can see $$a_1=1, a_2=2,a_3=3,a_4=4,a_5=6,a_6=8,a_7=9,a_8=12,\cdots.$$

Then, here is my question.

Question : Could you show me a good way to get $a_n$ for large $n$ supposing that we can use computer? For example, how can we get $a_{2000},a_{5000},a_{10000},a_{50000}$ ?

Motivation : I've known a question about finding $a_{20},a_{50},a_{100}.$

My way is to prepare the following values.

$$a_{13}=2^5, a_{17}=2^6, a_{22}=2^7, \cdots, a_{48}=2^{11},a_{56}=2^{12},\cdots, a_{95}=2^{16},a_{106}=2^{17}$$ $$a_{12}=3^3, a_{19}=3^4, \cdots, a_{49}=3^{7},\cdots, a_{93}=3^{10},a_{111}=3^{11}$$

These values help us find $$a_{20}=2^5\cdot 3^1=96, a_{50}=2^8\cdot 3^2=2304, a_{100}=2^7\cdot 3^6=93312.$$

However, this idea has difficulty for finding $a_n$ for much larger $n$, so it seems that another idea would be needed. Can anyone help?

Answer 1

I used the following in PARI/GP

ct(n)=if(n<5,n,floor(log(n+.5)/log(2))+1+ct(floor(n/3)))
T = 50000
b=1; while(ct(b)<T, a=b; b+=b)
while(b-a>1,c=(a+b)/2;if(ct(c)<T,a=c,b=c))
b

Here ct(x) counts the numbers of the required form $\le x$ and then I do a binary search.

This finally gave me $a_{50000}=2^{167}3^ {145}$. You need sufficient precision (e.g. \p150) for this to work, at least as as many digits as the final result has. If factor(b,5) fails to find a complete factorization, the precision was obviously too low. A thorough check for sufficient precision would involve checking when log(n+.5)/log(2) is so close to an integer that the floor function might guess wrong; the trick of adding $\frac12$ before taking logarithm already tries to avoid much of this hassle.

Answer 2

One approach is to work backwards. Given $x>0$, count how many elements in your sequence are less than $x$. That is, $2^a3^b<x$ or $$a (\ln 2) + b (\ln 3) < \ln x$$ This is equivalent to counting lattice points (points with integer coordinates) inside the triangle with vertices $(0,0)$, $(0,\log_3x)$, $(\log_2x,0)$. Unfortunately there is no really good way to explicitly do this; for an approach see here.

If you're just trying to speed up computer search, then round; the number of such points is at least $\frac{1}{2}\lfloor \log_3x\rfloor \lfloor \log_2x\rfloor$ and at most $\frac{1}{2}\lceil \log_3x\rceil \lceil \log_2x\rceil$; so pick an $x$ where $50000$ is between these two values, then explicitly calculate and order all the points in the diagonal strip between the smaller and larger triangles.

Answer 3

Each number $n=2^j\cdot 3^k$ corresponds to a lattice point $(j,k)$ in the first quadrant of the $(x,y)$-plane. Consider a given number $n_0=2^{j_0}\cdot 3^{k_0}$. The corresponding point $(j_0,k_0)$ lies on the line $$x\log 2+y\log 3=\log n_0\ .$$ All lattice points $(j,k)$ corresponding to values $n=2^j\cdot 3^k<n_0$ are lying below this line and whence in the triangle with vertices $$(0,0),\quad \left({\log n_0\over\log2},0\right),\quad \left(0,{\log n_0\over\log3}\right)\ .$$ Their number $N_0$ is approximately equal to the area of this triangle, so that we may write $$N_0\doteq{1\over2}{\bigl(\log n_0\bigr)^2\over\log2\log 3}\ .$$ Solving this for $n_0$ we get $$n_0\doteq\exp\left(\sqrt{2N_0\log2\log3}\right)\ .$$ Since $N_0$ is essentially the number that $n_0$ would obtain in your list $(a_N)_{N\geq0}$, we can say that approximatively $$a_N\doteq\exp\left(\sqrt{2N\log2\log3}\right)\qquad(N\gg1)\ .$$