2
$\begingroup$

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 .

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For N = 7 can you explain your answer ? $\endgroup$ – Way to infinity Dec 12 '13 at 6:35
  • $\begingroup$ 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. $\endgroup$ – P Vanchinathan Dec 12 '13 at 7:52
1
$\begingroup$

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))

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.