Project Euler 634 - Numbers of the form a^2*b^3

Official link:

Note: For some reason, I cannot figure out why I am off by 1 on some answers, but I'm more than happy with my implementation

Thought Process

This problem was very interesting and I had to learn a lot of new concepts.

The first and most important step to solving this problem is finding out about Powerful Numbers which are numbers that can be expressed as a^2*b^3 but a or b can be 1, very similar to what our question wants.

We get our first hint on the page which is that a^2*b^3 can be uniquely represented if b is squarefree, therefore we come up with the following:

Point 1 can be easily done with a Mobius Sieve, I made a function for this (and it is generalised) it is in my Essential Functions.

Point 2 was the crux of the problem, to efficiently find the number of cube-free numbers. I thought we could generalise the Mobius Function, and at first I wrongfully applied it until I found Aposotols Generalised Mobius Function.

Using this we can easily find not only cube-free but k-free integers, this function was also added to my Essential Functions Page as well as mathslib.

Putting everything together, we have a very elegant equation for the final problem, π is the prime counting function

Interactive Code

Input an integer (yourinput)

Code will output F(yourinput)

Note: The answer could be 1 or 2 off the actual correct answer