The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 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
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS 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. 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 A156361 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 REFERENCES 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. LINKS 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. 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 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. Toth, A gcd-sum function over regular integers modulo n, JIS 12 (2009) 09.2.5. FORMULA 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 EXAMPLE 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. MAPLE 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: MATHEMATICA 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 *) PROG (Haskell) a055653 = sum . map a000010 . a077610_row -- Reinhard Zumkeller, Mar 11 2012 (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 (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 CROSSREFS Cf. A000010, A053570, A053571, A000188, A006833, A055654, A157361, A114810, A000010, A077610, A318661, A318662. Sequence in context: A353832 A085314 A085310 * A155918 A344705 A331170 Adjacent sequences: A055650 A055651 A055652 * A055654 A055655 A055656 KEYWORD nonn,easy,nice,mult AUTHOR Labos Elemer, Jun 07 2000 STATUS approved

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

Last modified December 8 08:22 EST 2022. Contains 358693 sequences. (Running on oeis4.)