A053570 -id:A053570 - cp's OEIS frontend

A055653 Sum of phi(d) [A000010] over all unitary divisors d of n (that is, gcd(d,n/d) = 1).

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

Offset: 1

Labos Elemer, Jun 07 2000

Phi-summation over d-s if runs over all divisors is n, so these values do not exceed n. Compare also other "Phi-summations" like A053570, A053571, or distinct primes dividing n, etc.
a(n) is also the number of solutions of x^(k+1)=x mod n for some k>=1. - Steven Finch, Apr 11 2006
An integer a is called regular (mod n) if there is an integer x such that a^2 x == a (mod n). Then a(n) is also the number of regular integers a (mod n) such that 1 <= a <= n. - Laszlo Toth, Sep 04 2008
Equals row sums of triangle A157361 and inverse Mobius transform of A114810. - Gary W. Adamson, Feb 28 2009
a(m) = m iff m is squarefree, a(A005117(n)) = A005117(n). - Reinhard Zumkeller, Mar 11 2012
Apostol & Tóth call this ϱ(n), i.e., varrho(n). - Charles R Greathouse IV, Apr 23 2013

			n=1260 has 36 divisors of which 16 are unitary ones: {1,4,5,7,9,20,28,35,36,45,63,140,180,252,315,1260}.
EulerPhi values of these divisors are: {1,2,4,6,6,8,12,24,12,24,36,48,48,72,144,288}.
The sum is 735, thus a(1260)=735.
Or, 1260=2^2*3^2*5*7, thus a(1260) = (1 + 2^2 - 2)*(1 + 3^2 - 3)*(1 + 5 - 5^0)*(1 + 7 - 7^0) = 735.

J. Morgado, Inteiros regulares módulo n, Gazeta de Matematica (Lisboa), 33 (1972), no. 125-128, 1-5. [From Laszlo Toth, Sep 04 2008]
J. Morgado, A property of the Euler phi-function concerning the integers which are regular modulo n, Portugal. Math., 33 (1974), 185-191.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from T. D. Noe)
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.
Brăduţ Apostol and László Tóth, Some remarks on regular integers modulo n, arXiv:1304.2699 [math.NT], 2013.
Klaus Dohmen, On the Number of Regular Elements in Zn, arXiv:2304.02471 [math.CO], 2023.
S. R. Finch, Idempotents and nilpotents modulo n, arXiv:1304.2699 [math.NT], 2013.
V. S. Joshi, Order-free integers (mod m), Number Theory (Mysore, 1981), Lect. Notes in Math. 938, Springer-Verlag, 1982, pp. 93-100.
Vaclav Kotesovec, Plot of Sum_{k=1..n} a(k) / (Pi^2 * n^2 / 12) for n = 1..100000
Sagar Mandal, Divisibility and Sequence Properties of sigma+ and phi+, arXiv:2508.11660 [math.GM], 2025.
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. See phi+ function.
L. Tóth, Regular integers modulo n, arXiv:0710.1936 [math.NT], 2007-2008; Annales Univ. Sci. Budapest., Sect. Comp., 29 (2008), 263-275.
L. Tóth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5.

Cf. A000010, A053570, A053571, A000188, A008833, A055654, A157361, A114810, A000010, A077610, A318661, A318662.

a055653 = sum . map a000010 . a077610_row
-- Reinhard Zumkeller, Mar 11 2012

A055653 := proc(n) local ans, i:ans := 1: for i from 1 to nops(ifactors(n)[ 2 ]) do ans := ans*(1+ifactors(n)[ 2 ][ i ] [ 1 ]^ifactors(n)[ 2 ] [ i ] [ 2 ]-ifactors(n)[ 2 ][ i ] [ 1 ]^(ifactors(n)[ 2 ] [ i ] [ 2 ]-1)): od: RETURN(ans) end:

a[n_] := Total[EulerPhi[Select[Divisors[n], GCD[#, n/#] == 1 &]]]; Array[a, 73] (* Jean-François Alcover, May 03 2011 *)
f[p_, e_] := p^e - p^(e-1) + 1; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 10 2020 *)

a(n) = sumdiv(n, d, if(gcd(n/d, d)==1, eulerphi(d))); \\ Charles R Greathouse IV, Feb 19 2013, corrected by Antti Karttunen, Sep 03 2018

a(n)=my(f=factor(n));prod(i=1,#f[,1],f[i,1]^f[i,2]-f[i,1]^(f[i,2]-1)+1) \\ Charles R Greathouse IV, Feb 19 2013

If n = product p_i^e_i, a(n) = product (1+p_i^e_i-p_i^(e_i-1)). - Vladeta Jovovic, Apr 19 2001
Dirichlet g.f.: zeta(s)*zeta(s-1)*product_{primes p} (1+p^(-2s)-p^(1-2s)-p^(-s)). - R. J. Mathar, Oct 24 2011
Dirichlet convolution square of A318661(n)/A318662(n). - Antti Karttunen, Sep 03 2018
Sum_{k=1..n} a(k) ~ c * Pi^2 * n^2 / 12, where c = Product_{primes p} (1 - 1/p^2 - 1/p^3 + 1/p^4) = A330523 = 0.535896... - Vaclav Kotesovec, Dec 17 2019

A055631 Sum of Euler's totient function phi of distinct primes dividing n.

Original entry on oeis.org

0, 1, 2, 1, 4, 3, 6, 1, 2, 5, 10, 3, 12, 7, 6, 1, 16, 3, 18, 5, 8, 11, 22, 3, 4, 13, 2, 7, 28, 7, 30, 1, 12, 17, 10, 3, 36, 19, 14, 5, 40, 9, 42, 11, 6, 23, 46, 3, 6, 5, 18, 13, 52, 3, 14, 7, 20, 29, 58, 7, 60, 31, 8, 1, 16, 13, 66, 17, 24, 11, 70, 3, 72, 37, 6, 19, 16, 15, 78, 5, 2

Offset: 1

Labos Elemer, Jun 06 2000

nonn

G. C. Greubel, Table of n, a(n) for n = 1..5000

Cf. A000010, A001221, A006093, A008472, A053570, A053571, A055632.

with(numtheory); a := n -> add(f, f = map(phi, factorset(n)));
seq(a(n), n = 1..81);  # Peter Luschny, Mar 30 2014

Join[{0},Table[Total[EulerPhi[Transpose[FactorInteger[n]][[1]]]],{n,2,90}]] (* Harvey P. Dale, Oct 29 2012 *)

A055631(n)=sum(i=1,#n=factor(n)~,n[1,i]-1) \\ M. F. Hasler, Nov 10 2016

a(n) = Sum_{p divides n} p-1 = A008472(n) - A001221(n).
If n = p^w, a power of prime, then a(n) = p-1; if n = 2p, then a(n) = p = n/2.
Additive with a(p^e) = p-1: a(10) = a(2*5) = a(2)+a(5) = (2-1)+(5-1) = 5; a(28) = a(2^2*7) = a(2^2)+a(7) = 1+6 = 7. - Vladeta Jovovic, Oct 23 2001
G.f.: Sum_{k>=1} (prime(k) - 1) * x^prime(k) / (1 - x^prime(k)). - Ilya Gutkovskiy, Aug 18 2021

Edited by M. F. Hasler, Nov 10 2016

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

A249396 Composite numbers whose Euler totient divides the sum of the Euler totients of the numbers less than n that are relatively prime to n.

Original entry on oeis.org

9, 75, 135, 265, 1383, 6585, 17251, 165615, 503111, 856195

Offset: 1

Paolo P. Lava, Oct 27 2014

No more terms < 10^6.

			Numbers coprime to 9 are 1, 2, 4, 5, 7, 8 and phi(9) = 6. Then, phi(1) + phi(2) + phi(4) + phi(5) + phi(7) + phi(8) = 1 + 1 + 2 + 4 + 6 + 4 = 18 and 18/6 = 3.

Cf. A000010, A053570, A249397.

with(numtheory): P:=proc(q) local a,k,n; for n from 2 to q do
if not isprime(n) then a:=0;
for k from 1 to n do if gcd(k,n)=1 then a:=a+phi(k); fi; od;
if type(a/phi(n),integer) then print(n); fi; fi; od; end: P(10^9);

isok(n) = (n!=1) && !isprime(n) && (sum(k=1, n-1, if (gcd(k, n) == 1, eulerphi(k), 0)) % eulerphi(n) == 0); \\ Michel Marcus, Oct 29 2014

a(8) from Ray Chandler, Nov 07 2014

a(9)-a(10) from Ray Chandler, Nov 11 2014

A143620 Triangle read by rows, square of A054521, 1<=k<=n.

Original entry on oeis.org

1, 1, 0, 2, 0, 0, 2, 1, 0, 0, 4, 1, 1, 0, 0, 2, 1, 1, 1, 0, 0, 6, 2, 2, 1, 1, 0, 0, 4, 3, 2, 2, 1, 1, 0, 0, 6, 2, 4, 2, 2, 1, 1, 0, 0, 4, 3, 1, 2, 2, 1, 1, 1, 0, 0, 10, 4, 5, 3, 4, 1, 3, 1, 1, 0, 0, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 0, 0

Offset: 1

Gary W. Adamson, Aug 27 2008

Left border = phi(n), A000010.

Row sums = A053570: (1, 1, 2, 3, 6, 5, 12, 13,...).

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

Cf. A054521, A000010, A053570.

Triangle read by rows, square of A054521, 1<=k<=n

A332686 a(n) = Sum_{k=1..n} phi(k/gcd(n, k)).

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 13, 18, 21, 23, 33, 33, 47, 49, 51, 67, 81, 76, 103, 97, 103, 119, 151, 135, 163, 173, 185, 189, 243, 185, 279, 280, 265, 299, 291, 291, 397, 379, 369, 371, 491, 381, 543, 491, 455, 553, 651, 539, 653, 610, 643, 683, 831, 689, 743, 753, 801, 887, 1029

Offset: 1

Ilya Gutkovskiy, Feb 19 2020

nonn

Inverse Moebius transform of A053570.

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

Cf. A000010, A002088, A029935, A029939, A053570, A332685.

Table[Sum[EulerPhi[k/GCD[n, k]], {k, 1, n}], {n, 1, 59}]

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

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

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

cp's OEIS Frontend

A127373 Triangle, row sums = A023896, left column = A053570.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A055653 Sum of phi(d) [A000010] over all unitary divisors d of n (that is, gcd(d,n/d) = 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

A055631 Sum of Euler's totient function phi of distinct primes dividing n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

A249396 Composite numbers whose Euler totient divides the sum of the Euler totients of the numbers less than n that are relatively prime to n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

PARI

Extensions

A143620 Triangle read by rows, square of A054521, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A332686 a(n) = Sum_{k=1..n} phi(k/gcd(n, k)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula