A114810 -id:A114810 - cp's OEIS frontend

A157361 Triangle read by rows, A051731 * (A114810 * 0^(n-k)).

1, 1, 1, 1, 0, 2, 1, 1, 0, 1, 1, 0, 0, 0, 4, 1, 1, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 6, 1, 1, 0, 1, 0, 0, 0, 2, 1, 0, 2, 0, 0, 0, 0, 0, 4, 1, 1, 0, 0, 4, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 1, 1, 2, 1, 0, 2, 0, 0, 0, 0, 0, 2

Offset: 1

Gary W. Adamson, Feb 28 2009

Row sums = A055653: (1, 2, 3, 3, 5, 6, 7, 5,...)

			First few rows of the triangle =
1;
1, 1;
1, 0, 2;
1, 1, 0, 1;
1, 0, 0, 0, 4;
1, 1, 2, 0, 0, 2;
1, 0, 0, 0, 0, 0, 6;
1, 1, 0, 1, 0, 0, 0, 2;
1, 0, 2, 0, 0, 0, 0, 0, 4;
1, 1, 0, 0, 4, 0, 0, 0, 0, 4;
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10;
1, 1, 2, 1, 0, 2, 0, 0, 0, 0, 0, 2;
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12;
1, 1, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 6;
...

Cf. A114810, A055653

Triangle read by rows, A051731 * (A114810 * 0^(n-k)); where A051731 = the inverse Mobius transform and (A114810 * 0^(n-k)) = an infinite lower triangular matrix with A114810 as the main diagonal: (1, 1, 2, 1, 4, 2, 6,...) and the rest zeros.

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

Original entry on oeis.org

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

cp's OEIS Frontend

A157361 Triangle read by rows, A051731 * (A114810 * 0^(n-k)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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