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

 

Logo

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.

License Agreements, Terms of Use, Privacy Policy. .

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