login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

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). 15
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, 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.

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

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 *)

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: A052274 A085314 A085310 * A155918 A097248 A097247

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 16 09:34 EST 2018. Contains 318160 sequences. (Running on oeis4.)