The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A055653 Sum of phi(d) [A000010] over all unitary divisors d of n (that is, gcd(d,n/d) = 1). 19

%I

%S 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,

%T 19,21,29,30,31,17,33,34,35,21,37,38,39,25,41,42,43,33,35,46,47,27,43,

%U 42,51,39,53,38,55,35,57,58,59,45,61,62,49,33,65,66,67,51,69,70,71,35,73

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

%C Phi-summation over d-s if runs over all divisors is n, so these values are not exceeding n. Compare also other "Phi-summations" like A053570, A053571, or distinct primes dividing n, etc.

%C a(n) is also the number of solutions of x^(k+1)=x mod n for some k>=1. - _Steven Finch_, Apr 11 2006

%C 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

%C Equals row sums of triangle A156361 and inverse Mobius transform of A114810. - _Gary W. Adamson_, Feb 28 2009

%C a(m) = m iff m is squarefree, a(A005117(n)) = A005117(n). - _Reinhard Zumkeller_, Mar 11 2012

%C Apostol & Tóth call this ϱ(n), i.e., varrho(n). - _Charles R Greathouse IV_, Apr 23 2013

%D J. Morgado, Inteiros regulares módulo n, Gazeta de Matematica (Lisboa), 33 (1972), no. 125-128, 1-5. [From _Laszlo Toth_, Sep 04 2008]

%D J. Morgado, A property of the Euler phi-function concerning the integers which are regular modulo n, Portugal. Math., 33 (1974), 185-191.

%H Antti Karttunen, <a href="/A055653/b055653.txt">Table of n, a(n) for n = 1..65537</a> (first 1000 terms from T. D. Noe)

%H Osama Alkam and Emad Abu Osba, <a href="http://journals.tubitak.gov.tr/math/issues/mat-08-32-1/mat-32-1-4-0610-4.pdf">On the regular elements in Zn</a>, Turk J Math, 32 (2008) , 31-39.

%H B. Apostol, L. Petrescu, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Apostol/apostol3.html">Extremal Orders of Certain Functions Associated with Regular Integers (mod n)</a>, Journal of Integer Sequences, 2013, # 13.7.5.

%H Brăduţ Apostol and László Tóth, <a href="http://arxiv.org/abs/1304.2699">Some remarks on regular integers modulo n</a>, arXiv:1304.2699 [math.NT], 2013.

%H S. R. Finch, <a href="https://arxiv.org/abs/math/0605019">Idempotents and nilpotents modulo n</a>, arXiv:1304.2699 [math.NT], 2013.

%H V. S. Joshi, <a href="https://doi.org/10.1007/BFb0097176">Order-free integers (mod m)</a>, Number Theory (Mysore, 1981), Lect. Notes in Math. 938, Springer-Verlag, 1982, pp. 93-100.

%H Vaclav Kotesovec, <a href="/A055653/a055653.jpg">Plot of Sum_{k=1..n} a(k) / (Pi^2 * n^2 / 12) for n = 1..100000</a>

%H L. Tóth, <a href="http://arxiv.org/abs/0710.1936"> Regular integers modulo n</a>, arXiv:0710.1936 [math.NT], 2007-2008; Annales Univ. Sci. Budapest., Sect. Comp., 29 (2008), 263-275.

%H L. Toth, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Toth/toth3.html">A gcd-sum function over regular integers modulo n</a>, JIS 12 (2009) 09.2.5

%F 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

%F 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

%F Dirichlet convolution square of A318661(n)/A318662(n). - _Antti Karttunen_, Sep 03 2018

%F 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

%e 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}.

%e EulerPhi values of these divisors are: {1,2,4,6,6,8,12,24,12,24,36,48,48,72,144,288}.

%e The sum is 735, thus a(1260)=735.

%e 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.

%p 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:

%t a[n_] := Total[EulerPhi[Select[Divisors[n], GCD[#, n/#] == 1 &]]]; Array[a, 73] (* _Jean-François Alcover_, May 03 2011 *)

%o a055653 = sum . map a000010 . a077610_row

%o -- _Reinhard Zumkeller_, Mar 11 2012

%o (PARI) 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

%o (PARI) 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

%Y Cf. A000010, A053570, A053571, A000188, A006833, A055654, A157361, A114810, A000010, A077610, A318661, A318662.

%K nonn,easy,nice,mult

%O 1,2

%A _Labos Elemer_, Jun 07 2000

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 2 12:56 EDT 2020. Contains 334772 sequences. (Running on oeis4.)