0%

# Problem 643

## $2$-Friendly

Two positive integers $a$ and $b$ are $2$-friendly when $\text{gcd}(a,b)=2^t,t>0$. For example, $24$ and $40$ are $2$-friendly because $\text{gcd}(24,40)=8=2^3$ while $24$ and $36$ are not because $\text{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$.

## $2$-友善数

.

Find $f(10^{11})$并对$1\ 000\ 000\ 007$取余。