A358558 a(n) is the number of pairs (k,m) of positive integers with 1 <= k < m <= n such that gcd(k,m) = 2^t, t > 0.

0, 0, 0, 1, 1, 3, 3, 6, 6, 10, 10, 14, 14, 20, 20, 27, 27, 33, 33, 41, 41, 51, 51, 59, 59, 71, 71, 83, 83, 91, 91, 106, 106, 122, 122, 134, 134, 152, 152, 168, 168, 180, 180, 200, 200, 222, 222, 238, 238, 258, 258, 282, 282, 300, 300, 324, 324, 352, 352, 368, 368

Offset: 1

Author

Bernard Schott, Nov 23 2022

Keywords

• nonn

Comments

Integers k and m such that gcd(k,m) = 2^t, t > 0, are called 2-Friendly in Project Euler (see link).

If k=m were included then the number of pairs would A049690(floor(n/2)), and subtracting those cases is the 2nd formula.

If gcd(k,m) = 2^t, t > 0 is replaced by gcd(k,m) = 2*t, t > 0, with 1 <= k < m <= n+4, sequence becomes A008805.

Examples

			a(6)=3 because gcd(2,4)=2, gcd(2,6)=2, gcd(4,6)=2.
12 and 18 are not 2-friendly because gcd(12,18) = 6.
		

Links

• Project Euler, Problem 643: 2-Friendly.

Crossrefs

Cf. A000079, A000523, A008805, A049690.

Programs

Mathematica

q[n_] := n > 1 && n == 2^IntegerExponent[n, 2]; a[n_] := Module[{c = 0}, Do[Do[If[q[GCD[k, m]], c++], {k, 2, m - 1}], {m, 2, n}]; c]; Array[a, 60] (* Amiram Eldar, Nov 23 2022 *)

PARI

a(n) = { my(res = 0); forvec(x = vector(2, i, [1,floor(n/2)]), c = gcd(x[1], x[2]); if(c == 1 << logint(c, 2), res++ ) , 2 ); res } \\ David A. Corneth, Nov 24 2022

Formula

a(2*n) = a(2*n+1).

a(n) = A049690(floor(n/2)) - A000523(n).