P464
projecteuler.net

Möbius Function and Intervals

ℹ️Published on Sunday, 23rd March 2014, 01:00 am; Solved by 361;
Difficulty rating: 60%

The Möbius function, denoted $\mu(n)$, is defined as:

  • $\mu(n) = (-1)^{\omega(n)}$ if $n$ is squarefree (where $\omega(n)$ is the number of distinct prime factors of $n$)
  • $\mu(n) = 0$ if $n$ is not squarefree.

Let $P(a, b)$ be the number of integers $n$ in the interval $[a, b]$ such that $\mu(n) = 1$.
Let $N(a, b)$ be the number of integers $n$ in the interval $[a, b]$ such that $\mu(n) = -1$.
For example, $P(2,10) = 2$ and $N(2,10) = 4$.

Let $C(n)$ be the number of integer pairs $(a, b)$ such that:

  • $1\le a \le b \le n$,
  • $99 \cdot N(a, b) \le 100 \cdot P(a, b)$, and
  • $99 \cdot P(a, b) \le 100 \cdot N(a, b)$.

For example, $C(10) = 13$, $C(500) = 16676$ and $C(10\,000) = 20155319$.

Find $C(20\,000\,000)$.



Soluzione

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