This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A117494 #54 Jun 21 2025 11:49:56
%S A117494 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,
%T A117494 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,
%U A117494 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
%N A117494 a(n) is the number of m's, 1 <= m <= n, where gcd(m,n) is prime.
%C A117494 Dirichlet convolution of A000010 (Euler phi) and A010051 (characteristic function of primes), therefore also Möbius transform of A069359. - _Antti Karttunen_, Nov 17 2021
%H A117494 Antti Karttunen, <a href="/A117494/b117494.txt">Table of n, a(n) for n = 1..65537</a>
%F A117494 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
%F A117494 a(n) = Sum_{distinct primes p dividing n} phi(n/p), where phi(k) is the Euler totient function. - _Daniel Suteu_, Jun 23 2018
%F A117494 From _Antti Karttunen_, Nov 17 2021: (Start)
%F A117494 a(n) = Sum_{d|n} A008683(n/d) * A069359(d).
%F A117494 a(n) = Sum_{d|n} A000010(n/d) * A010051(d).
%F A117494 a(n) = A349338(n) - A000010(n).
%F A117494 a(A005117(n)) = A300251(A005117(n)) for all n >= 1. (End)
%F A117494 a(n) = 1 iff n = 4 or n is prime (A175787). - _Bernard Schott_, Nov 18 2021
%F A117494 Sum_{k=1..n} a(k) ~ 3 * A085548 * n^2 / Pi^2. - _Vaclav Kotesovec_, Nov 20 2021
%e A117494 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.)
%e A117494 So a(12) = 4.
%p A117494 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
%t A117494 f[n_] := Length@ Select[GCD[n, Range@n], PrimeQ@ # &]; Array[f, 84] (* _Robert G. Wilson v_, Apr 06 2006 *)
%t A117494 Table[Count[Range@ n, _?(PrimeQ@ GCD[#, n] &)], {n, 84}] (* _Michael De Vlieger_, Feb 25 2018 *)
%t A117494 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 *)
%o A117494 (PARI) A117494(n) = sum(k=1,n,isprime(gcd(n,k))); \\ _Antti Karttunen_, Feb 25 2018
%o A117494 (PARI) a(n) = my(f=factor(n)[, 1]); sum(k=1, #f, eulerphi(n/f[k])); \\ _Daniel Suteu_, Jun 23 2018
%o A117494 (PARI) A117494(n) = sumdiv(n,d,eulerphi(n/d)*isprime(d)); \\ _Antti Karttunen_, Nov 17 2021
%Y A117494 Cf. A000010, A008683, A010051, A069359, A085548, A122410, A122411, A175787, A349338.
%Y A117494 Coincides with A300251 on squarefree numbers, A005117.
%K A117494 nonn
%O A117494 1,6
%A A117494 _Leroy Quet_, Mar 22 2006
%E A117494 More terms from _Emeric Deutsch_, Apr 01 2006