Numbers of the Form $a^2b^3$

Define $F(n)$ to be the number of integers $x≤n$ that can be written in the form $x=a^2b^3$, where $a$ and $b$ are integers not necessarily different and both greater than 1.

For example, $32=2^2\times 2^3$ and $72=3^2\times 2^3$ are the only two integers less than $100$ that can be written in this form. Hence, $F(100)=2$.

Further you are given $F(2\times 10^4)=130$ and $F(3\times 10^6)=2014$.

Find $F(9\times 10^{18})$.

To start, we’ll use the observation that $x=a^2b^3=(ab)^3(ab)$, so for each $x$, there is exactly one pair $(a, b)$ with $a≤b$.

Note that $ab≤\sqrt[6]{x}=m$, so $a$ can be any integer up to $m$. Once $a$ is fixed, $b$ should be in the interval $[a,\frac{x}{a^2}]$. Therefore, if we fix $a$, the number of possible $x$ is $\left\lfloor \frac{n}{a^2} \right\rfloor – a + 1$.

For each $a\le m$, $a^2b^3$ can be calculated using each $b$ from $a$ to $\left\lfloor \frac{n}{a^2} \right\rfloor$, respectively.

Therefore, the overall total of such integers $x≤n$ is
$$
F(n)=\sum_{a=1}^{m} \left( \left\lfloor \frac{n}{a^2} \right\rfloor – a + 1 \right)=\sum_{a=1}^{m} \left\lfloor \frac{n}{a^2} \right\rfloor – m(m+1)/2 + m = \sum_{a=1}^{m} \left\lfloor \frac{n}{a^2} \right\rfloor – m^2/2 + m/2.
$$

This is a common number theoretical formula and can be calculated in $O(m)$ or $O(\sqrt n)$. However, if we also take account of the second part of the original formula, it turns out $O(n^{1/3})$ is sufficient for calculating $F(n)$.

It turns out that we only need to calculate the sum up to $m=n^{1/6}$, because for later terms $a>n^{1/6}$, $\frac{n}{a^2}

More Answers: