Detailed mathematical approach

Problem Summary

We seek the number of integers \(n \le N\), with \(N=9\times 10^{18}\), that can be written in the form

$n=a^2b^3,\qquad a>1,\qquad b>1.$

A direct scan up to \(N\) is impossible. The solution instead counts a larger class of numbers whose prime exponents are all at least \(2\), then removes the exceptional cases that still fail the conditions \(a>1\) and \(b>1\).

Mathematical Approach

Define

$F(N)=\#\left\{n\le N : n=a^2b^3 \text{ for some } a,b>1\right\}.$

If \(n=\prod p^{e_p}\) has the form \(a^2b^3\), then each exponent satisfies \(e_p\ge 2\). So every admissible \(n\) is a powerful number. The implementations therefore count all powerful numbers up to \(N\), and then subtract the powerful numbers that are still not valid \(a^2b^3\) values with both factors greater than \(1\).

Step 1: Count all powerful numbers through the canonical form

Every powerful number has a unique representation

$n=u^2v^3,$

where \(v\) is squarefree. For each prime exponent \(e\ge 2\), write

$e=2\alpha+3\beta,\qquad \beta\in\{0,1\},$

so the parity of \(e\) decides whether that prime contributes once to \(v\). This makes the decomposition unique.

Therefore the number of powerful numbers up to \(N\) is

$P(N)=\sum_{\substack{1\le v\le \lfloor N^{1/3}\rfloor\\ v \text{ squarefree}}}\left\lfloor\sqrt{\frac{N}{v^3}}\right\rfloor.$

For each squarefree \(v\), every integer \(u\) with \(u^2v^3\le N\) contributes one powerful number.

Step 2: Remove the cube-only obstruction

If \(u=1\), then \(n=v^3\) with \(v\) squarefree. Every nonzero prime exponent is then exactly \(3\), and the local equation

$3=2x+3y,\qquad x,y\ge 0$

forces \(x=0\). So any such representation has \(a=1\), which is forbidden.

Hence we must subtract

$C(N)=\#\left\{v\le \lfloor N^{1/3}\rfloor : v \text{ squarefree}\right\}.$

The same squarefree sieve used for \(P(N)\) also yields this correction term.

Step 3: Remove the square-only obstruction

If \(v=1\), then \(n=u^2\) is a perfect square. Such a number is not automatically admissible. The obstruction occurs exactly when \(u\) is cubefree.

If \(u\) is cubefree, every prime exponent of \(n=u^2\) is either \(2\) or \(4\). Neither exponent can contribute a positive cube part, because

$2=2x+3y,\qquad 4=2x+3y,\qquad x,y\ge 0$

has only solutions with \(y=0\). Therefore every representation forces \(b=1\).

Conversely, if \(u\) contains a cube factor \(p^3\), then \(n\) contains \(p^6\), and we can allocate \(p^2\) to the square part and \(p^3\) to the cube part, making both \(a\) and \(b\) greater than \(1\).

So we subtract the number of cubefree integers up to \(\lfloor\sqrt N\rfloor\):

$Q(X)=\#\left\{u\le X : u \text{ cubefree}\right\},\qquad X=\lfloor\sqrt N\rfloor.$

By Möbius inversion,

$Q(X)=\sum_{d=1}^{\lfloor X^{1/3}\rfloor}\mu(d)\left\lfloor\frac{X}{d^3}\right\rfloor.$

Step 4: Handle the residual sixth-power exception

After removing the previous two boundary families, one exceptional type remains: prime sixth powers \(p^6\).

For a single-prime exponent \(e\), the requirement that both factors be nontrivial is

$e=2x+3y,\qquad x\ge 1,\qquad y\ge 1.$

This has solutions for \(e=5\) and for every \(e\ge 7\), but not for \(e=6\). Thus \(p^6\) is powerful, is not a squarefree cube, and is not a square with cubefree root, yet it still cannot be written with both \(a>1\) and \(b>1\).

If a powerful number has at least two distinct prime factors and survives Steps 2 and 3, then one prime can supply a square factor while another supplies a cube factor. So the only leftover obstruction is

$R(N)=\pi\left(\lfloor N^{1/6}\rfloor\right),$

the number of prime sixth powers up to \(N\).

Step 5: Assemble the final formula

The number \(1\) is included in \(P(N)\), and it is removed once by the squarefree-cube correction and once by the cubefree-square correction. Since it should be excluded only once, we add \(1\) back.

Therefore

$\boxed{F(N)=P(N)-C(N)-Q(\lfloor\sqrt N\rfloor)-R(N)+1.}$

This is exactly the formula implemented by the C++, Python, and Java implementations.

Worked Example: \(N=100\)

Here \(\lfloor N^{1/3}\rfloor=4\), and the squarefree values are \(1,2,3\). So

$P(100)=\left\lfloor\sqrt{100}\right\rfloor+\left\lfloor\sqrt{\frac{100}{8}}\right\rfloor+\left\lfloor\sqrt{\frac{100}{27}}\right\rfloor=10+3+1=14.$

Next, \(C(100)=3\), coming from \(1^3,2^3,3^3\). Also \(\lfloor\sqrt{100}\rfloor=10\), and the cubefree integers up to \(10\) are

$1,2,3,4,5,6,7,9,10,$

so \(Q(10)=9\). Finally, \(\lfloor 100^{1/6}\rfloor=2\), hence \(R(100)=\pi(2)=1\).

Therefore

$F(100)=14-3-9-1+1=2.$

The two admissible numbers are \(64=2^2\cdot 2^3\) and \(72=3^2\cdot 2^3\).

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they compute exact integer square roots, cube roots, and sixth roots. Each root starts from a floating-point estimate and then uses short correction loops, which removes boundary errors near \(64\)-bit limits.

They then mark squarefree integers up to \(\lfloor N^{1/3}\rfloor\) by crossing out multiples of \(p^2\) for primes \(p\le \lfloor N^{1/6}\rfloor\). Scanning that array simultaneously gives the base sum \(P(N)\) and the correction \(C(N)\).

For the cubefree correction, the implementation computes Möbius values up to \(\lfloor N^{1/6}\rfloor\) with a sieve and evaluates

$\sum_{d\le \lfloor N^{1/6}\rfloor}\mu(d)\left\lfloor\frac{\lfloor\sqrt N\rfloor}{d^3}\right\rfloor.$

Finally it counts primes up to \(\lfloor N^{1/6}\rfloor\) for the sixth-power correction and combines the four terms. The same formula is checked on small values such as \(N=100\), \(20000\), and \(3000000\) before evaluating the target input.

Complexity Analysis

Let \(V=\lfloor N^{1/3}\rfloor\) and \(D=\lfloor N^{1/6}\rfloor\). Marking squarefree integers up to \(V\) costs \(O(V\log\log V)\) time and \(O(V)\) memory. The Möbius sieve and the prime count up to \(D\) cost \(O(D)\) to \(O(D\log\log D)\) time and \(O(D)\) memory. Since \(V\) dominates \(D\), the overall method runs in \(O(N^{1/3}\log\log N)\) time with \(O(N^{1/3})\) memory.

Footnotes and References

1. Problem page: Project Euler 634
2. Powerful numbers: Wikipedia — Powerful number
3. Squarefree integers: Wikipedia — Square-free integer
4. Möbius function and inversion: Wikipedia — Möbius function
5. Inclusion-exclusion principle: Wikipedia — Inclusion-exclusion principle