A059376 -id:A059376 - cp's OEIS frontend

A000010 Euler totient function phi(n): count numbers <= n and prime to n.

1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44

Offset: 1

N. J. A. Sloane

Number of elements in a reduced residue system modulo n.
Degree of the n-th cyclotomic polynomial (cf. A013595). - Benoit Cloitre, Oct 12 2002
Number of distinct generators of a cyclic group of order n. Number of primitive n-th roots of unity. (A primitive n-th root x is such that x^k is not equal to 1 for k = 1, 2, ..., n - 1, but x^n = 1.) - Lekraj Beedassy, Mar 31 2005
Also number of complex Dirichlet characters modulo n; Sum_{k=1..n} a(k) is asymptotic to (3/Pi^2)*n^2. - Steven Finch, Feb 16 2006
a(n) is the highest degree of irreducible polynomial dividing 1 + x + x^2 + ... + x^(n-1) = (x^n - 1)/(x - 1). - Alexander Adamchuk, Sep 02 2006, corrected Sep 27 2006
a(p) = p - 1 for prime p. a(n) is even for n > 2. For n > 2, a(n)/2 = A023022(n) = number of partitions of n into 2 ordered relatively prime parts. - Alexander Adamchuk, Jan 25 2007
Number of automorphisms of the cyclic group of order n. - Benoit Jubin, Aug 09 2008
a(n+2) equals the number of palindromic Sturmian words of length n which are "bispecial", prefix or suffix of two Sturmian words of length n + 1. - Fred Lunnon, Sep 05 2010
Suppose that a and n are coprime positive integers, then by Euler's totient theorem, any factor of n divides a^phi(n) - 1. - Lei Zhou, Feb 28 2012
If m has k prime factors, (p_1, p_2, ..., p_k), then phi(m*n) = (Product_{i=1..k} phi (p_i*n))/phi(n)^(k-1). For example, phi(42*n) = phi(2*n)*phi(3*n)*phi(7*n)/phi(n)^2. - Gary Detlefs, Apr 21 2012
Sum_{n>=1} a(n)/n! = 1.954085357876006213144... This sum is referenced in Plouffe's inverter. - Alexander R. Povolotsky, Feb 02 2013 (see A336334. - Hugo Pfoertner, Jul 22 2020)
The order of the multiplicative group of units modulo n. - Michael Somos, Aug 27 2013
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Dec 30 2016
From Eric Desbiaux, Jan 01 2017: (Start)
a(n) equals the Ramanujan sum c_n(n) (last term on n-th row of triangle A054533).
a(n) equals the Jordan function J_1(n) (cf. A007434, A059376, A059377, which are the Jordan functions J_2, J_3, J_4, respectively). (End)
For n > 1, a(n) appears to be equal to the number of semi-meander solutions for n with top arches containing exactly 2 mountain ranges and exactly 2 arches of length 1. - Roger Ford, Oct 11 2017
a(n) is the minimum dimension of a lattice able to generate, via cut-and-project, the quasilattice whose diffraction pattern features n-fold rotational symmetry. The case n=15 is the first n > 1 in which the following simpler definition fails: "a(n) is the minimum dimension of a lattice with n-fold rotational symmetry". - Felix Flicker, Nov 08 2017
Number of cyclic Latin squares of order n with the first row in ascending order. - Eduard I. Vatutin, Nov 01 2020
a(n) is the number of rational numbers p/q >= 0 (in lowest terms) such that p + q = n. - Rémy Sigrist, Jan 17 2021
From Richard L. Ollerton, May 08 2021: (Start)
Formulas for the numerous OEIS entries involving Dirichlet convolution of a(n) and some sequence h(n) can be derived using the following (n >= 1):
Sum_{d|n} phi(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k)) [see P. H. van der Kamp link] = Sum_{d|n} h(d)*phi(n/d) = Sum_{k=1..n} h(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). Similarly,
Sum_{d|n} phi(d)*h(d) = Sum_{k=1..n} h(n/gcd(n,k)) = Sum_{k=1..n} h(gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)).
More generally,
Sum_{d|n} h(d) = Sum_{k=1..n} h(gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))/phi(n/gcd(n,k)).
In particular, for sequences involving the Möbius transform:
Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where mu = A008683.
Use of gcd(n,k)*lcm(n,k) = n*k and phi(gcd(n,k))*phi(lcm(n,k)) = phi(n)*phi(k) provide further variations. (End)
From Richard L. Ollerton, Nov 07 2021: (Start)
Formulas for products corresponding to the sums above may found using the substitution h(n) = log(f(n)) where f(n) > 0 (for example, cf. formulas for the sum A018804 and product A067911 of gcd(n,k)):
Product_{d|n} f(n/d)^phi(d) = Product_{k=1..n} f(gcd(n,k)) = Product_{d|n} f(d)^phi(n/d) = Product_{k=1..n} f(n/gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d)^phi(d) = Product_{k=1..n} f(n/gcd(n,k)) = Product_{k=1..n} f(gcd(n,k))^(phi(gcd(n,k))/phi(n/gcd(n,k))),
Product_{d|n} f(d) = Product_{k=1..n} f(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(1/phi(n/gcd(n,k))),
Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))), where mu = A008683. (End)
a(n+1) is the number of binary words with exactly n distinct subsequences (when n > 0). - Radoslaw Zak, Nov 29 2021

			G.f. = x + x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 2*x^6 + 6*x^7 + 4*x^8 + 6*x^9 + 4*x^10 + ...
a(8) = 4 with {1, 3, 5, 7} units modulo 8. a(10) = 4 with {1, 3, 7, 9} units modulo 10. - _Michael Somos_, Aug 27 2013
From _Eduard I. Vatutin_, Nov 01 2020: (Start)
The a(5)=4 cyclic Latin squares with the first row in ascending order are:
  0 1 2 3 4   0 1 2 3 4   0 1 2 3 4   0 1 2 3 4
  1 2 3 4 0   2 3 4 0 1   3 4 0 1 2   4 0 1 2 3
  2 3 4 0 1   4 0 1 2 3   1 2 3 4 0   3 4 0 1 2
  3 4 0 1 2   1 2 3 4 0   4 0 1 2 3   2 3 4 0 1
  4 0 1 2 3   3 4 0 1 2   2 3 4 0 1   1 2 3 4 0
(End)

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
M. Baake and U. Grimm, Aperiodic Order Vol. 1: A Mathematical Invitation, Encyclopedia of Mathematics and its Applications 149, Cambridge University Press, 2013: see Tables 3.1 and 3.2.
Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 409.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 193.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 154-156.
C. W. Curtis, Pioneers of Representation Theory ..., Amer. Math. Soc., 1999; see p. 3.
J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Ellipses, Paris, 2004, Problème 529, pp. 71-257.
L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, Chapter V.
S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 115-119.
Carl Friedrich Gauss, "Disquisitiones Arithmeticae", Yale University Press, 1965; see p. 21.
Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Math., 2n-d ed.; Addison-Wesley, 1994, p. 137.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section B36.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 60, 62, 63, 288, 323, 328, 330.
Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, pages 261-264, the Coach theorem.
Jean-Marie Monier, Analyse, Exercices corrigés, 2ème année MP, Dunod, 1997, Exercice 3.2.21 pp. 281-294.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1976, Vol. II, problem 71, p. 126.
Paulo Ribenboim, The New Book of Prime Number Records.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 28-33.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 162-167.

Daniel Forgues, Table of n, phi(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972.
Dario A. Alpern, Factorization using the Elliptic Curve Method (along with sigma_0, sigma_1 and phi functions)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.7, pp. 776-778.
F. Bayart, Indicateur d'Euler (in French).
Alexander Bogomolny, Euler Function and Theorem.
Chris K. Caldwell, The Prime Glossary, Euler's phi function
Robert D. Carmichael, A table of the values of m corresponding to given values of phi(m), Amer. J. Math., 30 (1908), 394-400. [Annotated scanned copy]
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Kevin Ford, The number of solutions of phi(x)=m, arXiv:math/9907204 [math.NT], 1999.
Kevin Ford, Florian Luca and Pieter Moree, Values of the Euler phi-function not divisible by a given odd prime, and the distribution of Euler-Kronecker constants for cyclotomic fields, arXiv:1108.3805 [math.NT], 2011.
H. Fripertinger, The Euler phi function.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
E. Pérez Herrero, Totient Carnival partitions, Psychedelic Geometry Blogspot.
Peter H. van der Kamp, On the Fourier transform of the greatest common divisor, arXiv:1201.3139 [math.NT]
M. Lal and P. Gillard, Table of Euler's phi function, n < 10^5, Math. Comp., 23 (1969), 682-683.
Derrick N. Lehmer, Review of Dickson's History of the Theory of Numbers, Bull. Amer. Math. Soc., 26 (1919), 125-132.
Peter Luschny, Sequences related to Euler's totient function.
R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
Mathematics Stack Exchange, Is the Euler phi function bounded below? (2013).
Mathforum, Proving phi(m) Is Even.
Keith Matthews, Factorizing n and calculating phi(n), omega(n), d(n), sigma(n) and mu(n).
Graeme McRae, Euler's Totient Function.
François Nicolas, A simple, polynomial-time algorithm for the matrix torsion problem, arXiv:0806.2068 [cs.DM], 2009.
Matthew Parker, The first 5 million terms (7-Zip compressed file).
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp., to appear (2014).
Primefan, Euler's Totient Function Values For n=1 to 500, with Divisor Lists.
Marko Riedel, Combinatorics and number theory page.
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), no. 1, 64-94.
K. Schneider, Euler phi-function, PlanetMath.org.
Wacław F. Sierpiński, Euler's Totient Function And The Theorem Of Euler.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 14.
Ulrich Sondermann, Euler's Totient Function.
William A. Stein, Phi is a Multiplicative Function
Pinthira Tangsupphathawat, Takao Komatsu and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.
G. Villemin, Totient d'Euler.
K. W. Wegner, Values of phi(x) = n for n from 2 through 1978, mimeographed manuscript, no date. [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Modulo Multiplication Group.
Eric Weisstein's World of Mathematics, Moebius Transform.
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.
Wikipedia, Multiplicative group of integers modulo n.
Wikipedia, Ramanujan's sum
Wolfram Research, First 50 values of phi(n).
Gang Xiao, Numerical Calculator, To display phi(n) operate on "eulerphi(n)".
Index entries for "core" sequences
Index to divisibility sequences

Cf. A002088 (partial sums), A008683, A003434 (steps to reach 1), A007755, A049108, A002202 (values), A011755 (Sum k*phi(k)).
Cf. also A005277 (nontotient numbers). For inverse see A002181, A006511, A058277.
Jordan function J_k(n) is a generalization - see A059379 and A059380 (triangle of values of J_k(n)), this sequence (J_1), A007434 (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).
Cf. A054521, A023022, A054525.
Row sums of triangles A134540, A127448, A143239, A143353 and A143276.
Equals right and left borders of triangle A159937. - Gary W. Adamson, Apr 26 2009
Values for prime powers p^e: A006093 (e=1), A036689 (e=2), A135177 (e=3), A138403 (e=4), A138407 (e=5), A138412 (e=6).
Values for perfect powers n^e: A002618 (e=2), A053191 (e=3), A189393 (e=4), A238533 (e=5), A306411 (e=6), A239442 (e=7), A306412 (e=8), A239443 (e=9).
Cf. A003558, A135303.
Cf. A152455, A080737.
Cf. A076479.
Cf. A023900 (Dirichlet inverse of phi), A306633 (Dgf at s=3).

Axiom
```
[eulerPhi(n) for n in 1..100]
```

a n = length (filter (==1) (map (gcd n) [1..n])) -- Allan C. Wechsler, Dec 29 2014

# Computes the first N terms of the sequence.
function A000010List(N)
    phi = [i for i in 1:N + 1]
    for i in 2:N + 1
        if phi[i] == i
            for j in i:i:N + 1
                phi[j] -= div(phi[j], i)
    end end end
return phi end
println(A000010List(68))  # Peter Luschny, Sep 03 2023

[ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006

with(numtheory): A000010 := phi; [ seq(phi(n), n=1..100) ]; # version 1
with(numtheory): phi := proc(n) local i,t1,t2; t1 := ifactors(n)[2]; t2 := n*mul((1-1/t1[i][1]),i=1..nops(t1)); end; # version 2
# Alternative without library function:
A000010List := proc(N) local i, j, phi;
    phi := Array([seq(i, i = 1 .. N+1)]);
    for i from 2 to N + 1 do
        if phi[i] = i then
            for j from i by i to N + 1 do
                phi[j] := phi[j] - iquo(phi[j], i) od
        fi od;
return phi end:
A000010List(68);  # Peter Luschny, Sep 03 2023

Mathematica
```
Array[EulerPhi, 70]
```

makelist(totient(n),n,0,1000); /* Emanuele Munarini, Mar 26 2011 */

{a(n) = if( n==0, 0, eulerphi(n))}; /* Michael Somos, Feb 05 2011 */

from sympy.ntheory import totient
print([totient(i) for i in range(1, 70)])  # Indranil Ghosh, Mar 17 2017

# Note also the implementation in A365339.

def A000010(n): return euler_phi(n) # Jaap Spies, Jan 07 2007

[euler_phi(n) for n in range(1, 70)]  # Zerinvary Lajos, Jun 06 2009

phi(n) = n*Product_{distinct primes p dividing n} (1 - 1/p).
Sum_{d divides n} phi(d) = n.
phi(n) = Sum_{d divides n} mu(d)*n/d, i.e., the Moebius transform of the natural numbers; mu() = Moebius function A008683().
Dirichlet generating function Sum_{n>=1} phi(n)/n^s = zeta(s-1)/zeta(s). Also Sum_{n >= 1} phi(n)*x^n/(1 - x^n) = x/(1 - x)^2.
Multiplicative with a(p^e) = (p - 1)*p^(e-1). - David W. Wilson, Aug 01 2001
Sum_{n>=1} (phi(n)*log(1 - x^n)/n) = -x/(1 - x) for -1 < x < 1 (cf. A002088) - Henry Bottomley, Nov 16 2001
a(n) = binomial(n+1, 2) - Sum_{i=1..n-1} a(i)*floor(n/i) (see A000217 for inverse). - Jon Perry, Mar 02 2004
It is a classical result (certainly known to Landau, 1909) that lim inf n/phi(n) = 1 (taking n to be primes), lim sup n/(phi(n)*log(log(n))) = e^gamma, with gamma = Euler's constant (taking n to be products of consecutive primes starting from 2 and applying Mertens' theorem). See e.g. Ribenboim, pp. 319-320. - Pieter Moree, Sep 10 2004
a(n) = Sum_{i=1..n} |k(n, i)| where k(n, i) is the Kronecker symbol. Also a(n) = n - #{1 <= i <= n : k(n, i) = 0}. - Benoit Cloitre, Aug 06 2004 [Corrected by Jianing Song, Sep 25 2018]
Conjecture: Sum_{i>=2} (-1)^i/(i*phi(i)) exists and is approximately 0.558 (A335319). - Orges Leka (oleka(AT)students.uni-mainz.de), Dec 23 2004
From Enrique Pérez Herrero, Sep 07 2010: (Start)
a(n) = Sum_{i=1..n} floor(sigma_k(i*n)/sigma_k(i)*sigma_k(n)), where sigma_2 is A001157.
a(n) = Sum_{i=1..n} floor(tau_k(i*n)/tau_k(i)*tau_k(n)), where tau_3 is A007425.
a(n) = Sum_{i=1..n} floor(rad(i*n)/rad(i)*rad(n)), where rad is A007947. (End)
a(n) = A173557(n)*A003557(n). - R. J. Mathar, Mar 30 2011
a(n) = A096396(n) + A096397(n). - Reinhard Zumkeller, Mar 24 2012
phi(p*n) = phi(n)*(floor(((n + p - 1) mod p)/(p - 1)) + p - 1), for primes p. - Gary Detlefs, Apr 21 2012
For odd n, a(n) = 2*A135303((n-1)/2)*A003558((n-1)/2) or phi(n) = 2*c*k; the Coach theorem of Pedersen et al. Cf. A135303. - Gary W. Adamson, Aug 15 2012
G.f.: Sum_{n>=1} mu(n)*x^n/(1 - x^n)^2, where mu(n) = A008683(n). - Mamuka Jibladze, Apr 05 2015
a(n) = n - cototient(n) = n - A051953(n). - Omar E. Pol, May 14 2016
a(n) = lim_{s->1} n*zeta(s)*(Sum_{d divides n} A008683(d)/(e^(1/d))^(s-1)), for n > 1. - Mats Granvik, Jan 26 2017
Conjecture: a(n) = Sum_{a=1..n} Sum_{b=1..n} Sum_{c=1..n} 1 for n > 1. The sum is over a,b,c such that n*c - a*b = 1. - Benedict W. J. Irwin, Apr 03 2017
a(n) = Sum_{j=1..n} gcd(j, n) cos(2*Pi*j/n) = Sum_{j=1..n} gcd(j, n) exp(2*Pi*i*j/n) where i is the imaginary unit. Notice that the Ramanujan's sum c_n(k) := Sum_{j=1..n, gcd(j, n) = 1} exp(2*Pi*i*j*k/n) gives a(n) = Sum_{k|n} k*c_(n/k)(1) = Sum_{k|n} k*mu(n/k). - Michael Somos, May 13 2018
G.f.: x*d/dx(x*d/dx(log(Product_{k>=1} (1 - x^k)^(-mu(k)/k^2)))), where mu(n) = A008683(n). - Mamuka Jibladze, Sep 20 2018
a(n) = Sum_{d|n} A007431(d). - Steven Foster Clark, May 29 2019
G.f. A(x) satisfies: A(x) = x/(1 - x)^2 - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, Sep 06 2019
a(n) >= sqrt(n/2) (Nicolas). - Hugo Pfoertner, Jun 01 2020
a(n) > n/(exp(gamma)*log(log(n)) + 5/(2*log(log(n)))), except for n=223092870 (Rosser, Schoenfeld). - Hugo Pfoertner, Jun 02 2020
From Bernard Schott, Nov 28 2020: (Start)
Sum_{m=1..n} 1/a(m) = A028415(n)/A048049(n) -> oo when n->oo.
Sum_{n >= 1} 1/a(n)^2 = A109695.
Sum_{n >= 1} 1/a(n)^3 = A335818.
Sum_{n >= 1} 1/a(n)^k is convergent iff k > 1.
a(2n) = a(n) iff n is odd, and, a(2n) > a(n) iff n is even. (End) [Actually, a(2n) = 2*a(n) for even n. - Jianing Song, Sep 18 2022]
a(n) = 2*A023896(n)/n, n > 1. - Richard R. Forberg, Feb 03 2021
From Richard L. Ollerton, May 09 2021: (Start)
For n > 1, Sum_{k=1..n} phi^{(-1)}(n/gcd(n,k))*a(gcd(n,k))/a(n/gcd(n,k)) = 0, where phi^{(-1)} = A023900.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(gcd(n,k)))*rad(gcd(n,k))/gcd(n,k) = 0.
For n > 1, Sum_{k=1..n} a(gcd(n,k))*mu(rad(n/gcd(n,k)))*rad(n/gcd(n,k))*gcd(n,k) = 0.
Sum_{k=1..n} a(gcd(n,k))/a(n/gcd(n,k)) = n. (End)
a(n) = Sum_{d|n, e|n} gcd(d, e)*mobius(n/d)*mobius(n/e) (the sum is a multiplicative function of n by Tóth, and takes the value p^e - p^(e-1) for n = p^e, a prime power). - Peter Bala, Jan 22 2024
Sum_{n >= 1} phi(n)*x^n/(1 + x^n) = x + 3*x^3 + 5*x^5 + 7*x^7 + ... = Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(4*n-2)). For the first equality see Pólya and Szegő, problem 71, p. 126. - Peter Bala, Feb 29 2024
Conjecture: a(n) = lim_{k->oo} (n^(k + 1))/A000203(n^k). - Velin Yanev, Dec 04 2024 [A000010(p) = p-1, A000203(p^k) = (p^(k+1)-1)/(p-1), so the conjecture is true if n is prime. - Vaclav Kotesovec, Dec 19 2024]

A003557 n divided by largest squarefree divisor of n; if n = Product p(k)^e(k) then a(n) = Product p(k)^(e(k)-1), with a(1) = 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 4, 3, 1, 1, 2, 1, 1, 1, 8, 1, 3, 1, 2, 1, 1, 1, 4, 5, 1, 9, 2, 1, 1, 1, 16, 1, 1, 1, 6, 1, 1, 1, 4, 1, 1, 1, 2, 3, 1, 1, 8, 7, 5, 1, 2, 1, 9, 1, 4, 1, 1, 1, 2, 1, 1, 3, 32, 1, 1, 1, 2, 1, 1, 1, 12, 1, 1, 5, 2, 1, 1, 1, 8, 27, 1, 1, 2, 1, 1, 1, 4, 1, 3, 1, 2, 1, 1, 1, 16, 1, 7

Offset: 1

Marc LeBrun

a(n) is the size of the Frattini subgroup of the cyclic group C_n - Ahmed Fares (ahmedfares(AT)my-deja.com), Jun 07 2001.
Also of the Frattini subgroup of the dihedral group with 2*n elements. - Sharon Sela (sharonsela(AT)hotmail.com), Jan 01 2002
Number of solutions to x^m==0 (mod n) provided that n < 2^(m+1), i.e. the sequence of sequences A000188, A000189, A000190, etc. converges to this sequence. - Henry Bottomley, Sep 18 2001
a(n) is the number of nilpotent elements in the ring Z/nZ. - Laszlo Toth, May 22 2009
The sequence of partial products of a(n) is A085056(n). - Peter Luschny, Jun 29 2009
The first occurrence of n in this sequence is at A064549(n). - Franklin T. Adams-Watters, Jul 25 2014
From Hal M. Switkay, Jul 03 2025: (Start)
For n > 1, a(n) is a proper divisor of n. Thus the sequence n, a(n), a(a(n)), ... eventually becomes 1. This yields a minimal factorization of n as a product of squarefree numbers (A005117), each factor dividing all larger factors, in a factorization that is conjugate to the minimal factorization of n as a product of prime powers (A000961), as follows.
Let f(n,0) = n, and let f(n,k) = a(f(n,k-1)) for k > 0. A051903(n) is the minimal value of k such that f(n,k) = 1. A051903(n) <= log(n)/log(2). Since n/a(n) = A007947(n) is always squarefree by definition, n is a product of squarefree factors in the form Product_{i=1..A051903(n)} [f(n,i-1)/f(n,i)].
The two factorizations correspond to conjugate partitions of bigomega(n) = A001222(n). (End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Henry Bottomley, Some Smarandache-type multiplicative sequences.
Steven R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 2006-2017.

Cf. A007947, A062378, A062379, A064549, A300717 (Möbius transform), A326306 (inv. Möbius transf.), A328572.
Sequences that are multiples of this sequence (the other factor of a pointwise product is given in parentheses): A000010 (A173557), A000027 (A007947), A001615 (A048250), A003415 (A342001), A007434 (A345052), A057521 (A071773).
Cf. A082695 (Dgf at s=2), A065487 (Dgf at s=3).
Cf. A000961, A001222, A005117, A051903.

a003557 n = product $ zipWith (^)
                      (a027748_row n) (map (subtract 1) $ a124010_row n)
-- Reinhard Zumkeller, Dec 20 2013

using Nemo
function A003557(n)
    n < 4 && return 1
    q = prod([p for (p, e) ∈ Nemo.factor(fmpz(n))])
    return n == q ? 1 : div(n, q)
end
[A003557(n) for n in 1:90] |> println  # Peter Luschny, Feb 07 2021

[(&+[(Floor(k^n/n)-Floor((k^n-1)/n)): k in [1..n]]): n in [1..100]]; // G. C. Greubel, Nov 02 2018

A003557 := n -> n/ilcm(op(numtheory[factorset](n))):
seq(A003557(n), n=1..98); # Peter Luschny, Mar 23 2011
seq(n / NumberTheory:-Radical(n), n = 1..98); # Peter Luschny, Jul 20 2021

Prepend[ Array[ #/Times@@(First[ Transpose[ FactorInteger[ # ] ] ])&, 100, 2 ], 1 ] (* Olivier Gérard, Apr 10 1997 *)

a(n)=n/factorback(factor(n)[,1]) \\ Charles R Greathouse IV, Nov 17 2014

for(n=1, 100, print1(direuler(p=2, n, (1 - p*X + X)/(1 - p*X))[n], ", ")) \\ Vaclav Kotesovec, Jun 20 2020

from sympy.ntheory.factor_ import core
from sympy import divisors
def a(n): return n / max(i for i in divisors(n) if core(i) == i)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 16 2017

from math import prod
from sympy import primefactors
def A003557(n): return n//prod(primefactors(n)) # Chai Wah Wu, Nov 04 2022

def A003557(n) : return n*mul(1/p for p in prime_divisors(n))
[A003557(n) for n in (1..98)] # Peter Luschny, Jun 10 2012

Multiplicative with a(p^e) = p^(e-1). - Vladeta Jovovic, Jul 23 2001
a(n) = n/rad(n) = n/A007947(n) = sqrt(J_2(n)/J_2(rad(n))), where J_2(n) is A007434. - Enrique Pérez Herrero, Aug 31 2010
a(n) = (J_k(n)/J_k(rad(n)))^(1/k), where J_k is the k-th Jordan Totient Function: (J_2 is A007434 and J_3 A059376). - Enrique Pérez Herrero, Sep 03 2010
Dirichlet convolution of A000027 and A097945. - R. J. Mathar, Dec 20 2011
a(n) = A000010(n)/|A023900(n)|. - Eric Desbiaux, Nov 15 2013
a(n) = Product_{k = 1..A001221(n)} (A027748(n,k)^(A124010(n,k)-1)). - Reinhard Zumkeller, Dec 20 2013
a(n) = Sum_{k=1..n}(floor(k^n/n)-floor((k^n-1)/n)). - Anthony Browne, May 11 2016
a(n) = e^[Sum_{k=2..n} (floor(n/k)-floor((n-1)/k))*(1-A010051(k))*Mangoldt(k)] where Mangoldt is the Mangoldt function. - Anthony Browne, Jun 16 2016
a(n) = Sum_{d|n} mu(d) * phi(d) * (n/d), where mu(d) is the Moebius function and phi(d) is the Euler totient function (rephrases formula of Dec 2011). - Daniel Suteu, Jun 19 2018
G.f.: Sum_{k>=1} mu(k)*phi(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Nov 02 2018
Dirichlet g.f.: Product_{primes p} (1 + 1/(p^s - p)). - Vaclav Kotesovec, Jun 24 2020
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))*gcd(n,k).
a(n) = Sum_{k=1..n} mu(gcd(n,k))*(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
a(n) = A001615(n)/A048250(n) = A003415/A342001(n) = A057521(n)/A071773(n). - Antti Karttunen, Jun 08 2021

Secondary definition added to the name by Antti Karttunen, Jun 08 2021

A000537 Sum of first n cubes; or n-th triangular number squared.

Original entry on oeis.org

0, 1, 9, 36, 100, 225, 441, 784, 1296, 2025, 3025, 4356, 6084, 8281, 11025, 14400, 18496, 23409, 29241, 36100, 44100, 53361, 64009, 76176, 90000, 105625, 123201, 142884, 164836, 189225, 216225, 246016, 278784, 314721, 354025, 396900, 443556, 494209, 549081

Offset: 0

N. J. A. Sloane

Number of parallelograms in an n X n rhombus. - Matti De Craene (Matti.DeCraene(AT)rug.ac.be), May 14 2000
Or, number of orthogonal rectangles in an n X n checkerboard, or rectangles in an n X n array of squares. - Jud McCranie, Feb 28 2003. Compare A085582.
Also number of 2-dimensional cage assemblies (cf. A059827, A059860).
The n-th triangular number T(n) = Sum_{r=1..n} r = n(n+1)/2 satisfies the relations: (i) T(n) + T(n-1) = n^2 and (ii) T(n) - T(n-1) = n by definition, so that n^2*n = n^3 = {T(n)}^2 - {T(n-1)}^2 and by summing on n we have Sum_{ r = 1..n } r^3 = {T(n)}^2 = (1+2+3+...+n)^2 = (n*(n+1)/2)^2. - Lekraj Beedassy, May 14 2004
Number of 4-tuples of integers from {0,1,...,n}, without repetition, whose last component is strictly bigger than the others. Number of 4-tuples of integers from {1,...,n}, with repetition, whose last component is greater than or equal to the others.
Number of ordered pairs of two-element subsets of {0,1,...,n} without repetition.
Number of ordered pairs of 2-element multisubsets of {1,...,n} with repetition.
1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2.
a(n) is the number of parameters needed in general to know the Riemannian metric g of an n-dimensional Riemannian manifold (M,g), by knowing all its second derivatives; even though to know the curvature tensor R requires (due to symmetries) (n^2)*(n^2-1)/12 parameters, a smaller number (and a 4-dimensional pyramidal number). - Jonathan Vos Post, May 05 2006
Also number of hexagons with vertices in an hexagonal grid with n points in each side. - Ignacio Larrosa Cañestro, Oct 15 2006
Number of permutations of n distinct letters (ABCD...) each of which appears twice with 4 and n-4 fixed points. - Zerinvary Lajos, Nov 09 2006
With offset 1 = binomial transform of [1, 8, 19, 18, 6, ...]. - Gary W. Adamson, Dec 03 2008
The sequence is related to A000330 by a(n) = n*A000330(n) - Sum_{i=0..n-1} A000330(i): this is the case d=1 in the identity n*(n*(d*n-d+2)/2) - Sum_{i=0..n-1} i*(d*i-d+2)/2 = n*(n+1)*(2*d*n-2*d+3)/6. - Bruno Berselli, Apr 26 2010, Mar 01 2012
From Wolfdieter Lang, Jan 11 2013: (Start)
For sums of powers of positive integers S(k,n) := Sum_{j=1..n}j^k one has the recurrence S(k,n) = (n+1)*S(k-1,n) - Sum_{l=1..n} S(k-1,l), n >= 1, k >= 1.
This was used for k=4 by Ibn al-Haytham in an attempt to compute the volume of the interior of a paraboloid. See the Strick reference where the trick he used is shown, and the W. Lang link.
This trick generalizes immediately to arbitrary powers k. For k=3: a(n) = (n+1)*A000330(n) - Sum_{l=1..n} A000330(l), which coincides with the formula given in the previous comment by Berselli. (End)
Regarding to the previous contribution, see also Matem@ticamente in Links field and comments on this recurrences in similar sequences (partial sums of n-th powers). - Bruno Berselli, Jun 24 2013
A rectangular prism with sides A000217(n), A000217(n+1), and A000217(n+2) has surface area 6*a(n+1). - J. M. Bergot, Aug 07 2013, edited with corrected indices by Antti Karttunen, Aug 09 2013
A formula for the r-th successive summation of k^3, for k = 1 to n, is (6*n^2+r*(6*n+r-1)*(n+r)!)/((r+3)!*(n-1)!), (H. W. Gould). - Gary Detlefs, Jan 02 2014
Note that this sequence and its formula were known to (and possibly discovered by) Nicomachus, predating Ibn al-Haytham by 800 years. - Charles R Greathouse IV, Apr 23 2014
a(n) is the number of ways to paint the sides of a nonsquare rectangle using at most n colors. Cf. A039623. - Geoffrey Critzer, Jun 18 2014
For n > 0: A256188(a(n)) = A000217(n) and A256188(m) != A000217(n) for m < a(n), i.e., positions of first occurrences of triangular numbers in A256188. - Reinhard Zumkeller, Mar 26 2015
There is no cube in this sequence except 0 and 1. - Altug Alkan, Jul 02 2016
Also the number of chordless cycles in the complete bipartite graph K_{n+1,n+1}. - Eric W. Weisstein, Jan 02 2018
a(n) is the sum of the elements in the multiplication table [0..n] X [0..n]. - Michel Marcus, May 06 2021

			G.f. = x + 9*x^2 + 36*x^3 + 100*x^4 + 225*x^5 + 441*x^6 + ... - _Michael Somos_, Aug 29 2022

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 813.
Avner Ash and Robert Gross, Summing it up, Princeton University Press, 2016, p. 62, eq. (6.3) for k=3.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 110ff.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 155.
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, pp. 36, 58.
Clifford Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Oxford University Press, 2001, p. 325.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
H. K. Strick, Geschichten aus der Mathematik II, Spektrum Spezial 3/11, p. 13.
D. Wells, You Are A Mathematician, "Counting rectangles in a rectangle", Problem 8H, pp. 240; 254, Penguin Books 1995.

T. D. Noe, Table of n, a(n) for n = 0..1000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Luciano Ancora, Sum of cubes of the first "n" natural numbers
Luciano Ancora, The Square Pyramidal Number and other figurate numbers
M. Azaola and F. Santos, The number of triangulations of the cyclic polytope C(n,n-4), Discrete Comput. Geom., 27 (2002), 29-48 (see Prop. 4.2(b)).
Marcel Berger, Encounter with a Geometer, Part II, Notices of the American Mathematical Society, Vol. 47, No. 3, (March 2000), pp. 326-340. [About the work of Mikhael Gromov.]
Bruno Berselli, A description of the recursive method in Comments lines: website Matem@ticamente (in Italian).
blackpenredpen, Math for fun, how many rectangles?, Youtube video (2018).
Bikash Chakraborty, Proof Without Words: Sums of Powers of Natural numbers, arXiv:2012.11539 [math.HO], 2020.
Robert Dawson, On Some Sequences Related to Sums of Powers, J. Int. Seq., Vol. 21 (2018), Article 18.7.6.
Shel Kaphan, How to see that the difference between two successive squared triangular numbers is a cube
Sameen Ahmed Khan, Sums of the powers of reciprocals of polygonal numbers, Int'l J. of Appl. Math. (2020) Vol. 33, No. 2, 265-282.
Seon-Hong Kim and Kenneth B. Stolarsky, Translations and Extensions of the Nicomachean Identity, J. Int. Seq. (2024), Vol. 27, Issue 6, Art. No. 24.6.3. See p. 1.
Wolfdieter Lang, Ibn al-Haytham's trick.
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, JIS 12 (2009) 09.5.5.
Feihu Liu, Guoce Xin, and Chen Zhang, Ehrhart Polynomials of Order Polytopes: Interpreting Combinatorial Sequences on the OEIS, arXiv:2412.18744 [math.CO], 2024. See p. 13.
Henri Picciotto, Sum of Cubes, Proof without words.
C. A. Pickover, "Wonders of Numbers, Adventures in Mathematics, Mind and Meaning," Zentralblatt review
C. J. Pita Ruiz V., Some Number Arrays Related to Pascal and Lucas Triangles, J. Int. Seq. 16 (2013) #13.5.7.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Faulhaber's Formula
Wikipedia, Faulhaber's formula
Wikipedia, Squared triangular number
G. Xiao, Sigma Server, Operate on "n^3"
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Convolution of A000217 and A008458.
Cf. A000330, A000538, A006003.
Row sums of triangles A094414 and A094415.
Second column of triangle A008459.
Row 3 of array A103438.
Cf. A000578, A002415, A024166, A101102, A101094, A101097.
Cf. A236770 (see crossrefs).
Cf. A000290, A253169, A256188.
Cf. A000217, A000292, A000332, A000566, A035287, A039623, A053382, A053383, A059376, A059827, A059860, A085582, A127777, A176271.

List([0..40],n->(n*(n+1)/2)^2); # Muniru A Asiru, Dec 05 2018

a000537 = a000290 . a000217  -- Reinhard Zumkeller, Mar 26 2015

[(n*(n+1)/2)^2: n in [0..50]]; // Wesley Ivan Hurt, Jun 06 2014

a:= n-> (n*(n+1)/2)^2:
seq(a(n), n=0..40);

Accumulate[Range[0, 50]^3] (* Harvey P. Dale, Mar 01 2011 *)
f[n_] := n^2 (n + 1)^2/4; Array[f, 39, 0] (* Robert G. Wilson v, Nov 16 2012 *)
Table[CycleIndex[{{1, 2, 3, 4}, {3, 2, 1, 4}, {1, 4, 3, 2}, {3, 4, 1, 2}}, s] /. Table[s[i] -> n, {i, 1, 2}], {n, 0, 30}] (* Geoffrey Critzer, Jun 18 2014 *)
Accumulate @ Range[0, 50]^2 (* Waldemar Puszkarz, Jan 24 2015 *)
Binomial[Range[20], 2]^2 (* Eric W. Weisstein, Jan 02 2018 *)
LinearRecurrence[{5, -10, 10, -5, 1}, {0, 1, 9, 36, 100}, 20] (* Eric W. Weisstein, Jan 02 2018 *)
CoefficientList[Series[-((x (1 + 4 x + x^2))/(-1 + x)^5), {x, 0, 20}], x] (* Eric W. Weisstein, Jan 02 2018 *)

PARI
```
a(n)=(n*(n+1)/2)^2
```

def A000537(n): return (n*(n+1)>>1)**2 # Chai Wah Wu, Oct 20 2023

a(n) = (n*(n+1)/2)^2 = A000217(n)^2 = Sum_{k=1..n} A000578(k), that is, 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2.
G.f.: (x+4*x^2+x^3)/(1-x)^5. - Simon Plouffe in his 1992 dissertation
a(n) = Sum ( Sum ( 1 + Sum (6*n) ) ), rephrasing the formula in A000578. - Xavier Acloque, Jan 21 2003
a(n) = Sum_{i=1..n} Sum_{j=1..n} i*j, row sums of A127777. - Alexander Adamchuk, Oct 24 2004
a(n) = A035287(n)/4. - Zerinvary Lajos, May 09 2007
This sequence could be obtained from the general formula n*(n+1)*(n+2)*(n+3)*...*(n+k)*(n*(n+k) + (k-1)*k/6)/((k+3)!/6) at k=1. - Alexander R. Povolotsky, May 17 2008
G.f.: x*F(3,3;1;x). - Paul Barry, Sep 18 2008
Sum_{k > 0} 1/a(k) = (4/3)*(Pi^2-9). - Jaume Oliver Lafont, Sep 20 2009
a(n) = Sum_{1 <= k <= m <= n} A176271(m,k). - Reinhard Zumkeller, Apr 13 2010
a(n) = Sum_{i=1..n} J_3(i)*floor(n/i), where J_ 3 is A059376. - Enrique Pérez Herrero, Feb 26 2012
a(n) = Sum_{i=1..n} Sum_{j=1..n} Sum_{k=1..n} min(i,j,k). - Enrique Pérez Herrero, Feb 26 2013 [corrected by Ridouane Oudra, Mar 05 2025]
a(n) = 6*C(n+2,4) + C(n+1,2) = 6*A000332(n+2) + A000217(n), (Knuth). - Gary Detlefs, Jan 02 2014
a(n) = -Sum_{j=1..3} j*Stirling1(n+1,n+1-j)*Stirling2(n+3-j,n). - Mircea Merca, Jan 25 2014
Sum_{n>=1} (-1)^(n+1)/a(n) = 4*(3-4*log(2)). - Vaclav Kotesovec, Feb 13 2015
a(n)*((s-2)*(s-3)/2) = P(3, P(s, n+1)) - P(s, P(3, n+1)), where P(s, m) = ((s-2)*m^2-(s-4)*m)/2 is the m-th s-gonal number. For s=7, 10*a(n) = A000217(A000566(n+1)) - A000566(A000217(n+1)). - Bruno Berselli, Aug 04 2015
From Ilya Gutkovskiy, Jul 03 2016: (Start)
E.g.f.: x*(4 + 14*x + 8*x^2 + x^3)*exp(x)/4.
Dirichlet g.f.: (zeta(s-4) + 2*zeta(s-3) + zeta(s-2))/4. (End)
a(n) = (Bernoulli(4, n+1) - Bernoulli(4, 1))/4, n >= 0, with the Bernoulli polynomial B(4, x) from row n=4 of A053382/A053383. See, e.g., the Ash-Gross reference, p. 62, eq. (6.3) for k=3. - Wolfdieter Lang, Mar 12 2017
a(n) = A000217((n+1)^2) - A000217(n+1)^2. - Bruno Berselli, Aug 31 2017
a(n) = n*binomial(n+2, 3) + binomial(n+2, 4) + binomial(n+1, 4). - Tony Foster III, Nov 14 2017
Another identity: ..., a(3) = (1/2)*(1*(2+4+6)+3*(4+6)+5*6) = 36, a(4) = (1/2)*(1*(2+4+6+8)+3*(4+6+8)+5*(6+8)+7*(8)) = 100, a(5) = (1/2)*(1*(2+4+6+8+10)+3*(4+6+8+10)+5*(6+8+10)+7*(8+10)+9*(10)) = 225, ... - J. M. Bergot, Aug 27 2022
Comment from Michael Somos, Aug 28 2022: (Start)
The previous comment expresses a(n) as the sum of all of the n X n multiplication table array entries.
For example, for n = 4:
     1  2  3  4
     2  4  6  8
     3  6  9 12
     4  8 12 16
This array sum can be split up as follows:
   +---+---------------+
   | 0 | 1   2   3   4 |    (0+1)*(1+2+3+4)
   |   +---+-----------+
   | 0 | 2 | 4   6   8 |    (1+2)*(2+3+4)
   |   |   +---+-------+
   | 0 | 3 | 6 | 9  12 |    (2+3)*(3+4)
   |   |   |   +---+---+
   | 0 | 4 | 8 |12 |16 |    (3+4)*(4)
   +---+---+---+---+---+
This kind of row+column sums was used by Ramanujan and others for summing Lambert series. (End)
a(n) = 6*A000332(n+4) - 12*A000292(n+1) + 7*A000217(n+1) - n - 1. - Adam Mohamed, Sep 05 2024

Edited by M. F. Hasler, May 02 2015

A001158 sigma_3(n): sum of cubes of divisors of n.

Original entry on oeis.org

1, 9, 28, 73, 126, 252, 344, 585, 757, 1134, 1332, 2044, 2198, 3096, 3528, 4681, 4914, 6813, 6860, 9198, 9632, 11988, 12168, 16380, 15751, 19782, 20440, 25112, 24390, 31752, 29792, 37449, 37296, 44226, 43344, 55261, 50654, 61740, 61544, 73710, 68922, 86688

Offset: 1

N. J. A. Sloane, R. K. Guy

If the canonical factorization of n into prime powers is the product of p^e(p) then sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1).
Sum_{d|n} 1/d^k is equal to sigma_k(n)/n^k. So sequences A017665-A017712 also give the numerators and denominators of sigma_k(n)/n^k for k = 1..24. The power sums sigma_k(n) are in sequences A000203 (k=1), A001157-A001160 (k=2,3,4,5), A013954-A013972 for k = 6..24. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 05 2001
Also the eigenvalues of the Hecke operator T_n for the entire modular normalized Eisenstein form E_4(z) (see A004009): T_n E_4 = a(n) E_4, n >= 1. For the Hecke operator T_n and eigenforms see, e.g., the Koecher-Krieg reference, p. 207, eq. (5) and p. 211, section 4, or the Apostol reference p. 120, eq. (13) and pp. 129 - 133. - Wolfdieter Lang, Jan 28 2016

			G.f. = x + 9*x^2 + 28*x^3 + 73*x^4 + 126*x^5 + 252*x^6 + 344*x^7 + ...

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math.Series 55, Tenth Printing, 1972, p. 827.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 38.
T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Second edition, Springer, 1990, pp. 120, 129 - 133.
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, AMS Chelsea Publishing, Providence, Rhode Island, 2002, p. 166.
Max Koecher and Aloys Krieg, Elliptische Funktionen und Modulformen, 2. Auflage, Springer, 2007, pp. 207, 211.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Zagier, Don. "Elliptic modular forms and their applications." The 1-2-3 of modular forms. Springer Berlin Heidelberg, 2008. 1-103. See p. 17, G_4(z).

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math.Series 55, Tenth Printing, 1972, p. 827.
Joerg Arndt, On computing the generalized Lambert series, arXiv:1202.6525v3 [math.CA], (2012).
D. B. Lahiri, Some arithmetical identities for Ramanujan's and divisor functions, Bulletin of the Australian Mathematical Society, Volume 1, Issue 3 December 1969, pp. 307-314. See Theorem 2 p. 308.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
Eric Weisstein's World of Mathematics, Divisor Function.
Index entries for sequences related to sigma(n)

Cf. A000005, A000203, A001157.
Cf. A051731, A127093.
Cf. A027748, A124010.
Cf. A004009, A064603 (partial sums).

a001158 n = product $ zipWith (\p e -> (p^(3*e + 3) - 1) `div` (p^3 - 1))
                      (a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Jun 30 2013

[DivisorSigma(3,n): n in [1..40]]; // Bruno Berselli, Apr 10 2013

seq(numtheory:-sigma[3](n),n=1..100); # Robert Israel, Feb 05 2016

Table[DivisorSigma[3,n],{n,100}] (* corrected by T. D. Noe, Mar 22 2009 *)

makelist(divsum(n,3),n,1,100); /* Emanuele Munarini, Mar 26 2011 */

N=99; q='q+O('q^N);
Vec(sum(n=1,N,n^3*q^n/(1-q^n))) /* Joerg Arndt, Feb 04 2011 */

{a(n) = if( n<1, 0, sumdiv(n, d, d^3))}; /* Michael Somos, Jan 07 2017 */

from sympy import divisor_sigma
def a(n): return divisor_sigma(n, 3)
print([a(n) for n in range(1, 43)]) # Michael S. Branicky, Jan 09 2021

[sigma(n, 3) for n in range(1, 40)]  # Zerinvary Lajos, Jun 04 2009

Multiplicative with a(p^e) = (p^(3e+3)-1)/(p^3-1). - David W. Wilson, Aug 01 2001
Dirichlet g.f. zeta(s)*zeta(s-3). - R. J. Mathar, Mar 04 2011
G.f.: sum(k>=1, k^3*x^k/(1-x^k)). - Benoit Cloitre, Apr 21 2003
Equals A051731 * [1, 8, 27, 64, 125, ...] = A127093 * [1, 4, 9, 16, 25, ...]. - Gary W. Adamson, Nov 02 2007
L.g.f.: -log(Product_{j>=1} (1-x^j)^(j^2)) = (1/1)*z^1 + (9/2)*z^2 + (28/3)*z^3 + (73/4)*z^4 + ... + (a(n)/n)*z^n + ... - Joerg Arndt, Feb 04 2011
a(n) = Sum{d|n} tau_{-2}^d*J_3(n/d), where tau_{-2} is A007427 and J_3 is A059376. - Enrique Pérez Herrero, Jan 19 2013
a(n) = A004009(n)/240. - Artur Jasinski, Sep 06 2016. See, e.g., Hardy, p. 166, (10.5.6), with Q = E_4, and with present offset 0. - Wolfdieter Lang, Jan 31 2017
8*a(n) = sum of cubes of even divisors of 2*n. - Wolfdieter Lang, Jan 07 2017
G.f.: Sum_{n >= 1} x^n*(1 + 4*x^n + x^(2*n))/(1 - x^n)^4. - Peter Bala, Jan 11 2021
Faster converging g.f.: Sum_{n >= 1} q^(n^2)*( n^3 + ((n + 1)^3 - 3*n^3)*q^n + (4 - 6*n^2)*q^(2*n) + (3*n^3 - (n - 1)^3)*q^(3*n) - n^3*q^(4*n) )/(1 - q^n)^4 - apply the operator x*d/dx three times to equation 5 in Arndt and then set x = 1. - Peter Bala, Jan 21 2021
a(n) = Sum_{1 <= i, j, k <= n} tau(gcd(i, j, k, n)) = Sum_{d divides n} tau(d)* J_3(n/d), where the divisor function tau(n) = A000005(n) and the Jordan totient function J_3(n) = A059376(n). - Peter Bala, Jan 22 2024

A007434 Jordan function J_2(n) (a generalization of phi(n)).

Original entry on oeis.org

1, 3, 8, 12, 24, 24, 48, 48, 72, 72, 120, 96, 168, 144, 192, 192, 288, 216, 360, 288, 384, 360, 528, 384, 600, 504, 648, 576, 840, 576, 960, 768, 960, 864, 1152, 864, 1368, 1080, 1344, 1152, 1680, 1152, 1848, 1440, 1728, 1584, 2208, 1536

Offset: 1

N. J. A. Sloane

Number of points in the bicyclic group Z/mZ X Z/mZ whose order is exactly m. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Mar 14 2006
Number of irreducible fractions among {(u+v*i)/n : 1 <= u, v <= n} with i = sqrt(-1), where a fraction (u+v*i)/n is called irreducible if and only if gcd(u, v, n) = 1. - Reinhard Zumkeller, Aug 20 2005
The weight of the n-th polynomial for the analog of cyclotomic polynomials for elliptic divisibility sequences. That is, let the weight of b1 = 1, b2 = 3, b3 = 8, b4 = 12 and let e1 = b1, e2 = b2*b1, e3 = b3*b1, e4 = b2*b4*b1, e5 = (b2^4*b4 - b3^3)*b1 = b5*e1, and so on, be an elliptic divisibility sequence. Then weight of e2 = 4, e3 = 9, e4 = 16, e5 = 25, where weight of en is n^2 in general, while weight of bn is a(n). - Michael Somos, Aug 12 2008
J_2(n) divides J_{2k}(n). J_2(n) gives the number of 2-tuples (x1,x2), such that 1 <= x1, x2 <= n and gcd(x1, x2, n) = 1. - Enrique Pérez Herrero, Mar 05 2011
From Jianing Song, Apr 06 2019: (Start)
Let k be any quadratic field such that all prime factors of n are inert in k, O_k be the corresponding ring of integers and G(n) = (O_k/nO_k)* be the multiplicative group of integers in O_k modulo n, then a(n) is the number of elements in G(n). The exponent of G(n) is A306933(n). [Equivalently, G(p^e) can be defined as (Z_{p^2}/p^eZ_{p^2})*, where Z_{p^2} is the ring of integers of the field Q_{p^2} (with a unique maximal ideal pZ_{p^2}), and Q_{p^2} is the unique unramified quadratic extension of the p-adic field Q_p. For the group structure of G(p^e), see A306933. - Jianing Song, Jun 19 2025]
For n >= 5, a(n) is divisible by 24. (End)
The Del Centina article on page 106 mentions a formula by Halphen denoted by phi(n)T(n). - Michael Somos, Feb 05 2021

			a(4) = 12 because the divisors of 4 being 1, 2, 4, we find that phi(1)*phi(4/1)*(4/1) = 8, phi(2)*phi(4/2)*(4/2) = 2, phi(4)*phi(4/4)*(4/4) = 2 and 8 + 2 + 2 = 12.
G.f. = x + 3*x^2 + 8*x^3 + 12*x^4 + 24*x^5 + 24*x^6 + 48*x^7 + 48*x^8 + 72*x^9 + ...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 199, #3.
A. Del Centina, Poncelet's porism: a long story of renewed discoveries, I, Hist. Exact Sci. (2016), v. 70, p. 106.
L. E. Dickson (1919, repr. 1971). History of the Theory of Numbers I. Chelsea. p. 147.
P. J. McCarthy, Introduction to Arithmetical Functions, Universitext, Springer, New York, NY, USA, 1986.
G. Pólya and G. Szegő, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part Eight, Chap. 1, Section 6, Problem 64.
M. Ram Murty (2001). Problems in Analytic Number Theory. Graduate Texts in Mathematics. 206. Springer-Verlag. p. 11.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1000
Sukumar Das Adhikari and A. Sankaranarayanan, On an error term related to the Jordan totient function Jk(n), Journal of Number Theory Volume 34, Issue 2, February 1990, Pages 178-188.
Dorin Andrica and Mihai Piticari, On Some Extensions Of Jordan's Arithmetic Functions, Proceedings of the International Conference on Theory and Applications of Mathematics and Informatics - ICTAMI 2003, Alba Iulia.
E. Artal Bartolo, P. D. González Pérez, M. González Villa, and E. León-Cardenal, On a suspension formula for Denef-Loeser zeta functions, arXiv:2502.05022 [math.AG], 2025. See p. 19.
Theo Douvropoulos, Joel Brewster Lewis, and Alejandro H. Morales, Hurwitz numbers for reflection groups III: Uniform formulas, arXiv:2308.04751 [math.CO], 2023, see p. 32.
F. A. Lewis and others, Problem 4002, Amer. Math. Monthly, Vol. 49, No. 9, Nov. 1942, pp. 618-619.
H. Li and T. MacHenry, Permanents and Determinants, Weighted Isobaric Polynomials, and Integer Sequences, J. Int. Seq. 16 (2013) #13.3.5, example 38.
MathOverflow, Averages of euler-phi function and similar.
Carl-Fredrik Nyberg-Brodda, On congruence subgroups of SL_2(Z[1/p]) generated by two parabolic elements, arXiv:2312.11258 [math.GR], 2023.
Nittiya Pabhapote and Vichian Laohakosol, Combinatorial Aspects of the Generalized Euler's Totient, International Journal of Mathematics and Mathematical Sciences, Volume 2010 (2010), Article ID 648165, 15 p.
Wolfgang Schramm, The Fourier transform of functions of the greatest common divisor, Electronic Journal of Combinatorial Number Theory A50 (8(1)), 2008.
N. J. A. Sloane, Transforms.
S. Thajoddin and S. Vangipuram, A Note On Jordan's Totient Function, Indian J. Pure Appl. Math, 1988.
László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.
Wikipedia, Jordan's totient function.
Index to divisibility sequences

Cf. A000056, A000290, A001065, A001615, A027750, A046970, A115000, A134675.
Cf. A059379 and A059380 (triangle of values of J_k(n)).
Cf. A000010 (J_1), this sequence (J_2), A059376 (J_3), A059377 (J_4), A059378 (J_5).
Cf. A002117, A088453, A301875, A301876, A321879 (partial sums).

a007434 n = sum $ zipWith3 (\x y z -> x * y * z)
                  tdivs (reverse tdivs) (reverse divs)
                  where divs = a027750_row n;  tdivs = map a000010 divs
-- Reinhard Zumkeller, Nov 24 2012

J := proc(n,k) local i,p,t1,t2; t1 := n^k; for p from 1 to n do if isprime(p) and n mod p = 0 then t1 := t1*(1-p^(-k)); fi; od; t1; end; # (with k = 2)
A007434 := proc(n)
    add(d^2*numtheory[mobius](n/d),d=numtheory[divisors](n)) ;
end proc: # R. J. Mathar, Nov 03 2015

jordanTotient[n_, k_:1] := DivisorSum[n, #^k*MoebiusMu[n/#] &] /; (n > 0) && IntegerQ[n]; Table[jordanTotient[n, 2], {n, 48}] (* Enrique Pérez Herrero, Sep 14 2010 *)
a[ n_] := If[ n < 1, 0, Sum[ d^2 MoebiusMu[ n/d], {d, Divisors @ n}]]; (* Michael Somos, Jan 11 2014 *)
a[ n_] := If[ n < 2, Boole[ n == 1], n^2 (Times @@ ((1 - 1/#[[1]]^2) & /@ FactorInteger @ n))]; (* Michael Somos, Jan 11 2014 *)
jordanTotient[n_Integer?Positive, r_:1] := DirichletConvolve[MoebiusMu[K], K^r, K, n]; Table[jordanTotient[n, 2], {n, 48}] (* Jan Mangaldan, Jun 03 2016 *)

{a(n) = if( n<1, 0, sumdiv(n, d, d^2 * moebius(n / d)))}; /* Michael Somos, Mar 20 2004 */

{a(n) = if( n<1, 0, direuler( p=2, n, (1 - X) / (1 - X*p^2))[n])}; /* Michael Somos, Jan 11 2014 */

seq(n) = dirmul(vector(n,k,k^2), vector(n,k,moebius(k)));
seq(48)  \\ Gheorghe Coserea, May 11 2016

jordan(n,k)=my(a=n^k);fordiv(n,i,if(isprime(i),a*=(1-1/(i^k))));a  \\ Roderick MacPhee, May 05 2017

from math import prod
from sympy import factorint
def A007434(n): return prod(p**(e-1<<1)*(p**2-1) for p, e in factorint(n).items()) # Chai Wah Wu, Jan 29 2024

Moebius transform of squares.
Multiplicative with a(p^e) = p^(2e) - p^(2e-2). - Vladeta Jovovic, Jul 26 2001
a(n) = Sum_{d|n} d^2 * mu(n/d). - Benoit Cloitre, Apr 05 2002
a(n) = n^2 * Product_{p|n} (1-1/p^2). - Tom Edgar, Jan 07 2015
a(n) = Sum_{d|n} phi(d)*phi(n/d)*n/d; Sum_{d|n} a(d) = n^2. - Reinhard Zumkeller, Aug 20 2005
Dirichlet generating function: zeta(s-2)/zeta(s). - Franklin T. Adams-Watters, Sep 11 2005
Dirichlet inverse of A046970. - Michael Somos, Jan 11 2014
a(n) = a(n^2)/n^2. - Enrique Pérez Herrero, Sep 14 2010
a(n) = A000010(n) * A001615(n).
If n > 1, then 1 > a(n)/n^2 > 1/zeta(2). - Enrique Pérez Herrero, Jul 14 2011
a(n) = Sum_{d|n} phi(n^2/d)*mu(d)^2. - Enrique Pérez Herrero, Jul 24 2012
a(n) = Sum_{k = 1..n} gcd(k, n)^2 * cos(2*Pi*k/n). - Enrique Pérez Herrero, Jan 18 2013
a(1) + a(2) + ... + a(n) ~ 1/(3*zeta(3))*n^3 + O(n^2). Lambert series Sum_{n >= 1} a(n)*x^n/(1 - x^n) = x*(1 + x)/(1 - x)^3. - Peter Bala, Dec 23 2013
n * a(n) = A000056(n). - Michael Somos, Mar 20 2004
a(n) = 24 * A115000(n) unless n < 5. - Michael Somos, Aug 12 2008
a(n) = A001065(n) - A134675(n). - Conjectured by John Mason and proved by Max Alekseyev, Jan 07 2015
a(n) = Sum_{k=1..n} gcd(n, k) * phi(gcd(n, k)), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 15 2018
G.f.: Sum_{k>=1} mu(k)*x^k*(1 + x^k)/(1 - x^k)^3. - Ilya Gutkovskiy, Oct 24 2018
Sum_{k>=1} 1/a(k) = Product_{primes p} (1 + p^2/(p^2 - 1)^2) = 1.81078147612156295224312590448625180897250361794500723589001447178002894356... - Vaclav Kotesovec, Sep 19 2020
Limit_{n->oo} (1/n) * Sum_{k=1..n} a(k)/k^2 = 1/zeta(3) (A088453). - Amiram Eldar, Oct 12 2020
From Richard L. Ollerton, May 09 2021: (Start)
a(n) = Sum_{k=1..n} (n/gcd(n,k))^2*mu(gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} gcd(n,k)^2*mu(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = Sum_{k=1..n} n*phi(gcd(n,k))/gcd(n,k).
a(n) = Sum_{k=1..n} phi(n*gcd(n,k))*mu(n/gcd(n,k))^2.
a(n) = Sum_{k=1..n} phi(n^2/gcd(n,k))*mu(gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
a(n) = Sum_{k = 1..n} phi(gcd(n, k)^2) = Sum_{d divides n} phi(d^2)*phi(n/d). - Peter Bala, Jan 17 2024
a(n) = Sum_{1 <= i, j <= n, lcm(i, j) = n} phi(i)*phi(j). See Tóth, p. 14. - Peter Bala, Jan 29 2024
Conjecture: a(n) = lim_{k->oo} (n^(2*(k + 1)))/A001157(n^k). - Velin Yanev, Dec 04 2024

Thanks to Michael Somos for catching an error in this sequence.

cp's OEIS Frontend

A000010 Euler totient function phi(n): count numbers <= n and prime to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Axiom

Haskell

Julia

Magma

Maple

Mathematica

Maxima

PARI

Python

Python

Sage

Sage

Formula

A003557 n divided by largest squarefree divisor of n; if n = Product p(k)^e(k) then a(n) = Product p(k)^(e(k)-1), with a(1) = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Julia

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Sage

Formula

Extensions

A000537 Sum of first n cubes; or n-th triangular number squared.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A001158 sigma_3(n): sum of cubes of divisors of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI