A389271 Number of unordered pairs of n-bit numbers x, y such that gcd(x,y) = xor(x,y).

0, 1, 3, 9, 19, 45, 93, 202, 408, 853, 1713, 3512, 7035, 14216, 28468, 57195, 114346, 229096, 457894, 916253, 1830725, 3660780, 7315770, 14625120, 29229546, 58431467, 116797978, 233501798, 466801930, 933298077

Offset

1,3

Comments

Assuming x < y, we have gcd(x,y) = xor(x,y) = y-x.

Links

Table of n, a(n) for n=1..30.

Way to infinity, How many pairs (A, B) are there such that: gcd(A, B) = A \oplus B, Mathematics StackExchange, 2014.

Example

For n = 3, in binary notation we have a(3) = 3 such pairs: gcd(100,101) = 1 = xor(100,101), gcd(100,110) = 10 = xor(100,110), and gcd(110,111) = 1 = xor(110,111).

Prog

(PARI) a389271(n) = sum(g=1, 2^(n-1)-1, my(c=0); forstep(t=2^(n-1), 2^n-1, Mod(0, g), c += bitand(t, t+g)==t; ); c);

Crossrefs

Sequence in context: A146393 A147431 A329145 * A348377 A147334 A147463

Adjacent sequences: A389268 A389269 A389270 * A389272 A389273 A389274

Keyword

nonn,more

Author

Max Alekseyev, Sep 27 2025

Status

approved