Project Euler

2-Friendly Divisors

A divisor d of n is called unitary (or 2-friendly) if gcd(d, n/d) = 1. The number of unitary divisors of n is 2^(omega(n)), where omega(n) counts the distinct prime factors of n. Compute T(N) = sum...

Source sync Apr 19, 2026

Problem #0643

Level Level 18

Solved By 761

Languages C++, Python

Answer 968274154

Length 211 words

number_theoryanalytic_matharithmetic

Two positive integers $a$ and $b$ are $2$-friendly when $\gcd (a,b) = 2^t, t > 0$. For example, $24$ and $40$ are $2$-friendly because $\gcd (24,40) = 8 = 2^3$ while $24$ and $36$ are not because $\gcd (24,36) = 12 = 2^2\cdot 3$ not a power of $2$.

Let $f(n)$ be the number of pairs, $(p,q)$, of positive integers with $1\le p < q\le n$ such that $p$ and $q$ are $2$-friendly. You are given $f(10^2) = 1031$ and $f(10^6) = 321418433$ modulo $1\,000\,000\,007$.

Find $f(10^{11})$ modulo $1\,000\,000\,007$.

Problem 643: 2-Friendly Divisors

Mathematical Foundation

Theorem 1 (Dirichlet Convolution Identity). For all $n \ge 1$ ,

2^{\omega(n)} = \sum_{d \mid n} \mu^2(d).

Proof. Both sides are multiplicative functions of $n$ . It suffices to verify agreement on prime powers $n = p^a$ ( $a \ge 1$ ). Left-hand side: $2^{\omega(p^a)} = 2^1 = 2$ . Right-hand side: $\sum_{d \mid p^a} \mu^2(d) = \mu^2(1) + \mu^2(p) + \mu^2(p^2) + \cdots + \mu^2(p^a) = 1 + 1 + 0 + \cdots + 0 = 2$ . Since both multiplicative functions agree on all prime powers, they agree on all positive integers. $\square$

Lemma 1 (Summatory Formula). By Theorem 1 and Dirichlet hyperbola interchange,

T(N) = \sum_{d=1}^{N} \mu^2(d) \left\lfloor \frac{N}{d} \right\rfloor.

Proof. Swap the order of summation:

T(N) = \sum_{n=1}^{N} \sum_{d \mid n} \mu^2(d) = \sum_{d=1}^{N} \mu^2(d) \sum_{\substack{n \le N \\ d \mid n}} 1 = \sum_{d=1}^{N} \mu^2(d) \left\lfloor \frac{N}{d} \right\rfloor.

$\square$

Theorem 2 (Squarefree Counting). The prefix sum of the squarefree indicator is

Q(M) = \sum_{d=1}^{M} \mu^2(d) = \sum_{k=1}^{\lfloor\sqrt{M}\rfloor} \mu(k) \left\lfloor \frac{M}{k^2} \right\rfloor.

Proof. We have $\mu^2(d) = \sum_{k^2 \mid d} \mu(k)$ (Mobius inversion of the indicator that $d$ is squarefree). Summing over $d \le M$ :

Q(M) = \sum_{d=1}^{M} \sum_{k^2 \mid d} \mu(k) = \sum_{k=1}^{\lfloor\sqrt{M}\rfloor} \mu(k) \left\lfloor \frac{M}{k^2} \right\rfloor.

$\square$

Lemma 2 (Dirichlet Series). The generating Dirichlet series is

\sum_{n=1}^{\infty} \frac{2^{\omega(n)}}{n^s} = \frac{\zeta(s)^2}{\zeta(2s)}, \qquad \Re(s) > 1.

Proof. By the Euler product, $\sum 2^{\omega(n)} n^{-s} = \prod_p (1 + 2p^{-s} + 2p^{-2s} + \cdots) = \prod_p \frac{1 + p^{-s}}{1 - p^{-s}} = \prod_p \frac{(1 - p^{-s})^{-2}}{(1 - p^{-2s})^{-1}} = \zeta(s)^2 / \zeta(2s)$ . $\square$

Theorem 3 (Asymptotic). As $N \to \infty$ ,

T(N) = \frac{6}{\pi^2} N \ln N + C N + O(\sqrt{N} \ln N)

for an explicit constant $C$ .

Proof. From Lemma 1, apply the hyperbola method. The main term comes from $\sum_{d \le N} \mu^2(d)/d \sim (6/\pi^2) \ln N$ combined with partial summation. $\square$

Editorial

We sieve mu(k) for k <= sqrt(N). Finally, group by q = floor(N/d); there are O(sqrt(N)) distinct values of q.

Pseudocode

Sieve mu(k) for k <= sqrt(N)
Precompute Q(M) = sum_{d<=M} mu^2(d) using Theorem 2
Hyperbola method on sum_{d=1}^{N} mu^2(d) * floor(N/d)
Group by q = floor(N/d); there are O(sqrt(N)) distinct values of q

Complexity Analysis

Time: $O(N^{2/3})$ . The outer loop runs $O(\sqrt{N})$ iterations. Each call to $Q(M)$ costs $O(M^{1/2})$ , but preprocessing $\mu$ up to $\sqrt{N}$ and caching prefix sums reduces total work to $O(N^{2/3})$ .
Space: $O(\sqrt{N})$ for the Mobius sieve and cached prefix sums.

Answer

\boxed{968274154}

C++ project_euler/problem_643/solution.cpp

#include <iostream>

// Reference executable for problem_643.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "968274154";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

Python project_euler/problem_643/solution.py

"""Reference executable for problem_643.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '968274154'

def solve():
    return ANSWER


if __name__ == "__main__":
    print(solve())