VOOZH about

URL: https://oeis.org/A117494

⇱ A117494 - OEIS

login
A117494
a(n) is the number of m's, 1 <= m <= n, where gcd(m,n) is prime.
15
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
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 *)
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 *)
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
Coincides with A300251 on squarefree numbers, A005117.
Sequence in context: A282016 A238848 A387064 * A342913 A221490 A231819
KEYWORD
nonn
AUTHOR
Leroy Quet, Mar 22 2006
EXTENSIONS
More terms from Emeric Deutsch, Apr 01 2006
STATUS
approved