Search ProblemsRSS Feed
projecteuler.net

2-Friendly

Problem 643 Published on Saturday, 17th November 2018, 07:00 pm; Solved by 209

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\lt 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$.