A053571 -id:A053571 - 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

A055632 Sum of totient function of primes dividing n is a prime.

Original entry on oeis.org

3, 6, 9, 10, 12, 14, 18, 20, 22, 24, 26, 27, 28, 30, 34, 36, 38, 40, 44, 46, 48, 50, 52, 54, 56, 58, 60, 62, 66, 68, 70, 72, 74, 76, 80, 81, 82, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 112, 116, 118, 120, 122, 124, 130, 132, 134, 136, 140, 142, 144, 146

Offset: 1

Labos Elemer, Jun 06 2000

nonn

Observe that this sequence includes even numbers and for all primes p as (a phi-sum) an infinite number of solutions exist, like e.g. (2^w)*p, with 1+p-1=p Phi-sum over its factors.

			If n=2^a*3^b*5^c*7^d*11^e then prime-factor set is {2,3,5,7,11}. The totient function values of this set are {1,2,4,6,10} and the sum is 1+2+4+6+10=23.

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A001221, A006093, A053571, A055631.

Select[Range@ 150, PrimeQ@ Total@ Map[EulerPhi@ # &, FactorInteger[#][[All, 1]]] &] (* Michael De Vlieger, Oct 26 2017 *)

isok(n) = my(vp = factor(n)[,1]); isprime(sum(i=1, #vp, eulerphi(vp[i]))); \\ Michel Marcus, Dec 19 2013

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

cp's OEIS Frontend

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

A055632 Sum of totient function of primes dividing n is a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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