A074944 Number of k with 1 <= k <= n such that gcd(n,k) = tau(k), where tau is A000005, number of divisors function.

1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 3, 2, 2, 1, 3, 1, 2, 2, 3, 1, 5, 1, 3, 2, 2, 1, 5, 1, 2, 2, 3, 1, 3, 1, 4, 2, 2, 1, 5, 1, 2, 2, 5, 1, 5, 1, 3, 2, 2, 1, 5, 1, 2, 2, 3, 1, 5, 1, 4, 2, 2, 1, 7, 1, 2, 2, 5, 1, 4, 1, 3, 2, 2, 1, 9, 1, 2, 2, 3, 1, 5, 1, 6, 2

Offset

1,2

Links

Antti Karttunen, Table of n, a(n) for n = 1..16384

Amiram Eldar, Plot of Sum_{k=1..n} a(k)/(n*log(n)) for n = 2..10^5.

Formula

Sum_{i=1..n} a(i) seems to be asymptotic to c*n*log(n) with 0.5 < c < 0.6.

The above conjecture seems to be wrong. See the graph in the Links section. - Amiram Eldar, Mar 10 2026

Mathematica

a[n_] := Sum[If[GCD[n, k] == DivisorSigma[0, k], 1, 0], {k, 1, n}]; Array[a, 105] (* Amiram Eldar, Mar 10 2026 *)

Prog

(PARI) a(n)=sum(k=1, n, if(gcd(n, k)-numdiv(k), 0, 1))

Crossrefs

Cf. A000005.

Sequence in context: A161288 A185217 A131456 * A245041 A161315 A161249

Adjacent sequences: A074941 A074942 A074943 * A074945 A074946 A074947

Keyword

easy,nonn

Author

Benoit Cloitre, Oct 05 2002

Status

approved