# how many pairs $(A, B)$ are there such that: gcd $(A, B) = A \oplus B$

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 .

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.

• For N = 7 can you explain your answer ? – Way to infinity Dec 12 '13 at 6:35
• A=7, Try for B: 4 and 6. (7,4) : 111 xor 100 is 011, not the gcd 001. (7,6) : 111 xor 110 is 001, equals the gcd. * A = 6, try values for B: 4, 5. (6,4): 110 xor 100 is 010 equals gcd 2. * (6,5): 110 xor 101 is 011 exceeds gcd. A = 5. Try B value 4: (3,5) both odd is elminated. (5,4): 101 xor 100 is 001 equals gcd. * A = 4, Try B value 3 (4,3): 100 xor 011 is 111 exceeds gcd. * A = 3: Try B value 2 (3,2): 011 xor 010 is 001 equals gcd. * A = 2 B =1 do not have same bit length. Counting the number of successes (lines with *) we get answer of N= 7 is 5. – P Vanchinathan Dec 12 '13 at 7:52

First of all , A and B has the same number of digits in binary expansion. It's easy to prove.

Next suppose A and B has n binary digit(A>B), and gcd(A,B) has k(k < n) digit. If A xor B = gcd(A,B), then the leftmost (n-k)digit of A and B are the same.Such that A-B < 2*gcd(A,B). So, we get A xor B = gcd(A,B) only if B = A - gcd(A,B).

Enumeration pair A = i*k, B = (i-1)*k, (1<=B <= A <= N), O(nlog(n))