A173557 -id:A173557 - 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]

A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227

Offset: 1

N. J. A. Sloane

The term "prime power" is ambiguous. To a mathematician it means any number p^k, p prime, k >= 0, including p^0 = 1.
Any nonzero integer is a product of primes and units, where the units are +1 and -1. This is tied to the Fundamental Theorem of Arithmetic which proves that the factorizations are unique up to order and units. (So, since 1 = p^0 does not have a well defined prime base p, it is sometimes not regarded as a prime power. See A246655 for the sequence without 1.)
These numbers are (apart from 1) the numbers of elements in finite fields. - Franz Vrabec, Aug 11 2004
Numbers whose divisors form a geometrical progression. The divisors of p^k are 1, p, p^2, p^3, ..., p^k. - Amarnath Murthy, Jan 09 2002
These are also precisely the orders of those finite affine planes that are known to exist as of today. (The order of a finite affine plane is the number of points in an arbitrarily chosen line of that plane. This number is unique for all lines comprise the same number of points.) - Peter C. Heinig (algorithms(AT)gmx.de), Aug 09 2006
Except for first term, the index of the second number divisible by n in A002378, if the index equals n. - Mats Granvik, Nov 18 2007
These are precisely the numbers such that lcm(1,...,m-1) < lcm(1,...,m) (=A003418(m) for m>0; here for m=1, the l.h.s. is taken to be 0). We have a(n+1)=a(n)+1 if a(n) is a Mersenne prime or a(n)+1 is a Fermat prime; the converse is true except for n=7 (from Catalan's conjecture) and n=1, since 2^1-1 and 2^0+1 are not considered as Mersenne resp. Fermat prime. - M. F. Hasler, Jan 18 2007, Apr 18 2010
The sequence is A000015 without repetitions, or more formally, A000961=Union[A000015]. - Zak Seidov, Feb 06 2008
Except for a(1)=1, indices for which the cyclotomic polynomial Phi[k] yields a prime at x=1, cf. A020500. - M. F. Hasler, Apr 04 2008
Also, {A138929(k) ; k>1} = {2*A000961(k) ; k>1} = {4,6,8,10,14,16,18,22,26,32,34,38,46,50,54,58,62,64,74,82,86,94,98,...} are exactly the indices for which Phi[k](-1) is prime. - M. F. Hasler, Apr 04 2008
A143201(a(n)) = 1. - Reinhard Zumkeller, Aug 12 2008
Number of distinct primes dividing n=omega(n) < 2. - Juri-Stepan Gerasimov, Oct 30 2009
Numbers n such that Sum_{p-1|p is prime and divisor of n} = Product_{p-1|p is prime and divisor of n}. A055631(n) = A173557(n-1). - Juri-Stepan Gerasimov, Dec 09 2009, Mar 10 2010
Numbers n such that A028236(n) = 1. Klaus Brockhaus, Nov 06 2010
A188666(k) = a(k+1) for k: 2*a(k) <= k < 2*a(k+1), k > 0; notably a(n+1) = A188666(2*a(n)). - Reinhard Zumkeller, Apr 25 2011
A003415(a(n)) = A192015(n); A068346(a(n)) = A192016(n); a(n)=A192134(n) + A192015(n). - Reinhard Zumkeller, Jun 26 2011
A089233(a(n)) = 0. - Reinhard Zumkeller, Sep 04 2013
The positive integers n such that every element of the symmetric group S_n which has order n is an n-cycle. - W. Edwin Clark, Aug 05 2014
Conjecture: these are numbers m such that Sum_{k=0..m-1} k^phi(m) == phi(m) (mod m), where phi(m) = A000010(m). - Thomas Ordowski and Giovanni Resta, Jul 25 2018
Numbers whose (increasingly ordered) divisors are alternatingly squares and nonsquares. - Michel Marcus, Jan 16 2019
Possible numbers of elements in a finite vector space. - Jianing Song, Apr 22 2021

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 870.
M. Koecher and A. Krieg, Ebene Geometrie, Springer, 1993.
R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications, Cambridge 1986, Theorem 2.5, p. 45.
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).

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 [alternative scanned copy].
Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, and Tony W. H. Wong, A further investigation on covering systems with odd moduli, arXiv:2507.16135 [math.NT], 2025. See p. 3.
Brady Haran and Günter Ziegler, Cannons and Sparrows, Numberphile video (2018).
Laurentiu Panaitopol, Some of the properties of the sequence of powers of prime numbers, Rocky Mountain Journal of Mathematics, Volume 31, Number 4, Winter 2001.
Eric Weisstein's World of Mathematics, Prime Power
Eric Weisstein's World of Mathematics, Projective Plane
Index entries for "core" sequences

There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018
Cf. A008480, A010055, A065515, A095874, A025473.
Cf. indices of record values of A003418; A000668 and A019434 give a member of twin pairs a(n+1)=a(n)+1.
A138929(n) = 2*a(n).
Cf. A000040, A001221, A001477. - Juri-Stepan Gerasimov, Dec 09 2009
A028236 (if n = Product (p_j^k_j), a(n) = numerator of Sum 1/p_j^k_j). - Klaus Brockhaus, Nov 06 2010
A000015(n) = Min{term : >= n}; A031218(n) = Max{term : <= n}.
Complementary (in the positive integers) to sequence A024619. - Jason Kimberley, Nov 10 2015

import Data.Set (singleton, deleteFindMin, insert)
a000961 n = a000961_list !! (n-1)
a000961_list = 1 : g (singleton 2) (tail a000040_list) where
g s (p:ps) = m : g (insert (m * a020639 m) $ insert p s') ps
where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, May 01 2012, Apr 25 2011

[1] cat [ n : n in [2..250] | IsPrimePower(n) ]; // corrected by Arkadiusz Wesolowski, Jul 20 2012

readlib(ifactors): for n from 1 to 250 do if nops(ifactors(n)[2])=1 then printf(`%d,`,n) fi: od:
# second Maple program:
a:= proc(n) option remember; local k; for k from
      1+a(n-1) while nops(ifactors(k)[2])>1 do od; k
    end: a(1):=1: A000961:= a:
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 08 2013

Select[ Range[ 2, 250 ], Mod[ #, # - EulerPhi[ # ] ] == 0 & ]
Select[ Range[ 2, 250 ], Length[FactorInteger[ # ] ] == 1 & ]
max = 0; a = {}; Do[m = FactorInteger[n]; w = Sum[m[[k]][[1]]^m[[k]][[2]], {k, 1, Length[m]}]; If[w > max, AppendTo[a, n]; max = w], {n, 1, 1000}]; a (* Artur Jasinski *)
Join[{1}, Select[Range[2, 250], PrimePowerQ]] (* Jean-François Alcover, Jul 07 2015 *)

A000961(n,l=-1,k=0)=until(n--<1,until(lA000961(lim=999,l=-1)=for(k=1,lim, l==lcm(l,k) && next; l=lcm(l,k); print1(k,",")) \\ M. F. Hasler, Jan 18 2007

isA000961(n) = (omega(n) == 1 || n == 1) \\ Michael B. Porter, Sep 23 2009

nextA000961(n)=my(m,r,p);m=2*n;for(e=1,ceil(log(n+0.01)/log(2)),r=(n+0.01)^(1/e);p=prime(primepi(r)+1);m=min(m,p^e));m \\ Michael B. Porter, Nov 02 2009

is(n)=isprimepower(n) || n==1 \\ Charles R Greathouse IV, Nov 20 2012

list(lim)=my(v=primes(primepi(lim)),u=List([1])); forprime(p=2,sqrtint(lim\1),for(e=2,log(lim+.5)\log(p),listput(u,p^e))); vecsort(concat(v,Vec(u))) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import primerange
def A000961_list(limit): # following Python style, list terms < limit
    L = [1]
    for p in primerange(1, limit):
        pe = p
        while pe < limit:
            L.append(pe)
            pe *= p
    return sorted(L) # Chai Wah Wu, Sep 08 2014, edited by M. F. Hasler, Jun 16 2022

from sympy import primepi
from sympy.ntheory.primetest import integer_nthroot
def A000961(n):
    def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return m # Chai Wah Wu, Jul 23 2024

def A000961_list(n):
    R = [1]
    for i in (2..n):
        if i.is_prime_power(): R.append(i)
    return R
A000961_list(227) # Peter Luschny, Feb 07 2012

a(n) = A025473(n)^A025474(n). - David Wasserman, Feb 16 2006
a(n) = A117331(A117333(n)). - Reinhard Zumkeller, Mar 08 2006
Panaitopol (2001) gives many properties, inequalities and asymptotics, including a(n) ~ prime(n). - N. J. A. Sloane, Oct 31 2014, corrected by M. F. Hasler, Jun 12 2023 [The reference gives pi*(x) = pi(x) + pi(sqrt(x)) + ... where pi*(x) counts the terms up to x, so it is the inverse function to a(n).]
m=a(n) for some n <=> lcm(1,...,m-1) < lcm(1,...,m), where lcm(1...0):=0 as to include a(1)=1. a(n+1)=a(n)+1 <=> a(n+1)=A019434(k) or a(n)=A000668(k) for some k (by Catalan's conjecture), except for n=1 and n=7. - M. F. Hasler, Jan 18 2007, Apr 18 2010
A001221(a(n)) < 2. - Juri-Stepan Gerasimov, Oct 30 2009
A008480(a(n)) = 1 for all n >= 1. - Alois P. Heinz, May 26 2018
Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + 1 + A077761 + A136141. - François Huppé, Jul 31 2024

Description modified by Ralf Stephan, Aug 29 2014

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

A023900 Dirichlet inverse of Euler totient function (A000010).

Original entry on oeis.org

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

Offset: 1

Olivier Gérard

Also called reciprocity balance of n.
Apart from different signs, same as Sum_{d divides n} core(d)*mu(n/d), where core(d) (A007913) is the squarefree part of d. - Benoit Cloitre, Apr 06 2002
Main diagonal of A191898. - Mats Granvik, Jun 19 2011

			x - x^2 - 2*x^3 - x^4 - 4*x^5 + 2*x^6 - 6*x^7 - x^8 - 2*x^9 + 4*x^10 - ...

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 37.
D. M. Burton, Elementary Number Theory, Allyn and Bacon Inc. Boston, MA, 1976, p. 125.

Antti Karttunen, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
G. P. Brown, Some comments on inverse arithmetic functions, Math. Gaz. 89 (516) (2005) 403-408.
K. Dohmen and M. Trinks, An Abstraction of Whitney's Broken Circuit Theorem, arXiv preprint arXiv:1404.5480 [math.CO], 2014.
R. Kemp, On the number of words in the language {w in Sigma* | w = w^R }^2, Discrete Math., 40 (1982), 225-234.
Paul W. Oxby, A Function Based on Chebyshev Polynomials as an Alternative to the Sinc Function in FIR Filter Design, arXiv:2011.10546 [eess.SP], 2020.
László Tóth, Multiplicative arithmetic functions of several variables: a survey, arXiv preprint arXiv:1310.7053 [math.NT], 2013.

Cf. A000010, A007913, A023898, A117209, A134842.
Moebius transform is A055615.
Cf. A027748, A173557 (gives the absolute values), A295876.
Cf. A253905 (Dgf at s=3).

a023900 1 = 1
a023900 n = product $ map (1 -) $ a027748_row n
-- Reinhard Zumkeller, Jun 01 2015

A023900 := n -> mul(1-i,i=numtheory[factorset](n)); # Peter Luschny, Oct 26 2010

a[ n_] := If[ n < 1, 0, Sum[ d MoebiusMu @ d, { d, Divisors[n]}]] (* Michael Somos, Jul 18 2011 *)
Array[ Function[ n, 1/Plus @@ Map[ #*MoebiusMu[ # ]/EulerPhi[ # ]&, Divisors[ n ] ] ], 90 ]
nmax = 81; Drop[ CoefficientList[ Series[ Sum[ MoebiusMu[k] k x^k/(1 - x^k), {k, 1, nmax} ], {x, 0, nmax} ], x ], 1 ] (* Stuart Clary, Apr 15 2006 *)
t[n_, 1] = 1; t[1, k_] = 1; t[n_, k_] :=  t[n, k] = If[n < k, If[n > 1 && k > 1, Sum[-t[k - i, n], {i, 1, n - 1}], 0], If[n > 1 && k > 1, Sum[-t[n - i, k], {i, 1, k - 1}], 0]]; Table[t[n, n], {n, 36}] (* Mats Granvik, Robert G. Wilson v, Jun 25 2011 *)
Table[DivisorSum[m, # MoebiusMu[#] &], {m, 90}] (* Jan Mangaldan, Mar 15 2013 *)
f[p_, e_] := (1 - p); a[1] = 1; a[n_] := Times @@ (f @@@ FactorInteger[n]); Array[a, 100] (* Amiram Eldar, Oct 14 2020 *)

{a(n) = direuler( p=2, n, (1 - p*X) / (1 - X))[n]}

{a(n) = if( n<1, 0, sumdiv( n, d, d * moebius(d)))} /* Michael Somos, Jul 18 2011 */

a(n)=sumdivmult(n,d, d*moebius(d)) \\ Charles R Greathouse IV, Sep 09 2014

from sympy import divisors, mobius
def a(n): return sum([d*mobius(d) for d in divisors(n)]) # Indranil Ghosh, Apr 29 2017

from math import prod
from sympy import primefactors
def A023900(n): return prod(1-p for p in primefactors(n)) # Chai Wah Wu, Sep 08 2023

;; With memoization-macro definec.
(definec (A023900 n) (if (= 1 n) 1 (* (- 1 (A020639 n)) (A023900 (A028234 n))))) ;; Antti Karttunen, Nov 28 2017

a(n) = Sum_{ d divides n } d*mu(d) = Product_{p|n} (1-p).
a(n) = 1 / (Sum_{ d divides n } mu(d)*d/phi(d)).
Dirichlet g.f.: zeta(s)/zeta(s-1). - Michael Somos, Jun 04 2000
a(n+1) = det(n+1)/det(n) where det(n) is the determinant of the n X n matrix M_(i, j) = i/gcd(i, j) = lcm(i, j)/j. - Benoit Cloitre, Aug 19 2003
a(n) = phi(n)*moebius(A007947(n))*A007947(n)/n. Logarithmic g.f.: Sum_{n >= 1} a(n)*x^n/n = log(F(x)) where F(x) is the g.f. of A117209 and satisfies: 1/(1-x) = Product_{n >= 1} F(x^n). - Paul D. Hanna, Mar 03 2006
G.f.: A(x) = Sum_{k >= 1} mu(k) k x^k/(1 - x^k) where mu(k) is the Moebius (Mobius) function, A008683. - Stuart Clary, Apr 15 2006
G.f.: A(x) is x times the logarithmic derivative of A117209(x). - Stuart Clary, Apr 15 2006
Row sums of triangle A134842. - Gary W. Adamson, Nov 12 2007
G.f.: x/(1-x) = Sum_{n >= 1} a(n)*x^n/(1-x^n)^2. - Paul D. Hanna, Aug 16 2008
a(n) = phi(rad(n)) *(-1)^omega(n) = A000010(A007947(n)) *(-1)^A001221(n). - Enrique Pérez Herrero, Aug 24 2010
a(n) = Product_{i = 2..n} (1-i)^( (pi(i)-pi(i-1)) * floor( (cos(n*Pi/i))^2 ) ), where pi = A000720, Pi = A000796. - Wesley Ivan Hurt, May 24 2013
a(n) = -limit of zeta(s)*(Sum_{d divides n} moebius(d)/exp(d)^(s-1)) as s->1 for n>1. - Mats Granvik, Jul 31 2013
a(n) = Sum_{d divides n} mu(d)*rad(d), where rad is A007947. - Enrique Pérez Herrero, May 29 2014
Conjecture for n>1: Let n = 2^(A007814(n))*m = 2^(ruler(n))*odd_part(n), where m = A000265(n), then a(n) = (-1)^(m=n)*(0+Sum_{i=1..m and gcd(i,m)=1} (4*min(i,m-i)-m)) = (-1)^(m1} (4*min(i,m-i)-m)). - I. V. Serov, May 02 2017
a(n) = (-1)^A001221(n) * A173557(n). - R. J. Mathar, Nov 02 2017
a(1) = 1; for n > 1, a(n) = (1-A020639(n)) * a(A028234(n)), because multiplicative with a(p^e) = (1-p). - Antti Karttunen, Nov 28 2017
a(n) = 1 - Sum_{d|n, d > 1} d*a(n/d). - Ilya Gutkovskiy, Apr 26 2019
From Richard L. Ollerton, May 07 2021: (Start)
For n>1, Sum_{k=1..n} a(gcd(n,k)) = 0.
For n>1, Sum_{k=1..n} a(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)) = 0. (End)
a(n) = rad(n)*(-1)^omega(n)*phi(n)/n = A062953(n)*A000010(n)/n. - Amrit Awasthi, Jan 30 2022
a(n) = mu(n)*phi(n) = A008683(n)*A000010(n) whenever n is squarefree. - Amrit Awasthi, Feb 03 2022
From Peter Bala, Jan 24 2024: (Start)
a(n) = Sum_{d divides n} core(d)*mu(d). Cf. Comment by Benoit Cloitre, dated Apr 06 2002.
a(n) = Sum_{d|n, e|n}  n/gcd(d, e) * mu(n/d) * mu(n/e) (the sum is a multiplicative function of n by Tóth, and takes the value 1 - p for n = p^e, a prime power). (End)
From Peter Bala, Feb 01 2024: (Start)
G.f. Sum_{n >= 1} (2*n-1)*moebius(2*n-1)*x^(2*n-1)/(1 + x^(2n-1)).
a(n) = (-1)^(n+1) * Sum_{d divides n, d odd} d*moebius(d). (End)

A002618 a(n) = n*phi(n).

Original entry on oeis.org

1, 2, 6, 8, 20, 12, 42, 32, 54, 40, 110, 48, 156, 84, 120, 128, 272, 108, 342, 160, 252, 220, 506, 192, 500, 312, 486, 336, 812, 240, 930, 512, 660, 544, 840, 432, 1332, 684, 936, 640, 1640, 504, 1806, 880, 1080, 1012, 2162, 768, 2058, 1000

Offset: 1

N. J. A. Sloane

Also Euler phi function of n^2.
For n >= 3, a(n) is also the size of the automorphism group of the dihedral group of order 2n. This automorphism group is isomorphic to the group of transformations x -> ax + b, where a, b and x are integers modulo n and a is coprime to n. Its order is n*phi(n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 18 2001
Order of metacyclic group of polynomial of degree n. - Artur Jasinski, Jan 22 2008
It appears that this sequence gives the number of permutations of 1, 2, 3, ..., n that are arithmetic progressions modulo n. - John W. Layman, Aug 27 2008
The conjecture by Layman is correct. Obviously any such permutation must have an increment that is prime to n, and almost as obvious that any such increment will work, with any starting value; hence phi(n) * n total. - Franklin T. Adams-Watters, Jun 09 2009
Consider the numbers from 1 to n^2 written line by line as an n X n square: a(n) = number of numbers that are coprime to all their horizontal and vertical immediate neighbors. - Reinhard Zumkeller, Apr 12 2011
n -> a(n) is injective: a(m) = a(n) implies m = n. - Franz Vrabec, Dec 12 2012 (See Mathematics Stack Exchange link for a proof.)
a(p) = p*(p-1) a pronic number, see A036689 and A002378. - Fred Daniel Kline, Mar 30 2015
Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015
From Jianing Song, Aug 25 2023: (Start)
a(n) is the order of the holomorph (see the Wikipedia link) of the cyclic group of order n. Note that Hol(C_n) and Aut(D_{2n}) are isomorphic unless n = 2, where D_{2n} is the dihedral group of order 2*n. See the Wordpress link.
The odd-indexed terms form a subsequence of A341298: the holomorph of an abelian group of odd order is a complete group. See Theorem 3.2, Page 618 of the W. Peremans link. (End)

			a(4) = 8 since phi(4) = 2 and 4 * 2 = 8.
a(5) = 20 since phi(5) = 4 and 5 * 4 = 20.

Peter Giblin, Primes and Programming: An Introduction to Number Theory with Computing. Cambridge: Cambridge University Press (1993) p. 116, Exercise 1.10.
J. L. Lagrange, Oeuvres, Vol. III Paris 1869.
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).

Michael De Vlieger, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Daniel Fischer, answer to Injectivity of the function n times the Euler Totient of n, Mathematics Stack Exchange, October 2013.
Mikhail R. Gabdullin and Vitalii V. Iudelevich, Numbers of the form kf(k), arXiv:2201.09287 [math.NT] (2022).
Dmitry Krachun and Zhi-Wei Sun, Each positive rational number has the form phi(m^2)/phi(n^2), arXiv:2001.03736 [math.HO], 2020. See also The American Mathematical Monthly (2020) Vol. 127, Issue 9, 847-849.
F. Luca and A. O. Munagi, The number of permutations which form arithmetic progressions modulo m, Annals of the Alexandru Ioan Cuza University, 2014, DOI: 10.2478/aicu-2014-0053. [Broken link]
C. L. Mallows and N. J. A. Sloane, Notes on A002618, A002619, etc.
W. Peremans, Completeness of Holomorphs, Nederl. Akad. Wetensch. Indag. Math. Proc. Ser. A, 60. (1957) 608-619.
N. J. A. Sloane, Notes on A002618, A002619, etc.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61.
J. E. A. Steggall, On the numbers of patterns which can be derived from certain elements, Mess. Math., 37 (1907), 56-61. [Annotated scanned copy. Note that the scanned pages are out of order]
Wikipedia, Holomorph.
Wordpress, Automorphisms of dihedral groups.

First column of A047916.
Cf. A002619, A011755 (partial sums), A047918, A000010, A053650, A053191, A053192, A036689, A058161, A009262, A082473 (same terms, sorted into ascending order), A256545, A327172 (a left inverse), A327173, A065484.
Subsequence of A323333.

a002618 n = a000010 n * n  -- Reinhard Zumkeller, Dec 21 2012

[n*EulerPhi(n): n in [1..150]]; // Vincenzo Librandi, Apr 04 2011

with(numtheory):a:=n->phi(n^2): seq(a(n), n=1..50); # Zerinvary Lajos, Oct 07 2007

Table[n EulerPhi[n], {n, 100}] (* Artur Jasinski, Jan 22 2008 *)

numlib::phi(n^2)$ n=1..81 // Zerinvary Lajos, May 13 2008

a(n)=n*eulerphi(n) \\ Charles R Greathouse IV, Nov 20 2012

from sympy import totient as phi
def a(n): return n*phi(n)
print([a(n) for n in range(1, 51)]) # Michael S. Branicky, Mar 16 2022

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

Multiplicative with a(p^e) = (p-1)*p^(2e-1). - David W. Wilson, Aug 01 2001
Dirichlet g.f.: zeta(s-2)/zeta(s-1). - R. J. Mathar, Feb 09 2011
a(n) = A173557(n) * A102631(n). - R. J. Mathar, Mar 30 2011
From Wolfdieter Lang, May 12 2011: (Start)
a(n)/2 = A023896(n), n >= 2.
a(n)/2 = (1/n) * Sum_{k=1..n-1, gcd(k,n)=1} k, n >= 2 (see A023896 and A076512/A109395). (End)
a(n) = lcm(phi(n^2),n). - Enrique Pérez Herrero, May 11 2012
a(n) = phi(n^2). - Wesley Ivan Hurt, Jun 16 2013
a(n) = A009195(n) * A009262(n). - Michel Marcus, Oct 24 2013
G.f.: -x + 2*Sum_{k>=1} mu(k)*k*x^k/(1 - x^k)^3. - Ilya Gutkovskiy, Jan 03 2017
a(n) = A082473(A327173(n)), A327172(a(n)) = n. -- Antti Karttunen, Sep 29 2019
Sum_{n>=1} 1/a(n) = 2.203856... (A065484). - Amiram Eldar, Sep 30 2019
Define f(x) = #{n <= x: a(n) <= x}. Gabdullin & Iudelevich show that f(x) ~ c*sqrt(x) for c = Product_{p prime} (1 + 1/(p*(p - 1 + sqrt(p^2 - p)))) = 1.3651304521525857... - Charles R Greathouse IV, Mar 16 2022
a(n) = Sum_{d divides n} A001157(d)*A046692(n/d); that is, the Dirichlet convolution of sigma_2(n) and the Dirichlet inverse of sigma_1(n). - Peter Bala, Jan 26 2024

Better description from Labos Elemer, Feb 18 2000

A191898 Symmetric square array read by antidiagonals: T(n,1)=1, T(1,k)=1, T(n,k) = -Sum_{i=1..k-1} T(n-i,k) for n >= k, -Sum_{i=1..n-1} T(k-i,n) for n < k.

Original entry on oeis.org

1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, -2, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, 1, 1, 1, -2, 1, 1, -2, 1, 1, 1, -1, 1, -1, -4, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -2, -1, 1, 2, 1, -1, -2, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, 1, -1, -6, -1, 1, -1, 1, -1, 1

Offset: 1

Mats Granvik, Jun 19 2011

Rows equal columns and are periodic. No zero elements are found (conjecture). The recurrence is related to the recurrence for the Mahonian numbers. The main diagonal is the Dirichlet inverse of the Euler totient function A023900 (conjecture). [The 2nd and 3rd formulas state that the conjecture is correct. R. J. Mathar, Sep 16 2017]
The sums from n=1 to infinity of T(n,k)/n converge to the Mangoldt function for column k (conjecture).
If gcd(n,k)=1 then T(n,k)=1 and if T(n,k)=1 then gcd(n,k)=1 (conjecture).
The Dirichlet generating functions for s > 1 for the columns appear to be (see A054535):
Zeta(s)*(1 + (Sum over all possible combinations of products of negative distinct prime factors of k, up to rearrangement, 1/((-1* first distinct prime factor)*(-1*second distinct prime factor)*(-1*third distinct prime factor * ...))^(s-1))).
Examples:
k=1: Zeta(s)
k=2: Zeta(s)*(1 - 1/2^(s-1))
k=3: Zeta(s)*(1 - 1/3^(s-1))
k=4: Zeta(s)*(1 - 1/2^(s-1))
k=5: Zeta(s)*(1 - 1/5^(s-1))
k=6: Zeta(s)*(1 - 1/2^(s-1) - 1/3^(s-1) + 1/6^(s-1))
k=7: Zeta(s)*(1 - 1/7^(s-1))
...
k=30: Zeta(s)*(1 - 1/2^(s-1) - 1/3^(s-1) - 1/5^(s-1) + 1/6^(s-1) + 1/10^(s-1) + 1/15^(s-1) - 1/30^(s-1))
...
(conjecture)
See triangle A142971 for negative distinct prime factors.
This could probably be checked by matrix multiplication.
The signs of the eigenvalues of this matrix are a rearrangement of the Mobius function A008683 (conjecture). The first few eigenvalues are:
{1.0000}
{-1.4142, 1.4142}
{-2.6554, 1.8662, -1.2108}
{-3.4393, 2.1004, -1.6611, 0}
{-4.7711, -3.3867, 2.5910, -1.4332, 0}
{-5.2439, -3.4641, 3.4641, 2.5169, -2.2730, 0}
The relation to Dirichlet characters for the entries in this matrix appears appears to be formulated in terms of the sequence A089026 which is equal to n if n is a prime, otherwise equal to 1. See Mathematica program below. [Mats Granvik, Nov 23 2013]
From Mats Granvik, Jun 19 2016: (Start)
Remark about the Dirichlet generating function for the whole matrix: Subtracting the first column (in the form of zeta(c)) of the matrix gives us the limit: lim_{c->1} zeta(s)*zeta(c)/zeta(c+s-1)-zeta(c) = -zeta'(s)/zeta(s) which is the classical Dirichlet generating function for the von Mangoldt function.
For n >= k, see A231425, this matrix has row sums equal to zero except for the first row:
1=1
1-1=0
1+1-2=0
1-1+1-1=0
1+1+1+1-4=0
...
log(A014963(n)) = Sum_{k>=1} A191898(n,k)/k, for n>1.
log(A014963(k)) = Sum_{n>=1} A191898(n,k)/n, for k>1.
log(A014963(n)) = limit of zeta(s)*(Sum_{d divides n} A008683(d)/d^(s-1)) as s->1, for n>1.
A008683(n) = Sum_{k=1..n} A191898(n,k)*exp(-i*2*Pi*k/n)/n.
A008683(n) = Sum_{n=1..k} A191898(n,k)*exp(-i*2*Pi*n/k)/k.
(End)
From Mats Granvik, Aug 09 2016: (Start)
The Dirichlet generating function for the matrix is zero for any pair c and s = 2 - c and any pair s and c = 2 - s  except at the pole c = 1 and s = 1 where it is indeterminate.
In the Mathematica program section, in the expression for the matrix as Dirichlets characters, the variables s and c can apparently be any pair of positive integers.
Limits related to the Dirichlet generating function for the matrix: Let s = ZetaZero(n), then lim_{c->1} zeta(s*c)/zeta(c+s-1) = ZetaZero(n). Let s = ZetaZero(n), then lim_{c->1} zeta(s*c)/zeta(c+s*c-1) = ZetaZero(n)/(1+ZetaZero(n)).
(End)

			Array starts:
n\k | 1    2    3    4    5    6    7    8    9   10
----+-----------------------------------------------------
1   | 1,   1,   1,   1,   1,   1,   1,   1,   1,   1, ...
2   | 1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1, ...
3   | 1,   1,  -2,   1,   1,  -2,   1,   1,  -2,   1, ...
4   | 1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1, ...
5   | 1,   1,   1,   1,  -4,   1,   1,   1,   1,  -4, ...
6   | 1,  -1,  -2,  -1,   1,   2,   1,  -1,  -2,  -1, ...
7   | 1,   1,   1,   1,   1,   1,  -6,   1,   1,   1, ...
8   | 1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1, ...
9   | 1,   1,  -2,   1,   1,  -2,   1,   1,  -2,   1, ...
10  | 1,  -1,   1,  -1,  -4,  -1,   1,  -1,   1,   4, ...

Antti Karttunen, Table of n, a(n) for n = 1..22155; the first 210 antidiagonals of the array
Mats Granvik, Is this similarity to the Fourier transform of the von Mangoldt function real?
Mats Granvik, Is this Riemann zeta function product equal to the Fourier transform of the von Mangoldt function?
Mats Granvik, Primes approximated by eigenvalues?
Mats Granvik, Are the primes found as a subset in this sequence a(n)?
Mats Granvik, Will every eigenvalue in this type of matrix eventually be a common eigenvalue to infinitely many subsequent larger matrices of the same form?
Mats Granvik, How write Dirichlet character sums for the terms of the von Mangoldt function?
Mats Granvik, Do these series converge to the von Mangoldt function?
Mats Granvik, Is this sum equal to the Möbius function?
Mats Granvik, Can the Riemann hypothesis be relaxed to say that this matrix A consists of square roots?
Mats Granvik, Elementary proof of the prime number theorem?
Mats Granvik, Is this Dirichlet series generating function of the von Mangoldt function matrix correct?
Mats Granvik, Question about ratios of polynomials evaluated at x=1

Cf. A023900, A014963, A008302, A033999, A061347, A142971.
Cf. A007917, A199514, A260237. - Mats Granvik, Jun 19 2016
Cf. A343555, A343556.

T[ n_, k_] := T[ n, k] = Which[ n < 1 || k < 1, 0, n == 1 || k == 1, 1, k > n, T[k, n], n > k,T[k, Mod[n, k, 1]], True, -Sum[ T[n, i], {i, n - 1}]]; (* Michael Somos, Jul 18 2011 *)
(* Conjectured expression for the matrix as Dirichlet characters *) s = RandomInteger[{1, 3}]; c = RandomInteger[{1, 3}]; nn = 12; b = Table[Exp[MangoldtLambda[Divisors[n]]]^-MoebiusMu[Divisors[n]], {n, 1, nn^Max[s, c]}]; j = 1; MatrixForm[Table[Table[Product[(b[[n^s]][[m]]*DirichletCharacter[b[[n^s]][[m]], j, k^c] - (b[[n^s]][[m]] - 1)), {m, 1, Length[Divisors[n]]}], {n, 1, nn}], {k, 1, nn}]] (* Mats Granvik, Nov 23 2013 and Aug 09 2016 *)

{T(n, k) = if( n<1 || k<1, 0, n==1 || k==1, 1, k>n, T(k, n), kMichael Somos, Jul 18 2011 */

from sympy.core.cache import cacheit
@cacheit
def T(n, k): return 0 if n<1 or k<1 else 1 if n==1 or k==1 else T(k, n) if k>n else T(k, (n - 1)%k + 1) if n>k else -sum([T(n, i) for i in range(1, n)])
for n in range(1, 21): print([T(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Oct 23 2017

T(n,1)=1, T(1,k)=1, n>=k: -Sum_{i=1..k-1} T(n-i,k), n

T(n, n) = A023900(n). - Michael Somos, Jul 18 2011

T(n, k) = A023900(gcd(n,k)). - Mats Granvik, Jun 18 2012

Dirichlet generating function for sequence in the n-th row: zeta(s)*Sum_{ d divides n } mu(d)/d^(s-1). - Mats Granvik, Jun 18 2012 & Jun 19 2016

From Mats Granvik, Jun 19 2016: (Start)

Dirichlet generating function for the whole matrix: Sum_{k>=1} (Sum_{n>=1} T(n,k)/(n^c*k^s)) = Sum_{n>=1} (zeta(s)*Sum_{ d divides n } mu(d)/d^(s-1))/n^c = zeta(s)*zeta(c)/zeta( c + s - 1 ).

T(n,k) = A127093(n,k)^(1/2-i*a(k))*transpose(A008683(k)*(A127093(n,k)^(1/2+i*a(n)))) where a(x) is some real number. An example would be T(n,k) = A127093(n,k)^(zetazero(k))*transpose(A008683(k)*(A127093(n,k)^(zetazero(-k)))) but this is of course not special for only the zeta zeros.

Recurrence for a subset of A191898 that is a cross-directional variant of the recurrence in A051731: T(1,1)=1, T(1,2..k)=0, T(2..n,1)=0, n >= k: -Sum_{i=1..k-1} T(n-i,k) - T(n-i,k-1), n < k: -Sum_{i=1..n-1} T(k-i,n) - T(k-i,n-1). Notice that the identity matrix in linear algebra satisfies a similar recurrence:

T(1,1)=1, T(1,2..k)=0, T(2..n,1)=0, n >= k: -Sum_{i=1..n-1} T(n-i,k) - T(n-i,k-1), n < k: -Sum_{i=1..k-1} T(k-i,n) - T(k-i,n-1).

(End)

This array equals A051731*transpose(A143256). - Mats Granvik, Jul 22 2016

T(n,k) = sqrt(A143256(n,k))*transpose(sqrt(A143256(n,k))). - Mats Granvik, Aug 10 2018

Dirichlet generating function for absolute values: Sum_{k>=1} (Sum_{n>=1} abs(T(n,k))/(n^c*k^s)) = zeta(s)*zeta(c)*zeta(s + c - 1)/zeta(2*(s + c - 1))*Product_{k>=1} (1 - 2/(prime(k) + prime(k)^(s + c))). After Vaclav Kotesovec in A173557. - Mats Granvik, Apr 25 2021

A062570 a(n) = phi(2*n).

Original entry on oeis.org

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

Offset: 1

Jason Earls, Jul 03 2001

a(n) is also the number of non-congruent solutions to x^2 - y^2 == 1 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003
a(n) is the size of a square companion matrix of the minimal cyclotomic polynomial of (-1)^(1/n). - Eric Desbiaux, Dec 08 2015
a(n) is the degree of the (2n)-th cyclotomic field Q(zeta_(2n)). Note that Q(zeta_n) = Q(zeta_(2n)) for odd n. - Jianing Song, May 17 2021
The number of integers k from 1 to n such that gcd(n,k) is a power of 2. - Amiram Eldar, May 18 2025

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 28.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from Vincenzo Librandi)
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).
László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
Wikipedia, Ramanujan's sum.

Cf. A000010, A000034, A008683, A037225, A060968, A062803, A185199, A209229.
Column 1 of A129559, column 2 of A372673.
Row 1 of A379010.
Row sums of A129558 and of A129564.

[phi(2*n)$n=1..80]; # Muniru A Asiru, Mar 18 2019

Table[EulerPhi[2 n], {n, 80}] (* Vincenzo Librandi, Aug 23 2013 *)

PARI
```
a(n) = eulerphi(2*n)
```

from sympy import totient
def A062570(n): return totient(n) if n&1 else totient(n)<<1 # Chai Wah Wu, Aug 04 2024

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

a(n) = Sum_{d|n and d is odd} n/d*mu(d).
Multiplicative with a(2^e) = 2^e and a(p^e) = p^e-p^(e-1), p>2.
Dirichlet g.f.: zeta(s-1)/zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
a(n) = A000010(2*n).
a(n) = phi(n)*(1+((n+1) mod 2)). - Gary Detlefs, Jul 13 2011
a(n) = A173557(n)*b(n) where b(n) = 1, 2, 1, 4, 1, 2, 1, 8, 3, 2, 1, 4, 1, 2, ... is the multiplicative function defined by b(p^e) = p^(e-1) if p<>2 and b(2^e)=2^e. b(n) = n/A204455(n). - R. J. Mathar, Jul 02 2013
a(n) = -c_{2n}(n) where c_q(n) is Ramanujan's sum. - Michael Somos, Aug 23 2013
a(n) = A055034(2*n), for n >= 2. - Wolfdieter Lang, Nov 30 2013
O.g.f.: Sum_{n >= 1} mu(2*n-1)*x^(2*n-1)/(1 - x^(2*n-1))^2. - Peter Bala, Mar 17 2019
a(n) = A000010(4*n)/2, for n > = 1 (see Apostol, Theorem 2.5, (b), p. 28). - Wolfdieter Lang, Nov 17 2019
a(n) = n - Sum_{d|n, n/d odd, d < n} a(d). - Ilya Gutkovskiy, May 30 2020
Dirichlet convolution of A000010 and A209229. - Werner Schulte, Jan 17 2021
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} A209229(gcd(n,k)).
a(n) = Sum_{k=1..n} A209229(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = 4/Pi^2 = 0.405284... (A185199). - Amiram Eldar, Oct 22 2022
a(n) = A000034(n) * A000010(n). - Amiram Eldar, May 18 2025

Corrected by Vladeta Jovovic, Dec 04 2002

Previous Showing 31-40 of 94 results. Next

cp's OEIS Frontend

A239682 Product_{i=1..n} A173557(i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

Formula

A333872 Numbers at which the sum of the iterated absolute Möbius divisor function (A173557) attains a record.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A333873 Numbers that equal to the sum of their iterated absolute Möbius divisor function (A173557).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A000961 Powers of primes. Alternatively, 1 and the prime powers (p^k, p prime, k >= 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Python

Python

Sage

Formula

Extensions

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