A063659 -id:A063659 - cp's OEIS frontend

A384039 The number of integers k from 1 to n such that gcd(n,k) is a powerful number.

1, 1, 2, 3, 4, 2, 6, 6, 7, 4, 10, 6, 12, 6, 8, 12, 16, 7, 18, 12, 12, 10, 22, 12, 21, 12, 21, 18, 28, 8, 30, 24, 20, 16, 24, 21, 36, 18, 24, 24, 40, 12, 42, 30, 28, 22, 46, 24, 43, 21, 32, 36, 52, 21, 40, 36, 36, 28, 58, 24, 60, 30, 42, 48, 48, 20, 66, 48, 44

Offset: 1

Amiram Eldar, May 18 2025

The number of integers k from 1 to n such that the powerfree part (A055231) of gcd(n,k) is 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A001694, A005117, A050873, A055231, A063658, A206369.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), this sequence (powerful), A384040 (cubefull), A384041 (exponentially odd), A384042 (5-rough).

f[p_, e_] := If[e == 1, p-1, (p^2-p+1)*p^(e-2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, f[i,1]-1, (f[i,1]^2-f[i,1]+1)*f[i,1]^(f[i,2]-2)));}

Multiplicative with a(p^e) = (p^2-p+1)*p^(e-2) if e >= 2, and p-1 otherwise.
a(n) >= A000010(n), with equality if and only if n is squarefree (A005117).
Dirichlet g.f.: zeta(s-1) * Product_{p prime} (1 - 1/p^s + 1/p^(2*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/p^4) = 0.66922021803510257394... .

A384040 The number of integers k from 1 to n such that gcd(n,k) is a cubefull number.

Original entry on oeis.org

1, 1, 2, 2, 4, 2, 6, 5, 6, 4, 10, 4, 12, 6, 8, 10, 16, 6, 18, 8, 12, 10, 22, 10, 20, 12, 19, 12, 28, 8, 30, 20, 20, 16, 24, 12, 36, 18, 24, 20, 40, 12, 42, 20, 24, 22, 46, 20, 42, 20, 32, 24, 52, 19, 40, 30, 36, 28, 58, 16, 60, 30, 36, 40, 48, 20, 66, 32, 44, 24

Offset: 1

Amiram Eldar, May 18 2025

The number of integers k from 1 to n such that the cubefree part (A360539) of gcd(n,k) is 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A005117, A036966, A078429, A360539, A254926.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), this sequence (cubefull), A384041 (exponentially odd), A384042 (5-rough).

f[p_, e_] := Switch[e, 1, p-1, 2, p^2-p, , (p^3-p^2+1)*p^(e-3)]; a[1] = 1; a[n] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,2] == 1, f[i,1]-1, if(f[i,2] == 2, f[i,1]*(f[i,1]-1), (f[i,1]^3-f[i,1]^2+1)*f[i,1]^(f[i,2]-3))));}

Multiplicative with a(p^e) = (p^3-p^2+1)*p^(e-3) if e >= 3, p*(p-1) if e = 2, and p-1 otherwise.
a(n) >= A384039(n), with equality if and only if n is squarefree (A005117).
Dirichlet g.f.: zeta(s-1) * Product_{p prime} (1 - 1/p^s + 1/p^(3*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/p^6) = 0.62159731307414305346... .

A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 7, 8, 10, 11, 9, 13, 14, 15, 13, 17, 16, 19, 15, 21, 22, 23, 21, 24, 26, 25, 21, 29, 30, 31, 27, 33, 34, 35, 24, 37, 38, 39, 35, 41, 42, 43, 33, 40, 46, 47, 39, 48, 48, 51, 39, 53, 50, 55, 49, 57, 58, 59, 45, 61, 62, 56, 53, 65, 66, 67, 51

Offset: 1

Amiram Eldar, May 18 2025

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A268335.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), A384040 (cubefull), this sequence (exponentially odd), A384042 (5-rough).

f[p_, e_] := ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, ((f[i,1]^2+f[i,1]-1)*f[i,1]^(f[i,2]-1) - (-1)^f[i,2])/(f[i,1] + 1));}

Multiplicative with a(p^e) = ((p^2+p-1)*p^(e-1) - (-1)^e)/(p+1).
a(n) >= A000010(n), with equality if and only if n = 1.
Dirichlet g.f.: (zeta(s-1)*zeta(2*s)/zeta(s)) * Product_{p prime} (1 + 1/p^s - 1/p^(3*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 - 1/p^2 + 1/(p^2+1)) = 0.93749428273130025078... .

A384042 The number of integers k from 1 to n such that gcd(n,k) is a 5-rough number (A007310).

Original entry on oeis.org

1, 1, 2, 2, 5, 2, 7, 4, 6, 5, 11, 4, 13, 7, 10, 8, 17, 6, 19, 10, 14, 11, 23, 8, 25, 13, 18, 14, 29, 10, 31, 16, 22, 17, 35, 12, 37, 19, 26, 20, 41, 14, 43, 22, 30, 23, 47, 16, 49, 25, 34, 26, 53, 18, 55, 28, 38, 29, 59, 20, 61, 31, 42, 32, 65, 22, 67, 34, 46

Offset: 1

Amiram Eldar, May 18 2025

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A000010, A003586, A007310, A065330, A065331, A372671.

The number of integers k from 1 to n such that gcd(n,k) is: A026741 (odd), A062570 (power of 2), A063659 (squarefree), A078429 (cube), A116512 (power of a prime), A117494 (prime), A126246 (1 or 2), A206369 (square), A254926 (cubefree), A372671 (3-smooth), A384039 (powerful), A384040 (cubefull), A384041 (exponentially odd), this sequence (5-rough).

f[p_, e_] := If[p < 5, (p-1)*p^(e-1), p^e]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); prod(i = 1, #f~, if(f[i,1] < 5, (f[i,1]-1)*f[i,1]^(f[i,2]-1), f[i,1]^f[i,2]));}

Multiplicative with a(p^e) = (p-1)*p^(e-1) if p <= 3 and p^e if p >= 5.
a(n) >= A000010(n), with equality if and only if n is 3-smooth (A003586).
a(n) = A000010(A065331(n)) * A065330(n).
a(n) = 2 * n * phi(n)/phi(6*n) = n * A000010(n) / A372671(n).
Dirichlet g.f.: zeta(s-1) * (1-1/2^s) * (1-1/3^s).
Sum_{k=1..n} a(k) ~ n^2 / 3.

A384249 The number of integers k from 1 to n such that the greatest divisor of k that is an infinitary divisor of n is squarefree.

Original entry on oeis.org

1, 2, 3, 3, 5, 6, 7, 6, 8, 10, 11, 9, 13, 14, 15, 15, 17, 16, 19, 15, 21, 22, 23, 18, 24, 26, 24, 21, 29, 30, 31, 30, 33, 34, 35, 24, 37, 38, 39, 30, 41, 42, 43, 33, 40, 46, 47, 45, 48, 48, 51, 39, 53, 48, 55, 42, 57, 58, 59, 45, 61, 62, 56, 48, 65, 66, 67, 51

Offset: 1

Amiram Eldar, May 23 2025

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A005117, A065176, A077609.
Analogous sequences: A063659, A384048.
The number of integers k from 1 to n such that the greatest divisor of k that is an infinitary divisor of n is: A384247(1), this sequence (squarefree), A384250 (powerful), A384251 (odd), A384252 (power of 2).

f[p_, e_] := p^e*(1 - 1/p^(2^IntegerExponent[e - Mod[e, 2], 2])); f[p_, 1] := p; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

a(n) = {my(f = factor(n)); n * prod(i = 1, #f~, if(f[i,2] == 1, 1, 1 - 1/f[i,1]^(1 << valuation(f[i,2] - f[i,2]%2, 2))));}

Multiplicative with a(p) = p, and a(p^e) = p^e * (1 - 1/p^A065176(e)) for e >= 2.

Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} f(1/p) = 0.93444998595445071889..., and f(x) = 1 - (1-x^2) * Sum_{k>=2} x^(2^k)/(1-x^(2^k));

A063658 The number of integers m in [1..n] for which gcd(m,n) is divisible by a square greater than 1.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 3, 0, 0, 0, 4, 0, 2, 0, 5, 0, 0, 0, 6, 1, 0, 3, 7, 0, 0, 0, 8, 0, 0, 0, 12, 0, 0, 0, 10, 0, 0, 0, 11, 5, 0, 0, 12, 1, 2, 0, 13, 0, 6, 0, 14, 0, 0, 0, 15, 0, 0, 7, 16, 0, 0, 0, 17, 0, 0, 0, 24, 0, 0, 3, 19, 0, 0, 0, 20, 9, 0, 0, 21, 0, 0, 0, 22, 0, 10, 0, 23, 0, 0, 0, 24

Offset: 1

Floor van Lamoen, Jul 24 2001

nonn

Haviland (1944) proved that a(n) is the number of those arithmetic progressions among (m*n + s: m >= 0), s = 0, 1, ..., n-1, which contain a finite number of squarefree numbers. - Petros Hadjicostas, Jul 21 2019

			For n=12 we find gcd(4,12), gcd(8,12) and gcd(12,12) divisible by 4, so a(12) = 3.
From _Petros Hadjicostas_, Jul 21 2019: (Start)
We have a(2) = 0 because each of the two arithmetic progressions (2*m: m >= 0) and (2*m + 1: m >= 0) contains infinitely many squarefree numbers.
We have a(3) = 0 because each of the three arithmetic progressions (3*m: m >= 0), (3*m + 1: m >= 0), and (3*m + 2: m >= 0) contains infinitely many squarefree numbers.
We have  a(4) = 1 because, among the four arithmetic progressions (4*m: m >= 0), (4*m + 1: m >= 0), (4*m + 2: m >= 0), and (4*m + 3: m >= 0), only the first one contains a finite number of squarefree numbers (in this case, zero!).
We have a(8) = 2 because only the arithmetic progressions (8*m: m >= 0) and (8*m + 4: m >= 0) contain a finite number of squarefree numbers (in this case, zero!).
(End)

Harry J. Smith, Table of n, a(n) for n = 1..2000
E. K. Haviland, An analogue of Euler's phi-function, Duke Math. J. 11 (1944), 869-872.

a(n) = n - A063659(n).

f[list_, i_] := list[[i]]; nn = 100; a =Table[EulerPhi[n], {n, 1, nn}]; b =Table[If[Max[FactorInteger[n][[All, 2]]] > 1, 1, 0], {n,1,nn}]; Table[DirichletConvolve[f[a, n], f[b, n], n, m], {m, 1, nn}] (* Geoffrey Critzer, Mar 21 2015 *)
Table[Sum[EulerPhi[n/d]*(1-MoebiusMu[d]^2), {d, Divisors[n]}], {n, 1, 100}] (* Vaclav Kotesovec, Feb 01 2019 *)

{ for (n=1, 2000, a=0; for (m=2, n, if (!issquarefree(gcd(m, n)), a++)); write("b063658.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 27 2009

a(n) = sumdiv(n, d, eulerphi(n/d) * (1 - moebius(d)^2)); \\ Daniel Suteu, Jun 27 2018

Dirichlet g.f.: zeta(s - 1)/zeta(s)*(zeta(s) - zeta(s)/zeta(2*s)) = zeta(s-1)*(zeta(2s)-1)/zeta(2s). - Geoffrey Critzer, Mar 21 2015
a(n) = Sum_{d|n} phi(n/d) * (1 - mu(d)^2). - Daniel Suteu, Jun 27 2018
Sum_{k=1..n} a(k) ~ n^2 * (1 - 90/Pi^4) / 2. - Vaclav Kotesovec, Feb 01 2019

More terms from Larry Reeves (larryr(AT)acm.org), Vladeta Jovovic and Dean Hickerson, Jul 26 2001

Name edited by Petros Hadjicostas, Jul 21 2019

A078439 a(n) = Sum_{k=1..n} gcd(k,n)*mu(gcd(k,n))^2.

Original entry on oeis.org

1, 3, 5, 4, 9, 15, 13, 8, 12, 27, 21, 20, 25, 39, 45, 16, 33, 36, 37, 36, 65, 63, 45, 40, 40, 75, 36, 52, 57, 135, 61, 32, 105, 99, 117, 48, 73, 111, 125, 72, 81, 195, 85, 84, 108, 135, 93, 80, 84, 120, 165, 100, 105, 108, 189, 104, 185, 171, 117, 180, 121, 183, 156, 64

Offset: 1

Vladeta Jovovic, Dec 31 2002

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001620, A000010, A008683, A063659.

[&+[Gcd(k,n)*MoebiusMu(Gcd(n,k))^2:k  in [1..n]]:n in [1..70]]; // Marius A. Burtea, Sep 15 2019

Table[Sum[d*MoebiusMu[d]^2*EulerPhi[n/d], {d, Divisors[n]}], {n, 1, 100}] (* Vaclav Kotesovec, Feb 01 2019 *)
f[p_, e_] := If[e==1, 2*p-1, 2*(p-1)*p^(e-1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 30 2023 *)

vector(80, n, sumdiv(n, d, d*moebius(d)^2*eulerphi(n/d))) \\ Michel Marcus, Mar 20 2015

a(n) = Sum_{d|n} d*mu(d)^2*phi(n/d).
Multiplicative with a(p) = 2*p-1 and a(p^e) = 2*(p-1)*p^(e-1), e>1.
Dirichlet g.f.: zeta(s-1)^2 / (zeta(s) * zeta(2s-2)). - Álvar Ibeas, Mar 20 2015
Sum_{k=1..n} a(k) ~ 9 * n^2 * (2*log(n) + 4*gamma - 1 - 36*Zeta'(2)/Pi^2) / Pi^4, where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Feb 01 2019

A332685 a(n) = Sum_{k=1..n} mu(k/gcd(n, k)).

Original entry on oeis.org

1, 2, 1, 2, 0, 2, 0, 0, -1, 0, 0, 0, -1, -2, -2, -3, 0, -4, -1, -5, -4, -2, 0, -8, -3, -4, -4, -7, 0, -8, -2, -10, -5, -4, -4, -13, 0, -5, -4, -13, 1, -15, -1, -9, -10, -5, -1, -22, -4, -12, -5, -11, -1, -19, -6, -17, -6, -4, 1, -28, 0, -8, -12, -18, -6, -19, 0, -12, -5, -17

Offset: 1

Ilya Gutkovskiy, Feb 19 2020

sign

Inverse Moebius transform of A112399.

Ilya Gutkovskiy, Scatterplot of a(n) up to n=10000

Cf. A002321, A007431, A007947, A008683, A063659, A112399, A276833, A304575.

Table[Sum[MoebiusMu[k/GCD[n, k]], {k, 1, n}], {n, 1, 70}]

a(n) = sum(k=1, n, moebius(k/gcd(n, k))); \\ Michel Marcus, Feb 21 2020

a(n) = Sum_{k=1..n} mu(lcm(n, k)/n).

a(n) = Sum_{d|n} A112399(d).

A347230 Möbius transform of A344695, gcd(sigma(n), psi(n)).

Original entry on oeis.org

1, 2, 3, -2, 5, 6, 7, 2, -3, 10, 11, -6, 13, 14, 15, -2, 17, -6, 19, -10, 21, 22, 23, 6, -5, 26, 3, -14, 29, 30, 31, 2, 33, 34, 35, 6, 37, 38, 39, 10, 41, 42, 43, -22, -15, 46, 47, -6, -7, -10, 51, -26, 53, 6, 55, 14, 57, 58, 59, -30, 61, 62, -21, -2, 65, 66, 67, -34, 69, 70, 71, -6, 73, 74, -15, -38, 77, 78, 79

Offset: 1

Antti Karttunen, Aug 25 2021

sign

Not multiplicative because A344695 isn't either. For example, a(4) = -2, a(27) = 3, but a(108) = -2 != -6.
The absolute values are not equal to A007947. The first n where abs(a(n)) != A007947(n) is at n=108, with a(108) = -2, while A007947(108) = 6.
The first n such that a(n) does not divide n are: 196, 216, 392, 432, 441, 588, etc.
The zeros occur at n = 288, 576, 1440, 2016, 2880, 3168, 3744, 4032, etc.

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

Cf. A000203, A001615, A008683, A344695, A347228, A347231.

Cf. also A007947, A063659.

A001615(n) = if(1==n,n, my(f=factor(n)); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1))); \\ After code in A001615
A344695(n) = gcd(sigma(n), A001615(n));
A347230(n) = sumdiv(n,d,moebius(n/d)*A344695(d));

a(n) = Sum_{d|n} A008683(n/d) * A344695(d).

a(n) = A344695(n) - A347231(n).

A309287 Square array T(v, m), read by antidiagonals, for the Rogel-Klee arithmetic function: number of positive integers h in the set [m] for which gcd(h, m) is v-th-power-free, i.e., gcd(h, m) is not divisible by any v-th power of an integer > 1 (with v, m >= 1).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 3, 2, 1, 4, 3, 3, 2, 1, 2, 5, 4, 3, 2, 1, 6, 6, 5, 4, 3, 2, 1, 4, 7, 6, 5, 4, 3, 2, 1, 6, 6, 7, 6, 5, 4, 3, 2, 1, 4, 8, 7, 7, 6, 5, 4, 3, 2, 1, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 4, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 12, 9, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 6, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Petros Hadjicostas, Jul 21 2019

For fixed v >= 1, T(v, .) is a multiplicative arithmetic function with T(v, 1) = 1; T(v, p^e) = p^e, if e < v; and T(v, p^e) = p^e - p^(e-v) if e >= v (where p is a prime >= 2).
Here, T(v=1, m) = phi(m) is the number of arithmetic progressions (s*m + k: s >= 0), k = 1, ..., m, that contain infinitely many primes (by Dirichlet's theorem). For v >= 2, T(v, m) is the number of these arithmetic progressions that contain infinitely many v-th-power-free numbers.
In Section 6 of his paper, Cohen (1959) mentions that this function was introduced by Rogel (1900) in an article published in a Bohemian journal. Roger's (1900) paper is a continuation of Rogel (1897) and the two should be read together.
McCarthy (1958) uses the asymptotic result given in the FORMULA section below to prove that the probability that the GCD of two positive integers is v-th-power-free is 1/zeta(2*v).

			Table for T(v, m) (with rows v >= 1 and columns m >= 1) begins as follows:
  v=1: 1, 1, 2, 2, 4, 2, 6, 4, 6,  4, 10,  4, 12,  6,  8,  8, ...
  v=2: 1, 2, 3, 3, 5, 6, 7, 6, 8, 10, 11,  9, 13, 14, 15, 12, ...
  v=3: 1, 2, 3, 4, 5, 6, 7, 7, 9, 10, 11, 12, 13, 14, 15, 14, ...
  v=4: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, ...
  v=5: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
  v=6: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
  v=7: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
  ...
Clearly, lim_{v -> infinity} T(v, m) = m.

Paul J. McCarthy, Introduction to Arithmetical Functions, Springer-Verlag, 1986; see pp. 38-40 and 69.

Eckford Cohen, A class of residue systems (mod r) and related arithmetical functions. I. A generalization of the Moebius function, Pacific J. Math. 9(1) (1959), 13-24; see Section 6 where T(v, m) = Phi_v(m).
Eckford Cohen, A generalized Euler phi-function, Math. Mag. 41 (1968), 276-279; here T(v, m) = phi_v(m).
E. K. Haviland, An analogue of Euler's phi-function, Duke Math. J. 11 (1944), 869-872; here T(v=2, m) = rho(m).
V. L. Klee, Jr., A generalization of Euler's phi function, Amer. Math. Monthly, 55(6) (1948), 358-359; here T(v, m) = Phi_v(m).
Paul J. McCarthy, On a certain family of arithmetic functions, Amer. Math. Monthly 65 (1958), 586-590; here, T(v, m) = T_v(m).
Franz Rogel, Entwicklung einiger zahlentheoreticher Funktionen in unendliche Reihen, S.-B. Kgl. Bohmischen Ges. Wiss. Article XLVI/XLIV (1897), Prague (26 pages). [This paper deals with arithmetic functions, especially the Euler phi function. It was continued three years later with the next paper, which contains his function phi_k(n). As stated at the end of the volume, in the table of contents, there is a mistake in numbering the article, so two Roman numerals appear in the literature for labeling this article!]
Franz Rogel, Entwicklung einiger zahlentheoreticher Funktionen in unendliche Reihen, S.-B. Kgl. Bohmischen Ges. Wiss. Article XXX (1900), Prague (9 pages). [This is a continuation of the previous article, which was written three years earlier and has the same title. The numbering of the equations continues from the previous paper, but this paper is the one that introduces the function phi_k(n). In our notation, T(v, m) = phi_v(m). Cohen (1959) refers to this paper and correctly attributes this function to F. Rogel.]

A000010 (row v = 1 is Euler's phi function), A063659 (row v = 2 is Haviland's function), A254926 (row v = 3).

/* Modification of Michel Marcus's program from sequence A254926: */
T(v, m) = {f = factor(m); for (i=1, #f~, if ((e=f[i, 2])>=v, f[i, 1] = f[i, 1]^e - f[i, 1]^(e-v); f[i, 2]=1); ); factorback(f); }
/* Print the first 40 terms of each of the first 10 rows: */
{ for (v=1, 10, for (m=1, 40, print1(T(v, m), ", "); ); print(); ); }

T(v, m) = m * Product_{p prime and p^v|m} (1 - p^(-v)) for v, m >= 1.
T(v, m) = Sum_{n >= 1} mu(n) * [m, n^v] * (m/n^v), where [m, n^v] = 1 when m is a multiple of n^v, and = 0 otherwise. [This is Eq. (53) in Rogel (1900) and Eq. (6.1) in Cohen (1959).]
Dirichlet g.f. for row v: Sum_{m >= 1} T(v, m)/m^s = zeta(s-1)/zeta(v*s) for Re(s) > 1.
Asymptotics: Sum_{m = 1..n} T(v, m) = n^2/(2*zeta(2*v)) + O(n) for v >= 2 and = n^2/(2*zeta(2)) + O(n*log(n)) for v = 1 (for Euler's phi-function).
Analog of Fermat's theorem: if gcd(a, m) = 1 with a >= 1, then m/gcd(a^T(v, m) - 1, m) is v-th-power-free. (For v = 1, this means m/gcd(a^T(v=1, m) - 1, m) = 1.)
T(v, m^v)/m^v = Sum_{d|m} mu(d)/d^v for m, v >= 1. (It generalizes the formula phi(m)/m = Sum_{d|m} mu(d)/d since phi(m) = T(v=1, m).)

cp's OEIS Frontend

A384039 The number of integers k from 1 to n such that gcd(n,k) is a powerful number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384040 The number of integers k from 1 to n such that gcd(n,k) is a cubefull number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384041 The number of integers k from 1 to n such that gcd(n,k) is an exponentially odd number.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384042 The number of integers k from 1 to n such that gcd(n,k) is a 5-rough number (A007310).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A384249 The number of integers k from 1 to n such that the greatest divisor of k that is an infinitary divisor of n is squarefree.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A063658 The number of integers m in [1..n] for which gcd(m,n) is divisible by a square greater than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A078439 a(n) = Sum_{k=1..n} gcd(k,n)*mu(gcd(k,n))^2.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A332685 a(n) = Sum_{k=1..n} mu(k/gcd(n, k)).

Views