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

A000668 Mersenne primes (primes of the form 2^n - 1).

Original entry on oeis.org

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727

Offset: 1

N. J. A. Sloane

For a Mersenne number 2^n - 1 to be prime, the exponent n must itself be prime.
See A000043 for the values of n.
Primes that are repunits in base 2.
Define f(k) = 2k+1; begin with k = 2, a(n+1) = least prime of the form f(f(f(...(a(n))))). - Amarnath Murthy, Dec 26 2003
Mersenne primes other than the first are of the form 6n+1. - Lekraj Beedassy, Aug 27 2004. Mersenne primes other than the first are of the form 24n+7; see also A124477. - Artur Jasinski, Nov 25 2007
A034876(a(n)) = 0 and A034876(a(n)+1) = 1. - Jonathan Sondow, Dec 19 2004
Mersenne primes are solutions to sigma(n+1)-sigma(n) = n as perfect numbers (A000396(n)) are solutions to sigma(n) = 2n. In fact, appears to give all n such that sigma(n+1)-sigma(n) = n. - Benoit Cloitre, Aug 27 2002
If n is in the sequence then sigma(sigma(n)) = 2n+1. Is it true that this sequence gives all numbers n such that sigma(sigma(n)) = 2n+1? - Farideh Firoozbakht, Aug 19 2005
It is easily proved that if n is a Mersenne prime then sigma(sigma(n)) - sigma(n) = n. Is it true that Mersenne primes are all the solutions of the equation sigma(sigma(x)) - sigma(x) = x? - Farideh Firoozbakht, Feb 12 2008
Sum of divisors of n-th even superperfect number A061652(n). Sum of divisors of n-th superperfect number A019279(n), if there are no odd superperfect numbers. - Omar E. Pol, Mar 11 2008
Indices of both triangular numbers and generalized hexagonal numbers (A000217) that are also even perfect numbers. - Omar E. Pol, May 10 2008, Sep 22 2013
Number of positive integers (1, 2, 3, ...) whose sum is the n-th perfect number A000396(n). - Omar E. Pol, May 10 2008
Vertex number where the n-th perfect number A000396(n) is located in the square spiral whose vertices are the positive triangular numbers A000217. - Omar E. Pol, May 10 2008
Mersenne numbers A000225 whose indices are the prime numbers A000043. - Omar E. Pol, Aug 31 2008
The digital roots are 1 if p == 1 (mod 6) and 4 if p == 5 (mod 6). [T. Koshy, Math Gaz. 89 (2005) p. 465]
Primes p such that for all primes q < p, p XOR q = p - q. - Brad Clardy, Oct 26 2011
All these primes, except 3, are Brazilian primes, so they are also in A085104 and A023195. - Bernard Schott, Dec 26 2012
All prime numbers p can be classified by k = (p mod 12) into four classes: k=1, 5, 7, 11. The Mersennne prime numbers 2^p-1, p > 2 are in the class k=7 with p=12*(n-1)+7, n=1,2,.... As all 2^p (p odd) are in class k=8 it follows that all 2^p-1, p > 2 are in class k=7. - Freimut Marschner, Jul 27 2013
From "The Guinness Book of Primes": "During the reign of Queen Elizabeth I, the largest known prime number was the number of grains of rice on the chessboard up to and including the nineteenth square: 524,287 [= 2^19 - 1]. By the time Lord Nelson was fighting the Battle of Trafalgar, the record for the largest prime had gone up to the thirty-first square of the chessboard: 2,147,483,647 [= 2^31 - 1]. This ten-digits number was proved to be prime in 1772 by the Swiss mathematician Leonard Euler, and it held the record until 1867." [du Sautoy] - Robert G. Wilson v, Nov 26 2013
If n is in the sequence then A024816(n) = antisigma(n) = antisigma(n+1) - 1. Is it true that this sequence gives all numbers n such that antisigma(n) = antisigma(n+1) - 1? Are there composite numbers with this property? - Jaroslav Krizek, Jan 24 2014
If n is in the sequence then phi(n) + sigma(sigma(n)) = 3n. Is it true that Mersenne primes are all the solutions of the equation phi(x) + sigma(sigma(x)) = 3x? - Farideh Firoozbakht, Sep 03 2014
a(5) = A229381(2) = 8191 is the "Simpsons' Mersenne prime". - Jonathan Sondow, Jan 02 2015
Equivalently, prime powers of the form 2^n - 1, see Theorem 2 in Lemos & Cambraia Junior. - Charles R Greathouse IV, Jul 07 2016
Primes whose sum of divisors is a power of 2. Primes p such that p + 1 is a power of 2. Primes in A046528. - Omar E. Pol, Jul 09 2016
From Jaroslav Krizek, Jan 19 2017: (Start)
Primes p such that sigma(p+1) = 2p+1.
Primes p such that A051027(p) = sigma(sigma(p)) = 2^k-1 for some k > 1.
Primes p of the form sigma(2^prime(n)-1)-1 for some n. Corresponding values of numbers n are in A016027.
Primes p of the form sigma(2^(n-1)) for some n > 1. Corresponding values of numbers n are in A000043 (Mersenne exponents).
Primes of the form sigma(2^(n+1)) for some n > 1. Corresponding values of numbers n are in A153798 (Mersenne exponents-2).
Primes p of the form sigma(n) where n is even; subsequence of A023195. Primes p of the form sigma(n) for some n. Conjecture: 31 is the only prime p such that p = sigma(x) = sigma(y) for distinct numbers x and y; 31 = sigma(16) = sigma(25).
Conjecture: numbers n such that n = sigma(sigma(n+1)-n-1)-1, i.e., A072868(n)-1.
Conjecture: primes of the form sigma(4*(n-1)) for some n. Corresponding values of numbers n are in A281312. (End)
[Conjecture] For n > 2, the Mersenne number M(n) = 2^n - 1 is a prime if and only if 3^M(n-1) == -1 (mod M(n)). - Thomas Ordowski, Aug 12 2018 [This needs proof! - Joerg Arndt, Mar 31 2019]
Named "Mersenne's numbers" by W. W. Rouse Ball (1892, 1912) after Marin Mersenne (1588-1648). - Amiram Eldar, Feb 20 2021
Theorem. Let b = 2^p - 1 (where p is a prime). Then b is a Mersenne prime iff (c = 2^p - 2 is totient or a term of A002202). Otherwise, if c is (nontotient or a term of A005277) then b is composite. Proof. Trivial, since, while b = v^g - 1 where v is even, v > 2, g is an integer, g > 1, b is always composite, and c = v^g - 2 is nontotient (or a term of A005277), and so is for any composite b = 2^g - 1 (in the last case, c = v^g - 2 is also nontotient, or a term of A005277). - Sergey Pavlov, Aug 30 2021 [Disclaimer: This proof has not been checked. - N. J. A. Sloane, Oct 01 2021]

Tom M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 4.
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman and S. S. Wagstaff, Jr., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 135-136.
Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 76.
Marcus P. F. du Sautoy, The Number Mysteries, A Mathematical Odyssey Through Everyday Life, Palgrave Macmillan, First published in 2010 by the Fourth Estate, an imprint of Harper Collins UK, 2011, p. 46. - Robert G. Wilson v, Nov 26 2013
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).
Bryant Tuckerman, The 24th Mersenne prime, Notices Amer. Math. Soc., 18 (Jun, 1971), Abstract 684-A15, p. 608.

Harry J. Smith, Table of n, a(n) for n = 1..18
Peter Alfeld, The 39th Mersenne prime, 2003.
Yan Bingze, Li Qiong, Mao Haokun, and Chen Nan, An efficient hybrid hash based privacy amplification algorithm for quantum key distribution, arXiv:2105.13678 [quant-ph], 2021.
Andrew R. Booker, The Nth Prime Page
John Rafael M. Antalan, A Recreational Application of Two Integer Sequences and the Generalized Repetitious Number Puzzle, arXiv:1908.06014 [math.HO], 2019-2020.
W. W. Rouse Ball, Mathematical recreations and problems of past and present times, London, Macmillan and Co., 1892, pp. 24-25.
W. W. Rouse Ball, Mersenne's numbers, Messenger of Mathematics, Vol. 21 (1892), pp. 34-40, 121.
W. W. Rouse Ball, Mersenne's numbers, Nature, Vol. 89 (1912), p. 86.
John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman and S. S. Wagstaff, Jr., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
Kevin A. Broughan and Qizhi Zhou, On the Ratio of the Sum of Divisors and Euler's Totient Function II, Journal of Integer Sequences, Vol. 17 (2014), Article 14.9.2.
Douglas Butler, Mersenne Primes.
C. K. Caldwell, Mersenne primes.
C. K. Caldwell, "Top Twenty" page, Mersenne Primes.
Luis H. Gallardo and Olivier Rahavandrainy, On (unitary) perfect polynomials over F_2 with only Mersenne primes as odd divisors, arXiv:1908.00106 [math.NT], 2019.
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly 95 (1988), no. 8, 697-712. [Annotated scanned copy]
Christian Kassel and Christophe Reutenauer, Pairs of intertwined integer sequences, arXiv:2507.15780 [math.NT], 2025. See p. 12.
Sameen Ahmed Khan, Primes in Geometric-Arithmetic Progression, arXiv preprint arXiv:1203.2083 [math.NT], 2012. - From _N. J. A. Sloane_, Sep 15 2012
Abílio Lemos and Ady Cambraia Junior, On the number of prime factors of Mersenne numbers, arXiv:1606.08690 [math.NT] (2016).
Benny Lim, Prime Numbers Generated From Highly Composite Numbers, Parabola (2018) Vol. 54, Issue 3.
Math Reference Project, Mersenne and Fermat Primes.
Romeo Meštrović, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 BC--2012) and another new proof, arXiv preprint arXiv:1202.3670 [math.HO], 2012. - From _N. J. A. Sloane_, Jun 13 2012
Romeo Meštrović, Goldbach-type conjectures arising from some arithmetic progressions, University of Montenegro, 2018.
Romeo Meštrović, Goldbach's like conjectures arising from arithmetic progressions whose first two terms are primes, arXiv:1901.07882 [math.NT], 2019.
Landon Curt Noll, Mersenne Prime Digits and Names.
Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
Omar E. Pol, Determinacion geometrica de los numeros primos y perfectos.
Primefan, The Mersenne Primes.
Christian Salas, Cantor Primes as Prime-Valued Cyclotomic Polynomials, arXiv preprint arXiv:1203.3969 [math.NT], 2012.
Harry J. Smith, Mersenne Primes, 1981-2010.
Gordon Spence, 36th Mersenne Prime Found, 1999.
Susan Stepney, Mersenne Prime.
Thesaurus.maths.org, Mersenne Prime.
Bryant Tuckerman, The 24th Mersenne prime, Proc. Nat. Acad. Sci. USA, Vol. 68 (1971), pp. 2319-2320.
Samuel S. Wagstaff, Jr., The Cunningham Project.
Yunlan Wei, Yanpeng Zheng, Zhaolin Jiang and Sugoog Shon, A Study of Determinants and Inverses for Periodic Tridiagonal Toeplitz Matrices with Perturbed Corners Involving Mersenne Numbers, Mathematics, Vol. 7, No. 10 (2019), 893.
Eric Weisstein's World of Mathematics, Mersenne Prime.
Eric Weisstein's World of Mathematics, Perfect Number.
Wikipedia, Mersenne prime.
Marek Wolf, Computer experiments with Mersenne primes, arXiv preprint arXiv:1112.2412 [math.NT], 2011.
Chai Wah Wu, Can machine learning identify interesting mathematics? An exploration using empirically observed laws, arXiv:1805.07431 [cs.LG], 2018.

Cf. A000225 (Mersenne numbers).
Cf. A000043 (Mersenne exponents).
Cf. A001348 (Mersenne numbers with n prime).
Cf. A000040, A000203, A000217, A000396, A003056, A007947, A016027, A019279, A023195, A023758, A028335 (lengths), A034876, A046051, A057951-A057958, A059305, A061652, A083420, A085104, A124477, A135659, A173898.

A000668:=Filtered(List(Filtered([1..600], IsPrime),i->2^i-1),IsPrime); # Muniru A Asiru, Oct 01 2017

A000668 := proc(n) local i;
i := 2^(ithprime(n))-1:
if (isprime(i)) then
   return i
fi: end:
seq(A000668(n), n=1..31); # Jani Melik, Feb 09 2011
# Alternate:
seq(numtheory:-mersenne([i]),i=1..26); # Robert Israel, Jul 13 2014

2^Array[MersennePrimeExponent, 18] - 1 (* Jean-François Alcover, Feb 17 2018, Mersenne primes with less than 1000 digits *)
2^MersennePrimeExponent[Range[18]] - 1 (* Eric W. Weisstein, Sep 04 2021 *)

forprime(p=2,1e5,if(ispseudoprime(2^p-1),print1(2^p-1", "))) \\ Charles R Greathouse IV, Jul 15 2011

LL(e) = my(n, h); n = 2^e-1; h = Mod(2, n); for (k=1, e-2, h=2*h*h-1); return(0==h) \\ after Joerg Arndt in A000043
forprime(p=1, , if(LL(p), print1(p, ", "))) \\ Felix Fröhlich, Feb 17 2018

from sympy import isprime, primerange
print([2**n-1 for n in primerange(1, 1001) if isprime(2**n-1)]) # Karl V. Keller, Jr., Jul 16 2020

a(n) = sigma(A061652(n)) = A000203(A061652(n)). - Omar E. Pol, Apr 15 2008
a(n) = sigma(A019279(n)) = A000203(A019279(n)), provided that there are no odd superperfect numbers. - Omar E. Pol, May 10 2008
a(n) = A000225(A000043(n)). - Omar E. Pol, Aug 31 2008
a(n) = 2^A000043(n) - 1 = 2^(A000005(A061652(n))) - 1. - Omar E. Pol, Oct 27 2011
a(n) = A000040(A059305(n)) = A001348(A016027(n)). - Omar E. Pol, Jun 29 2012
a(n) = A007947(A000396(n))/2, provided that there are no odd perfect numbers. - Omar E. Pol, Feb 01 2013
a(n) = 4*A134709(n) + 3. - Ivan N. Ianakiev, Sep 07 2013
a(n) = A003056(A000396(n)), provided that there are no odd perfect numbers. - Omar E. Pol, Dec 19 2016
Sum_{n>=1} 1/a(n) = A173898. - Amiram Eldar, Feb 20 2021

A002202 Values taken by totient function phi(m) (A000010).

Original entry on oeis.org

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100, 102, 104, 106, 108, 110, 112, 116, 120, 126, 128, 130, 132, 136, 138, 140, 144, 148, 150, 156, 160, 162, 164, 166, 168, 172, 176

Offset: 1

N. J. A. Sloane

These are the numbers n such that for some m the multiplicative group mod m has order n.
Maier & Pomerance show that there are about x * exp(c (log log log x)^2)/log x members of this sequence up to x, with c = 0.81781465... (A234614); see the paper for details on making this precise. - Charles R Greathouse IV, Dec 28 2013
A264739(a(n)) = 1; a(n) occurs A058277(n) times in A007614. - Reinhard Zumkeller, Nov 26 2015
There are no odd numbers > 2 in the sequence and the even numbers that are not in the sequence are in A005277. - Bernard Schott, May 13 2020

J. W. L. Glaisher, Number-Divisor Tables. British Assoc. Math. Tables, Vol. 8, Camb. Univ. Press, 1940, p. 64.
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
André Contiero, and Davi Lima, 2-Adic Stratification of Totients, arXiv:2005.05475 [math.NT], 2020.
K. Ford, The distribution of totients, Electron. Res. Announc. Amer. Math. Soc. 4 (1998), 27-34.
Helmut Maier and Carl Pomerance, On the number of distinct values of Euler's phi-function, Acta Arithmetica 49:3 (1988), pp. 263-275.
Maxim Rytin, Finding the Inverse of Euler Totient Function (1999).
S. Sivasankaranarayana Pillai, On some functions connected with phi(n), Bull. Amer. Math. Soc. 35 (1929), 832-836.
Eric Weisstein's World of Mathematics, Totient Valence Function

Cf. A000010, A002180, A032446, A058277.
Cf. A002110, A005277, A007614, A007617 (complement).
Cf. A083533 (first differences), A264739.
Cf. A006093 (a subsequence).

import Data.List.Ordered (insertSet)
a002202 n = a002202_list !! (n-1)
a002202_list = f [1..] (tail a002110_list) [] where
   f (x:xs) ps'@(p:ps) us
     | x < p = f xs ps' $ insertSet (a000010' x) us
     | otherwise = vs ++ f xs ps ws
     where (vs, ws) = span (<= a000010' x) us
-- Reinhard Zumkeller, Nov 22 2015

with(numtheory); t1 := [seq(nops(invphi(n)), n=1..300)]; t2 := []: for n from 1 to 300 do if t1[n] <> 0 then t2 := [op(t2), n]; fi; od: t2;
# second Maple program:
q:= n-> is(numtheory[invphi](n)<>[]):
select(q, [$1..176])[];  # Alois P. Heinz, Nov 13 2024

phiQ[m_] := Select[Range[m+1, 2m*Product[(1-1/(k*Log[k]))^(-1), {k, 2, DivisorSigma[0, m]}]], EulerPhi[#] == m &, 1 ] != {}; Select[Range[176], phiQ] (* Jean-François Alcover, May 23 2011, after Maxim Rytin *)

lst(lim)=my(P=1,q,v);forprime(p=2,default(primelimit), if(eulerphi(P*=p)>=lim,q=p;break));v=vecsort(vector(P/q*lim\eulerphi(P/q),k,eulerphi(k)),,8);select(n->n<=lim,v) \\ Charles R Greathouse IV, Apr 16 2012

select(istotient,vector(100,i,i)) \\ Charles R Greathouse IV, Dec 28 2012

A007617 Values not in range of Euler phi function.

Original entry on oeis.org

3, 5, 7, 9, 11, 13, 14, 15, 17, 19, 21, 23, 25, 26, 27, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 45, 47, 49, 50, 51, 53, 55, 57, 59, 61, 62, 63, 65, 67, 68, 69, 71, 73, 74, 75, 76, 77, 79, 81, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 98, 99, 101, 103, 105, 107

Offset: 1

Walter Nissen

nonn

Nontotient numbers.
All odd numbers > 2 are in the sequence.
The even numbers of the sequence are in A005277.
The asymptotic density of this sequence is 1. - Amiram Eldar, Mar 26 2021

			There are no solutions to phi(m)=14, so 14 is a member of the sequence.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004, section B36, page 138-142.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Jerzy Browkin and Andrzej Schinzel, On integers not of the form n-phi(n), Colloq. Math., Vol. 58 (1995), pp. 55-58.
Paul Erdős and R. R. Hall, Distinct values of Euler's phi-function, Mathematika, Vol. 23 (1976), pp. 1-3.
Kevin Ford, The distribution of totients. Paul Erdős (1913-1996). Ramanujan J., Vol. 2 (1998) pp. 67-151; arXiv preprint, arXiv:1104.3264 [math.NT], 2011-2013.
Kevin Ford, The distribution of totients, Electron. Res. Announc. Amer. Math. Soc., Vol. 4 (1998) pp. 27-34.
Kevin Ford, The number of solutions of phi(x)=m, Ann. of Math.(2), Vol. 150, No. 1 (1999), pp. 283-311.
Helmut Maier and Carl Pomerance, On the number of distinct values of Euler's phi-function, Acta Arithmetica, Vol. 49, No. 3 (1988), pp. 263-275.
Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
Maxim Rytin, Finding the Inverse of Euler Totient Function, Wolfram Library Archive, 1999.
Zhang Ming-Zhi, On nontotients, J. Number Theory, Vol. 43, No. 2 (1993), pp. 168-173.

Numbers not in A000010.
Complement of A002202.
Cf. A005277, A180639.
Cf. A083534 (first differences), A264739.

import Data.List.Ordered (minus)
a007617 n = a007617_list !! (n-1)
a007617_list = [1..] `minus` a002202_list
-- Reinhard Zumkeller, Nov 22 2015

A007617 := n -> if invphi(n)=[] then n fi: seq(A007617(i),i=1..107); # Peter Luschny, Jun 26 2011

inversePhi[m_?OddQ] = {}; inversePhi[1] = {1, 2}; inversePhi[m_] := Module[{p, nmax, n, nn}, p = Select[Divisors[m] + 1, PrimeQ]; nmax = m*Times @@ (p/(p - 1)); n = m; nn = {}; While[n <= nmax, If[EulerPhi[n] == m, AppendTo[nn, n]]; n++]; nn]; Select[Range[107], inversePhi[#] == {} &] (* Jean-François Alcover, Jan 03 2012 *)
Select[Range[107], invphi[#] == {}&] (* Jean-François Alcover, Mar 19 2019, using Maxim Rytin's much faster 'invphi' program *)

is(n)=!istotient(n) \\ Charles R Greathouse IV, Dec 28 2013

A264739(a(n)) = 0. - Reinhard Zumkeller, Nov 26 2015

A051222 Numbers k such that Bernoulli number B_{k} has denominator 6.

Original entry on oeis.org

2, 14, 26, 34, 38, 62, 74, 86, 94, 98, 118, 122, 134, 142, 146, 158, 182, 194, 202, 206, 214, 218, 254, 266, 274, 278, 298, 302, 314, 326, 334, 338, 362, 386, 394, 398, 422, 434, 446, 454, 458, 482, 494, 514, 518, 526, 538, 542, 554, 566, 578

Offset: 1

N. J. A. Sloane

Alternative definition: let D(m) = set of divisors of m; sequence gives n such that the set 1 + D(n) contains only two primes, 2 and 3. E.g., n=98: D(98)={1,2,7,15,49,98}, 1+D = {2,3,8,16,50,99} of which only 2 terms are prime numbers: {2,3}. Observation by Labos Elemer, Jun 24 2002. This is a consequence of the von Staudt-Clausen theorem. - N. J. A. Sloane, Jan 04 2004
The fraction of Bernoulli numbers with denominator 6 is roughly 1/6, see Erdős-Wagstaff. But calculations by H. Cohen and G. Tenenbaum suggest that the fraction is closer to 1/7 (posting to Number Theory List around Dec 20 2005).
Simon Plouffe reports (Feb 13 2007) that at B_{9083002} the proportion is 0.151848915149418661363281... and still decreasing very slowly.
In his PhD thesis at the University of Illinois (see reference), Richard Sunseri proved that a higher proportion of Bernoulli denominators equal 6 than any other value.
Rado showed that for a given Bernoulli number B_n there exist infinitely many Bernoulli numbers B_m having the same denominator. As a special case, if n = 2p where p is an odd prime p == 1 (mod 3), then the denominator of the Bernoulli number B_n equals 6. - Bernd C. Kellner, Mar 21 2018
Conjecture: When the expression (p+q^b)/2 is required to be prime, p is prime, and q is a prime >=5, then all p values are prime congruent to 1 (mod 12) (A068228), if and only if the exponent b is a member of this set. - Richard R. Forberg, Apr 07 2025
There are additional exponential expressions conjectured for generating each of several known prime subsequences (e.g., Pythagorean primes, A002144) where the sequence is invariant to the exponent, if and only if the exponent is a member of this set.  See Forberg link. - Richard R. Forberg, Apr 25 2025

B. C. Berndt, Ramanujan's Notebooks Part IV, Springer-Verlag, see p. 75.
C. J. Moreno and S. S. Wagstaff, Sums of Squares of Integers, CRC Press, 2005, Sect. 3.9.
H. Rademacher, Topics in Analytic Number Theory, Springer, 1973, Chap. 1, p. 10.

T. D. Noe, Table of n, a(n) for n = 1..1000
Paul Erdős and Samuel S. Wagstaff, Jr., The fractional parts of the Bernoulli numbers, Illinois J. Math. 24 (1980), pp. 104-112, MR 81c:10064.
Richard R. Forberg, A051222 and Exponential Expressions the Reproduce Certain Prime Subsets, 2025.
K. L. Jensen, Om talteoretiske Egenskaber ved de Bernoulliske Tal, Nyt Tidskrift für Math. Afdeling B 28 (1915), pp. 73-83.
R. Rado, A note on the Bernoullian numbers, J. London Math. Soc. 9 (1934) 88-90.
Richard Sunseri, Zeros of p-adic L-functions and densities relating to Bernoulli numbers, PhD thesis, University of Illinois, 1979.
Index entries for sequences related to Bernoulli numbers.

Except for 2, all terms are even nontotient numbers. Proper subset of A005277: e.g., 50 and 90 are not here. - Labos Elemer
A112772 is a subsequence. - Bernd C. Kellner, Mar 21 2018
Cf. A045979, A000005, A067513, A002202, A005277.

di[x_] := Divisors[x]
dp[x_] := Part[di[x], Flatten[Position[PrimeQ[1+di[x]], True]]]+1
Do[s=Length[dp[n]]; If[Equal[s, 2], Print[n]], {n, 1, 10000}] (* Labos Elemer *)
Do[s=Denominator[BernoulliB[n]]; If[Equal[s, 6], Print[n]], {n, 1, 1000}] (* Labos Elemer *)
Do[s=1+Divisors[n];s1=Flatten[Position[PrimeQ[s], True]]; (*analogous [suitably modified] pairs of programs yield A051225-A051230*) s2=Part[s, s1];If[Equal[s2, {2, 3}], Print[n]], {n, 1, 100}] (* Labos Elemer *)
Select[Range[600],Denominator[BernoulliB[#]]==6&] (* Harvey P. Dale, Dec 08 2011 *)

for(n=1,10^3,if(denominator(bernfrac(n))==6,print1(n,", "))); \\ Joerg Arndt, Oct 28 2014

is(n)=if(n%2,return(0)); fordiv(n/2,d,if(isprime(2*d+1)&&d>1, return(0))); 1 \\ Charles R Greathouse IV, Oct 28 2014

Additional comments and references from Sam Wagstaff, Dec 20 2005

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

A000668 Mersenne primes (primes of the form 2^n - 1).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

PARI

Python

Formula

A002202 Values taken by totient function phi(m) (A000010).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

A007617 Values not in range of Euler phi function.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A051222 Numbers k such that Bernoulli number B_{k} has denominator 6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI