A117494 a(n) is the number of m's, 1 <= m <= n, where gcd(m,n) is prime.

0, 1, 1, 1, 1, 3, 1, 2, 2, 5, 1, 4, 1, 7, 6, 4, 1, 8, 1, 6, 8, 11, 1, 8, 4, 13, 6, 8, 1, 14, 1, 8, 12, 17, 10, 10, 1, 19, 14, 12, 1, 20, 1, 12, 14, 23, 1, 16, 6, 24, 18, 14, 1, 24, 14, 16, 20, 29, 1, 20, 1, 31, 18, 16, 16, 32, 1, 18, 24, 34, 1, 20, 1, 37, 28, 20, 16, 38, 1, 24, 18, 41, 1, 28

Offset: 1

Author

Leroy Quet, Mar 22 2006

Keywords

• nonn

Comments

Dirichlet convolution of A000010 (Euler phi) and A010051 (characteristic function of primes), therefore also Möbius transform of A069359. - Antti Karttunen, Nov 17 2021

Examples

			Of the positive integers <= 12, exactly four (2, 3, 9 and 10) have a GCD with 12 that is prime. (gcd(2,12) = 2, gcd(3,12) = 3, gcd(9,12) = 3, gcd(10,12) = 2.)
So a(12) = 4.
		

Links

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

Crossrefs

Cf. A000010, A008683, A010051, A069359, A085548, A122410, A122411, A175787, A349338.

Coincides with A300251 on squarefree numbers, A005117.

Programs

Maple

a:=proc(n) local c,m: c:=0: for m from 1 to n do if isprime(gcd(m,n))=true then c:=c+1 else c:=c fi od: end: seq(a(n),n=1..100); # Emeric Deutsch, Apr 01 2006

Mathematica

f[n_] := Length@ Select[GCD[n, Range@n], PrimeQ@ # &]; Array[f, 84] (* Robert G. Wilson v, Apr 06 2006 *)
Table[Count[Range@ n, ?(PrimeQ@ GCD[#, n] &)], {n, 84}] (* _Michael De Vlieger, Feb 25 2018 *)
a[n_] := Module[{f = FactorInteger[n], p, e}, p = f[[;; , 1]]; e = f[[;; , 2]]; n * Times @@ (1-1/p) * Total[1/(p - (Boole[# == 1] & /@ e))]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jun 21 2025 *)

PARI

A117494(n) = sum(k=1,n,isprime(gcd(n,k))); \\ Antti Karttunen, Feb 25 2018

PARI

a(n) = my(f=factor(n)[, 1]); sum(k=1, #f, eulerphi(n/f[k])); \\ Daniel Suteu, Jun 23 2018

PARI

A117494(n) = sumdiv(n,d,eulerphi(n/d)*isprime(d)); \\ Antti Karttunen, Nov 17 2021

Formula

Dirichlet g.f: P(s)*Z(s-1)/Z(s) with P(s) the prime zeta function and Z(s) the Riemann zeta function. - Pierre-Louis Giscard, Jul 16 2014

a(n) = Sum_{distinct primes p dividing n} phi(n/p), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 23 2018

From Antti Karttunen, Nov 17 2021: (Start)

a(n) = Sum_{d|n} A008683(n/d) * A069359(d).

a(n) = Sum_{d|n} A000010(n/d) * A010051(d).

a(n) = A349338(n) - A000010(n).

a(A005117(n)) = A300251(A005117(n)) for all n >= 1. (End)

a(n) = 1 iff n = 4 or n is prime (A175787). - Bernard Schott, Nov 18 2021

Sum_{k=1..n} a(k) ~ 3 * A085548 * n^2 / Pi^2. - Vaclav Kotesovec, Nov 20 2021

Extensions

More terms from Emeric Deutsch, Apr 01 2006