A055653 -id:A055653 - cp's OEIS frontend

A332713 a(n) = Sum_{d|n} phi(d/gcd(d, n/d)).

1, 2, 3, 4, 5, 6, 7, 7, 8, 10, 11, 12, 13, 14, 15, 13, 17, 16, 19, 20, 21, 22, 23, 21, 22, 26, 22, 28, 29, 30, 31, 24, 33, 34, 35, 32, 37, 38, 39, 35, 41, 42, 43, 44, 40, 46, 47, 39, 44, 44, 51, 52, 53, 44, 55, 49, 57, 58, 59, 60, 61, 62, 56, 46, 65, 66, 67, 68, 69, 70

Offset: 1

Ilya Gutkovskiy, Feb 20 2020

Vaclav Kotesovec, Graph - the asymptotic ratio (1000000 terms)

Cf. A000010, A001616, A010052, A046790 (numbers n such that a(n) < n), A055653, A061884, A078779 (fixed points), A332619, A332686, A332712.

Table[Sum[EulerPhi[d/GCD[d, n/d]], {d, Divisors[n]}], {n, 1, 70}]
A055653[n_] := Sum[Boole[GCD[d, n/d] == 1] EulerPhi[d], {d, Divisors[n]}]; a[n_] := Sum[Boole[IntegerQ[(n/d)^(1/2)]] A055653[d], {d, Divisors[n]}]; Table[a[n], {n, 1, 70}]

a(n) = sumdiv(n, d, eulerphi(d/gcd(d, n/d))); \\ Michel Marcus, Feb 20 2020

Dirichlet g.f.: zeta(s) * zeta(2*s) * zeta(s - 1) * Product_{p prime} (1 - p^(-s) + p^(-2*s) - p^(1 - 2*s)).
a(n) = Sum_{d|n} phi(lcm(d, n/d)/d).
a(n) = Sum_{d|n} A010052(n/d) * A055653(d).
Sum_{k=1..n} a(k) ~ c * Pi^6 * n^2 / 1080, where c = A330523 = Product_{primes p} (1 - 1/p^2 - 1/p^3 + 1/p^4) = 0.5358961538283379998085... - Vaclav Kotesovec, Feb 22 2020
From Richard L. Ollerton, May 10 2021: (Start)
a(n) = Sum_{k=1..n} phi(gcd(n,k)/gcd(gcd(n,k),n/gcd(n,k)))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} phi(n/gcd(n,k)/gcd(gcd(n,k),n/gcd(n,k)))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} phi(lcm(gcd(n,k),n/gcd(n,k))/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} phi(lcm(gcd(n,k),n/gcd(n,k))*gcd(n,k)/n)/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} A010052(gcd(n,k))*A055653(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} A010052(n/gcd(n,k))*A055653(gcd(n,k))/phi(n/gcd(n,k)). (End)

A055654 Difference between n and the result of "Phi-summation" over unitary divisors of n.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 3, 2, 0, 0, 3, 0, 0, 0, 7, 0, 4, 0, 5, 0, 0, 0, 9, 4, 0, 8, 7, 0, 0, 0, 15, 0, 0, 0, 15, 0, 0, 0, 15, 0, 0, 0, 11, 10, 0, 0, 21, 6, 8, 0, 13, 0, 16, 0, 21, 0, 0, 0, 15, 0, 0, 14, 31, 0, 0, 0, 17, 0, 0, 0, 37, 0, 0, 12, 19, 0, 0, 0, 35, 26, 0, 0, 21, 0, 0, 0, 33, 0, 20, 0, 23

Offset: 1

Labos Elemer, Jun 07 2000

Squarefree numbers are roots of a(n)=0 equation, while Min n for which a(n)=k is k^2. See also A000188, A008833.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000188, A008833, A055653, A053570, A053571, A055631, A055632, A055653, A065465.

a055654 n = a055654_list !! (n-1)
a055654_list = zipWith (-) [1..] a055653_list
-- Reinhard Zumkeller, Mar 11 2012

Table[n - DivisorSum[n, EulerPhi[#] &, CoprimeQ[#, n/#] &], {n, 92}] (* Michael De Vlieger, Oct 26 2017 *)
f[p_, e_] := p^e - p^(e-1) + 1; a[1] = 0; a[n_] := n - Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 04 2024 *)

a(n) = n - sumdiv(n, d, if (gcd(d, n/d)==1, eulerphi(d))); \\ Michel Marcus, Oct 27 2017

a(n) = {my(f = factor(n)); n - prod(k = 1, #f~, f[k,1]^f[k,2] - f[k,1]^(f[k,2] - 1) + 1);} \\ Amiram Eldar, Oct 04 2024

a(n) = n - Sum_{u|n, gcd(u,n/u) = 1} phi(u), i.e. when u is a unitary divisor of n.
a(n) = n - A055653(n). - Sean A. Irvine, Mar 30 2022
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = 1 - A065465 = 0.11848616... . - Amiram Eldar, Oct 04 2024

A114810 Number of complex, weakly primitive Dirichlet characters modulo n.

Original entry on oeis.org

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

Offset: 1

Steven Finch, Feb 19 2006

Any primitive Dirichlet character is weakly primitive (not conversely). Jager uses the phrase "proper character", but this conflicts with other authors (e.g., W. Ellison and F. Ellison, Prime Numbers, Wiley, 1985, p. 224) who use the word "proper" to mean the same as "primitive".

Equals Mobius transform of A055653. - Gary W. Adamson, Feb 28 2009

			The function chi defined on the integers by chi(1)=1, chi(5)=-1 and chi(2)=chi(3)=chi(4)=chi(6)=0 [and extended periodically] is a weakly primitive character mod 6, but not mod 12 or mod 18. In this sense, we eliminate the "overcounting" of complex Dirichlet characters in A000010.

Amiram Eldar, Table of n, a(n) for n = 1..10000
H. Jager, On the number of Dirichlet characters with modulus not exceeding x, Nederl. Akad. Wetensch. Proc. Ser. A 76=Indag. Math. 35 (1973) 452-455.

Cf. A000010, A007431, A055231, A330523.

Cf. A055653. [Gary W. Adamson, Feb 28 2009]

b[n_] := Sum[EulerPhi[d]*MoebiusMu[n/d], {d, Divisors[n]}]; squareFreeKernel[n_] := Times @@ First /@ FactorInteger[n]; a[n_] := Sum[b[n/d], {d, Divisors[Denominator[n/squareFreeKernel[n]^2]]}]; Table[a[n], {n, 1, 80}] (* Jean-François Alcover, Sep 07 2015 *)
f[p_, e_] := If[e == 1, p - 1, (p - 1)^2*p^(e - 2)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 04 2022 *)

a(n) is multiplicative with a(p) = phi(p), a(p^k) = phi(p^k)-phi(p^(k-1)) and phi(n) = A000010(n).
a(n) = Sum_{d} A007431(n/d), where the sum is over all divisors 1<=d<=n of A055231(n).
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} (1 - 1/p^2 - 1/p^3 + 1/p^4) = A330523 / 2 = 0.2679480769... . - Amiram Eldar, Nov 04 2022

A143869 An integer k is called regular (mod n) if there is an integer x such that k^2 x == k (mod n). Then these numbers are the sum of regular integers k (mod n) such that 1 <= k <= n for n=1,2,... .

Original entry on oeis.org

1, 3, 6, 8, 15, 21, 28, 24, 36, 55, 66, 60, 91, 105, 120, 80, 153, 135, 190, 160, 231, 253, 276, 192, 275, 351, 270, 308, 435, 465, 496, 288, 561, 595, 630, 396, 703, 741, 780, 520, 861, 903, 946, 748, 810, 1081, 1128, 672, 1078, 1075, 1326, 1040, 1431, 1053

Offset: 1

Laszlo Toth, Sep 04 2008

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Osama Alkam and Emad Abu Osba, On the regular elements in Zn, Turk J Math, 32 (2008), 31-39.
B. Apostol and L. Petrescu, Extremal Orders of Certain Functions Associated with Regular Integers (mod n), Journal of Integer Sequences, 2013, # 13.7.5.
L. Tóth, Regular integers modulo n, Annales Univ. Sci. Budapest., Sect. Comp., 29 (2008), 263-275.

Cf. A055653, A176345.

isregu(k, n) = {g = gcd(k, n); if ((n % g == 0) && (gcd(g, n/g) == 1), return(k), return(0));}
a(n) = sum(k=1, n, isregu(k, n)) \\ Michel Marcus, May 25 2013

a(n) = n*(A055653(n)+1)/2.

Extended by R. J. Mathar, Sep 05 2008

A333557 a(n) = Sum_{d|n, gcd(d, n/d) = 1} uphi(d) * uphi(n/d), where uphi = unitary totient function (A047994).

Original entry on oeis.org

1, 2, 4, 6, 8, 8, 12, 14, 16, 16, 20, 24, 24, 24, 32, 30, 32, 32, 36, 48, 48, 40, 44, 56, 48, 48, 52, 72, 56, 64, 60, 62, 80, 64, 96, 96, 72, 72, 96, 112, 80, 96, 84, 120, 128, 88, 92, 120, 96, 96, 128, 144, 104, 104, 160, 168, 144, 112, 116, 192, 120, 120, 192, 126, 192, 160, 132, 192, 176, 192

Offset: 1

Ilya Gutkovskiy, Mar 26 2020

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

Cf. A001221, A029935, A034444, A047994, A055653, A062355, A145388.

uphi[1] = 1; uphi[n_] := Times @@ (#[[1]]^#[[2]] - 1 & /@ FactorInteger[n]); a[n_] := Sum[If[GCD[d, n/d] == 1, uphi[d] uphi[n/d], 0], {d, Divisors[n]}]; Table[a[n], {n, 1, 70}]
Table[Sum[If[GCD[d, n/d] == 1, (-2)^PrimeNu[n/d] 2^PrimeNu[d] d, 0], {d, Divisors[n]}], {n, 1, 70}]
f[p_, e_] := 2*(p^e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Apr 30 2023 *)

a(n) = sumdiv(n, d, if (gcd(d, n/d) == 1, (-2)^omega(n/d)*2^omega(d)*d)); \\ Michel Marcus, Mar 27 2020

If n = Product (p_j^k_j) then a(n) = Product (2 * (p_j^k_j - 1)).
a(n) = 2^omega(n) * uphi(n).
a(n) = Sum_{d|n, gcd(d, n/d) = 1} (-2)^omega(n/d) * 2^omega(d) * d.
a(n) = Sum_{d|n, gcd(d, n/d) = 1} (-1)^omega(n/d) * A145388(d).

A157361 Triangle read by rows, A051731 * (A114810 * 0^(n-k)).

Original entry on oeis.org

1, 1, 1, 1, 0, 2, 1, 1, 0, 1, 1, 0, 0, 0, 4, 1, 1, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 6, 1, 1, 0, 1, 0, 0, 0, 2, 1, 0, 2, 0, 0, 0, 0, 0, 4, 1, 1, 0, 0, 4, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 1, 1, 2, 1, 0, 2, 0, 0, 0, 0, 0, 2

Offset: 1

Gary W. Adamson, Feb 28 2009

Row sums = A055653: (1, 2, 3, 3, 5, 6, 7, 5,...)

			First few rows of the triangle =
1;
1, 1;
1, 0, 2;
1, 1, 0, 1;
1, 0, 0, 0, 4;
1, 1, 2, 0, 0, 2;
1, 0, 0, 0, 0, 0, 6;
1, 1, 0, 1, 0, 0, 0, 2;
1, 0, 2, 0, 0, 0, 0, 0, 4;
1, 1, 0, 0, 4, 0, 0, 0, 0, 4;
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10;
1, 1, 2, 1, 0, 2, 0, 0, 0, 0, 0, 2;
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12;
1, 1, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 6;
...

Cf. A114810, A055653

Triangle read by rows, A051731 * (A114810 * 0^(n-k)); where A051731 = the inverse Mobius transform and (A114810 * 0^(n-k)) = an infinite lower triangular matrix with A114810 as the main diagonal: (1, 1, 2, 1, 4, 2, 6,...) and the rest zeros.

A263320 Number of regular elements in Z_n[i].

Original entry on oeis.org

1, 3, 9, 9, 25, 27, 49, 33, 73, 75, 121, 81, 169, 147, 225, 129, 289, 219, 361, 225, 441, 363, 529, 297, 441, 507, 649, 441, 841, 675, 961, 513, 1089, 867, 1225, 657, 1369, 1083, 1521, 825, 1681, 1323, 1849, 1089, 1825, 1587, 2209, 1161, 2353, 1323, 2601, 1521

Offset: 1

José María Grau Ribas, Oct 14 2015

A Gaussian integer z is called regular (mod n) if there is a Gaussian integer x such that z^2 * x == z (mod n).
From Robert Israel, Nov 30 2015: (Start)
a(2^k) = 1 + 2^(2k-1) for k >= 1.
a(p) = p^2 if p is an odd prime.
a(p^k) = 1 - p^(2k-2) + p^(2k) if p is a prime == 3 mod 4.
a(p^k) = 1 - 2 p^(k-1) + 2 p^k + p^(2k-2) - 2 p^(2k-1) + p^(2k) if p is a prime == 1 mod 4.(End)

			a(2) = 3 because the regular elements in Z_2[i] are {0, 1, i}.

Robert Israel, Table of n, a(n) for n = 1..10000
Wikipedia, Gaussian Integer.

Cf. A055653.

regularQ[a_, b_, n_] := ! {0} == Union@Flatten@Table[If[Mod[(a + b I) - (a +  b I)^2 (x + y I),  n] == 0, x + I y, 0], {x, 0, n - 1}, {y, 0, n -1}]; Ho[1]=1; Ho[n_] := Ho[n] = Sum[If[regularQ[a, b, n], 1, 0], {a, 1, n}, {b, 1, n}]; Table[Ho[n], {n, 1, 33}]
f[p_, e_] := If[Mod[p, 4] == 1, 1 - 2*p^(e-1) + 2*p^e + p^(2*e-2) - 2*p^(2*e-1) + p^(2*e), 1 - p^(2*e-2) + p^(2*e)]; f[2, e_] := 1 + 2^(2*e-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 31 2023 *)

A333645 a(n) = Sum_{d|n} uphi(d).

Original entry on oeis.org

1, 2, 3, 5, 5, 6, 7, 12, 11, 10, 11, 15, 13, 14, 15, 27, 17, 22, 19, 25, 21, 22, 23, 36, 29, 26, 37, 35, 29, 30, 31, 58, 33, 34, 35, 55, 37, 38, 39, 60, 41, 42, 43, 55, 55, 46, 47, 81, 55, 58, 51, 65, 53, 74, 55, 84, 57, 58, 59, 75, 61, 62, 77, 121, 65, 66, 67, 85, 69, 70

Offset: 1

Ilya Gutkovskiy, Mar 31 2020

Inverse Moebius transform of A047994.

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

Cf. A005117 (fixed points), A023900, A047994, A055653, A062949, A065464, A152649.

uphi[1] = 1; uphi[n_] := Times @@ (#[[1]]^#[[2]] - 1 & /@ FactorInteger[n]); a[n_] := Sum[uphi[d], {d, Divisors[n]}]; Table[a[n], {n, 70}]
A023900[n_] := Sum[MoebiusMu[d] d, {d, Divisors[n]}]; A062949[n_] := Sum[EulerPhi[d] DivisorSigma[0, d], {d, Divisors[n]}]; a[n_] := Sum[A023900[d] A062949[n/d], {d, Divisors[n]}]; Table[a[n], {n, 70}]
f[p_,e_] := (p^(e+1) - e*p + e - 1)/(p-1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a,100] (* Amiram Eldar, Nov 12 2022 *)

uphi(n)=my(f=factor(n)~); prod(i=1, #f, f[1, i]^f[2, i]-1); \\ A047994
a(n) = sumdiv(n, d, uphi(d)); \\ Michel Marcus, Mar 31 2020

G.f.: Sum_{k>=1} uphi(k) * x^k / (1 - x^k).
a(n) = Sum_{d|n} A023900(d) * A062949(n/d).
From Amiram Eldar, Nov 12 2022: (Start)
Multiplicative with a(p^e) = (p^(e+1) - e*p + e - 1)/(p-1).
Sum_{k=1..n} a(k) ~ c * n^2, where c = (Pi^4/72) * Product_{p prime} (1 - (2*p-1)/p^3) = A152649 * A065464 = 0.5793804872... . (End)

A383954 a(n) = Product_{i} (phi(p_i^e_i)-1) where n = Product_{i} p_i^e_i and phi is the Euler phi function.

Original entry on oeis.org

1, 0, 1, 1, 3, 0, 5, 3, 5, 0, 9, 1, 11, 0, 3, 7, 15, 0, 17, 3, 5, 0, 21, 3, 19, 0, 17, 5, 27, 0, 29, 15, 9, 0, 15, 5, 35, 0, 11, 9, 39, 0, 41, 9, 15, 0, 45, 7, 41, 0, 15, 11, 51, 0, 27, 15, 17, 0, 57, 3, 59, 0, 25, 31, 33, 0, 65, 15, 21, 0, 69, 15, 71, 0, 19, 17, 45, 0, 77, 21

Offset: 1

Michel Marcus, Aug 19 2025

This is the phi- function in Sandor and Atanassof.

Paolo Xausa, Table of n, a(n) for n = 1..10000
József Sándor and Krassimir Atanassov, Some new arithmetic functions, Notes on Number Theory and Discrete Mathematics, Volume 30, 2024, Number 4, Pages 851-856.

Cf. A000010 (phi), A107758 (sigma+), A057723 (sigma-), A055653 (phi+).

A383954[n_] := If[n == 1, 1, Times @@ (EulerPhi[Power @@@ FactorInteger[n]] - 1)];
Array[A383954, 100] (* Paolo Xausa, Aug 19 2025 *)

a(n) = my(f=factor(n)); prod(k=1, #f~, p=f[k,1]; eulerphi(f[k,1]^f[k,2])-1);

From Amiram Eldar, Aug 19 2025: (Start)
Multiplicative with a(p^e) = (p-1)*p^(e-1) - 1.
Dirichlet g.f.: zeta(s-1) * zeta(s) * Product_{p prime} (1 - 3/p^s + 1/p^(2*s-1) + 1/p^(2*s)).
Sum_{k=1..n} a(k) ~ c * n^2 / 2, where c = Product_{p prime} (1 + 1/(p+1) - (p+1)/p^2) = 0.39439177573628632634... . (End)

A384763 Product of the Euler totients of the unitary divisors of n.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 4, 6, 16, 10, 16, 12, 36, 64, 8, 16, 36, 18, 64, 144, 100, 22, 64, 20, 144, 18, 144, 28, 4096, 30, 16, 400, 256, 576, 144, 36, 324, 576, 256, 40, 20736, 42, 400, 576, 484, 46, 256, 42, 400, 1024, 576, 52, 324, 1600, 576, 1296, 784, 58, 65536

Offset: 1

Darío Clavijo, Jun 09 2025

nonn

a(n) is the product of phi(d) over all unitary divisors d of n; i.e., those divisors satisfying gcd(d, n/d) = 1.
a(n) is upper bounded by A061537(n) (product of phi(d) over all divisors d of n).
The function is not multiplicative.
The sum of the totients over all unitary divisors d of n is A055653(n).

			For n = 6, a(6) = phi(1) * phi(2) * phi(3) * phi(6) = 1*1*2*2 = 4.

Cf. A000010, A034444, A055653, A061537, A077610.

a[n_] := EulerPhi[n]^(2^(PrimeNu[n] - 1)); Array[a, 100] (* Amiram Eldar, Jun 09 2025 *)

a(n) = my(p=1); fordiv(n, d, if (gcd(d,n/d) == 1, p*=eulerphi(d))); p; \\ Michel Marcus, Jun 09 2025

from sympy import totient, divisors, gcd
def a(n):
   prod = 1
   for d in divisors(n):
      if gcd(d, n//d) == 1:
          prod *= totient(d)
   return prod
print([a(n) for n in range(1, 61)])

a(n) = Product_{d|n} phi(d) if gcd(n,floor(n/d)) = 1.
a(p) = p-1 for p prime.
a(p^k) = p^k-p^(k-1).
a(n) = phi(n)^(2^(omega(n)-1)) = A000010(n)^(A034444(n)/2). - Amiram Eldar, Jun 09 2025

cp's OEIS Frontend

A332713 a(n) = Sum_{d|n} phi(d/gcd(d, n/d)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055654 Difference between n and the result of "Phi-summation" over unitary divisors of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Formula

A114810 Number of complex, weakly primitive Dirichlet characters modulo n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A143869 An integer k is called regular (mod n) if there is an integer x such that k^2 x == k (mod n). Then these numbers are the sum of regular integers k (mod n) such that 1 <= k <= n for n=1,2,... .

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A333557 a(n) = Sum_{d|n, gcd(d, n/d) = 1} uphi(d) * uphi(n/d), where uphi = unitary totient function (A047994).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A157361 Triangle read by rows, A051731 * (A114810 * 0^(n-k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A263320 Number of regular elements in Z_n[i].

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A333645 a(n) = Sum_{d|n} uphi(d).

Views

Author

Keywords

Comments

Links

Crossrefs