P362
projecteuler.net

Squarefree Factors

ℹ️Published on Sunday, 11th December 2011, 07:00 am; Solved by 533;
Difficulty rating: 70%

Consider the number $54$.
$54$ can be factored in $7$ distinct ways into one or more factors larger than $1$:
$54$, $2 \times 27$, $3 \times 18$, $6 \times 9$, $3 \times 3 \times 6$, $2 \times 3 \times 9$ and $2 \times 3 \times 3 \times 3$.
If we require that the factors are all squarefree only two ways remain: $3 \times 3 \times 6$ and $2 \times 3 \times 3 \times 3$.

Let's call $\operatorname{Fsf}(n)$ the number of ways $n$ can be factored into one or more squarefree factors larger than $1$, so $\operatorname{Fsf}(54)=2$.

Let $S(n)$ be $\sum \operatorname{Fsf}(k)$ for $k=2$ to $n$.

$S(100)=193$.

Find $S(10\,000\,000\,000)$.



Soluzione

Last modified: May 01, 2025. Website built with Franklin.jl and the lovely Julia programming language.