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:
Constrained Permutations
Square Prime Factors
Square Prime Factors II