Can I make general formula for this problem I want to find how many pairs of numbers satisfy this condition on $[1,n]$.
For given $n$ , how many pairs $(a,b)$ are there such that $gcd(a,b) = 2^t , t > 0 $ for some whole number $t$.
All pairs $(a,b)$ should be bounded by $1\leq a < b \leq n $ .
Now I know that if $2|a \land2|b \implies 2|gcd(a,b)$ and this excludes all odd numbers .
But the space is too big to count for very large $n$.
Can I make general formula for $\forall n $ ?
$a,b,n,t$ are whole numbers.
 A: Let $\psi(n)=\#\{(x,y) : 1 \leqslant x,y \leqslant n, \gcd(x, y) = 1\}$. Then, for $1 \leqslant d \leqslant n$,
$$\#\{(x,y) : 1 \leqslant x,y \leqslant n, \gcd(x, y) = d\} = \psi\big(\lfloor n/d \rfloor\big),$$
and the union of these sets is just $\{(x,y) : 1 \leqslant x,y \leqslant n\}$. This gives
$$\color{blue}{\sum_{d=1}^{n}\psi\big(\lfloor n/d \rfloor\big)=n^2} \implies \psi(n)=\sum_{d=1}^{n}\mu(d)\lfloor n/d \rfloor^2$$
(by the "second" Möbius inversion formula). This leads to a solution of your problem:
$$2^t \leqslant n \implies \#\{(a, b) : 1 \leqslant a < b \leqslant n, \gcd(a, b) = 2^t \} = \frac{\psi(\lfloor 2^{-t} n \rfloor) - 1}{2}.$$
There's an algorithm which computes $\psi(n)$ in $\mathcal{O}(n^{1+\epsilon})$ time and $\mathcal{O}(n^{1/2+\epsilon})$ space (without computing any values of $\mu$). The idea is to use the "blue" formula above recursively (or rather iteratively), noting that there are just $\mathcal{O}(\sqrt{n})$ different values of $\lfloor n/d \rfloor$ for $1 \leqslant d \leqslant n$, which allows to simplify the sum; namely, for any $1 \leqslant k \leqslant n$,
$$n^2=\sum_{d=1}^{n}\psi\left(\left\lfloor\frac{n}{d}\right\rfloor\right)=\sum_{d=1}^{\lfloor n/(k+1) \rfloor}\psi\left(\left\lfloor\frac{n}{d}\right\rfloor\right)+\sum_{d=1}^{k}\psi(d)\left(\left\lfloor\frac{n}{d}\right\rfloor-\left\lfloor\frac{n}{d+1}\right\rfloor\right),$$
and we may put $k=\lfloor\sqrt{n}\rfloor$ here. This recurrence for $\psi(n)$ gives the algorithm.
