Given an integer N,how can I find how many pairs $(A, B)$ are there such that: gcd $(A, B) = $A$ \oplus B$ where $ 1 ≤ B ≤ A ≤ N $.
Here gcd $(A, B)$ means the greatest common divisor of the numbers A and B. And $A \oplus B$ is the value of the bitwise $\oplus $ operation on the binary representation of A and B.
For example , if I have been given the value of N is $20000000$ , then the answer is $34866117 $ . I am trying to solve this problem by experimenting with small values of N .
Best Answer
Suppose $B$ has $n$ digits and $A$ has $n+k$ digits in their binary expansion. Then the leftmost $k$ digits of $B$ would be $0$ and $A$ would have a $1$ in one of those positions. So XOR operation would lead to a number having bit $1$ in the same position. Hence, A xor B > B. But gcd(A,B) cannot exceed B.
Also both A,B cannot be odd as their gcd would be odd while XOR would yield make the least significant bit $0$.
So you have to search among pairs of numbers A,B having same number of bits, narrowing down your search to within pairs (A,B) with $B< A < 2B$, and not both odd.