A122411 -id:A122411

Search: a122411 -id:a122411

Displaying 1-3 of 3 results found.

page 1

A117494

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

+10
8

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

(list; graph; refs; listen; history; text; internal format)

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.

KEYWORD

nonn

AUTHOR

Leroy Quet, Mar 22 2006

EXTENSIONS

More terms from Emeric Deutsch, Apr 01 2006

STATUS

approved

A347104

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

+10
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

Moebius transform of A328260.

LINKS

Seiichi Manyama, Table of n, a(n) for n = 1..10000

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

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}]

PROG

(PARI) a(n) = sumdiv(n, d, moebius(n/d)*d*omega(d)); \\ Michel Marcus, Aug 18 2021

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Ilya Gutkovskiy, Aug 18 2021

STATUS

approved

A122410

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

+10
3

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

LINKS

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

EXAMPLE

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.

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

PROG

(PARI) A122410(n) = sum(k=1, n, isprimepower(gcd(n, k))); \\ Antti Karttunen, Feb 25 2018

CROSSREFS

Cf. A122411.

KEYWORD

nonn

AUTHOR

Leroy Quet, Sep 02 2006

EXTENSIONS

Extended by Ray Chandler, Sep 06 2006

STATUS

approved

page 1

Search completed in 0.005 seconds