cp's OEIS Frontend

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.

Showing 1-3 of 3 results.

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

Original entry on oeis.org

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

Views

Author

Leroy Quet, Mar 22 2006

Keywords

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

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

A122410 a(n) is the sum of j's for those k's, 1 <= k <= n, where gcd(k,n) = p^j, p = prime.

Original entry on oeis.org

0, 1, 1, 3, 1, 3, 1, 7, 4, 5, 1, 8, 1, 7, 6, 15, 1, 10, 1, 14, 8, 11, 1, 18, 6, 13, 13, 20, 1, 14, 1, 31, 12, 17, 10, 26, 1, 19, 14, 32, 1, 20, 1, 32, 22, 23, 1, 38, 8, 26, 18, 38, 1, 31, 14, 46, 20, 29, 1, 36, 1, 31, 30, 63, 16, 32, 1, 50, 24, 34, 1, 58, 1, 37, 32, 56, 16, 38, 1, 68, 40
Offset: 1

Views

Author

Leroy Quet, Sep 02 2006

Keywords

Examples

			The positive integers k, k <= 12, where gcd(k,12) = a power of a prime, are 1, 2, 3, 4, 8, 9 and 10; gcd(1,12) = p^0, gcd(2,12) = 2^1, gcd(3,12) = 3^1, gcd(4,12) = 2^2, gcd(8,12) = 2^2, gcd(9,12) = 3^1 and gcd(10,12) = 2^1. The sum of the exponents raising the primes is 0+1+1+2+2+1+1 = 8. So a(12) = 8.

Links

Crossrefs

Cf. A000010, A013661, A100995, A116512, A122411.

Programs

  • Mathematica
    f[n_] := Plus @@ Last /@ Flatten[Select[FactorInteger[GCD[Range[n], n]], Length[ # ] == 1 &], 1]; Table[f[n], {n, 80}] (* Ray Chandler, Sep 06 2006 *)
a[n_] := Module[{f = FactorInteger[n], p, e}, p = f[[;; , 1]]; e = f[[;; , 2]]; n * Times @@ (1-1/p) * Total[p*(1-1/p^e)/(p - 1)^2]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Jun 21 2025 *)
  • PARI
    A122410(n) = sum(k=1,n,isprimepower(gcd(n,k))); \\ Antti Karttunen, Feb 25 2018
  • PARI
    a(n) = {my(f = factor(n), p = f[,1], e = f[,2]); eulerphi(f) * sum(i = 1, #p, p[i] * (1 - 1/p[i]^e[i]) / (p[i] - 1)^2);} \\ Amiram Eldar, Jun 21 2025

Formula

From Ridouane Oudra, Jun 06 2025: (Start)
a(p^m) = (p^m-1)/(p-1), for p prime and m >= 0.
a(n) = Sum_{p|n, p prime} phi(n/p), for n a squarefree.
More generally, for all n we have:
a(n) = Sum_{d|n, d is a prime power} A100995(d)*phi(n/d).
a(n) = Sum_{p|n, p prime} ((p^v(n,p)-1)/(p-1))*phi(n/p^v(n,p)), where p^v(n,p) is the highest power of p dividing n.
a(n) = phi(n) * Sum_{p|n, p prime} p*(1-p^(-v(n,p)))/((1-p)^2). (End)
Sum_{k=1..n} a(k) ~ c * zeta(2) * n^2 / 2, where c = Sum_{p prime} (p^2/(p^2-1)^2) = 0.68073222355480674093... . - Amiram Eldar, Jun 21 2025

Extensions

Extended by Ray Chandler, Sep 06 2006

A347104 Dirichlet g.f.: primezeta(s-1) * zeta(s-1) / zeta(s).

Original entry on oeis.org

0, 2, 3, 2, 5, 7, 7, 4, 6, 13, 11, 10, 13, 19, 22, 8, 17, 18, 19, 18, 32, 31, 23, 20, 20, 37, 18, 26, 29, 38, 31, 16, 52, 49, 58, 24, 37, 55, 62, 36, 41, 56, 43, 42, 54, 67, 47, 40, 42, 60, 82, 50, 53, 54, 94, 52, 92, 85, 59, 60, 61, 91, 78, 32, 112, 92, 67, 66, 112, 106, 71, 48, 73, 109, 100
Offset: 1

Views

Author

Ilya Gutkovskiy, Aug 18 2021

Keywords

Comments

a(n) is the sum of the prime terms in row n of A050873.
Moebius transform of A328260.

Links

Crossrefs

Cf. A000010, A001221, A008472, A010051, A018804, A050873, A061397, A078439, A117494, A122411, A255655, A328260, A329354.

Programs

  • Mathematica
    Table[DivisorSum[n, MoebiusMu[n/#] # PrimeNu[#] &], {n, 1, 75}]
Table[DivisorSum[n, # EulerPhi[n/#] &, PrimeQ[#] &], {n, 1, 75}]
Table[Sum[Boole[PrimeQ[GCD[n, k]]] GCD[n, k], {k, 1, n}], {n, 1, 75}]
  • PARI
    a(n) = sumdiv(n, d, moebius(n/d)*d*omega(d)); \\ Michel Marcus, Aug 18 2021

Formula

a(n) = Sum_{d|n} mu(n/d) * d * omega(d).
a(n) = Sum_{p|n, p prime} p * phi(n/p).
a(n) = Sum_{k=1..n} A010051(gcd(n,k)) * gcd(n,k).
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.