Project Euler Problem 634
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 ne
Solution
Answer: 4019680944
Let $x=\prod p_i^{e_i}$.
We want to know when $x$ can be written as
$$x=a^2b^3 \qquad (a,b>1).$$
For each prime exponent $e$, we need
$$e = 2u+3v,$$
with $u,v\ge 0$.
The only exponents that cannot contribute simultaneously to both the square and cube parts are:
- $2,4$: square-only,
- $3$: cube-only,
- $6$: can go entirely to one side, but not both.
Hence a powerful number fails to be representable only in these three cases:
- all exponents are in ${2,4}$,
- all exponents are $3$,
- the number is $p^6$ for a prime $p$.
So:
$$F(N)=P(N)-C_3(\sqrt N)-Q(\sqrt[3]N)-\pi(\sqrt[6]N)+1,$$
where
- $P(N)$ = number of powerful numbers $\le N$,
- $C_3(x)$ = number of cube-free integers $\le x$,
- $Q(x)$ = number of square-free integers $\le x$,
- $\pi(x)$ = prime counting function.
The powerful numbers satisfy
$$P(N)=\sum_{\substack{b\le N^{1/3}\ b\text{ squarefree}}} \left\lfloor \sqrt{\frac{N}{b^3}}\right\rfloor.$$
Evaluating these quantities for
$$N=9\times 10^{18}$$
gives
$$P(N)=6516667851,$$
$$C_3(\sqrt N)=2495722127,$$
$$Q(\sqrt[3]N)=1264553,$$
$$\pi(\sqrt[6]N)=228.$$
Therefore
$$F(N) = 6516667851 - 2495722127 - 1264553 - 228 + 1 = 4019680944.$$
Answer: 4019680944