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,6

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

Links

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

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

Example

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.

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

Prog

(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

Crossrefs

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

Coincides with A300251 on squarefree numbers, A005117.

Sequence in context: A002016 A282016 A238848 * A342913 A221490 A231819

Adjacent sequences: A117491 A117492 A117493 * A117495 A117496 A117497

Keyword

nonn

Author

Leroy Quet, Mar 22 2006

Extensions

More terms from Emeric Deutsch, Apr 01 2006

Status

approved