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

A000225 a(n) = 2^n - 1. (Sometimes called Mersenne numbers, although that name is usually reserved for A001348.)

Original entry on oeis.org

0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591

Offset: 0

N. J. A. Sloane

This is the Gaussian binomial coefficient [n,1] for q=2.
Number of rank-1 matroids over S_n.
Numbers k such that the k-th central binomial coefficient is odd: A001405(k) mod 2 = 1. - Labos Elemer, Mar 12 2003
This gives the (zero-based) positions of odd terms in the following convolution sequences: A000108, A007460, A007461, A007463, A007464, A061922.
Also solutions (with minimum number of moves) for the problem of Benares Temple, i.e., three diamond needles with n discs ordered by decreasing size on the first needle to place in the same order on the third one, without ever moving more than one disc at a time and without ever placing one disc at the top of a smaller one. - Xavier Acloque, Oct 18 2003
a(0) = 0, a(1) = 1; a(n) = smallest number such that a(n)-a(m) == 0 (mod (n-m+1)), for all m. - Amarnath Murthy, Oct 23 2003
Binomial transform of [1, 1/2, 1/3, ...] = [1/1, 3/2, 7/3, ...]; (2^n - 1)/n, n=1,2,3, ... - Gary W. Adamson, Apr 28 2005
Numbers whose binary representation is 111...1. E.g., the 7th term is (2^7) - 1 = 127 = 1111111 (in base 2). - Alexandre Wajnberg, Jun 08 2005
Number of nonempty subsets of a set with n elements. - Michael Somos, Sep 03 2006
For n >= 2, a(n) is the least Fibonacci n-step number that is not a power of 2. - Rick L. Shepherd, Nov 19 2007
Let P(A) be the power set of an n-element set A. Then a(n+1) = the number of pairs of elements {x,y} of P(A) for which x and y are disjoint and for which either x is a subset of y or y is a subset of x. - Ross La Haye, Jan 10 2008
A simpler way to state this is that it is the number of pairs (x,y) where at least one of x and y is the empty set. - Franklin T. Adams-Watters, Oct 28 2011
2^n-1 is the sum of the elements in a Pascal triangle of depth n. - Brian Lewis (bsl04(AT)uark.edu), Feb 26 2008
Sequence generalized: a(n) = (A^n -1)/(A-1), n >= 1, A integer >= 2. This sequence has A=2; A003462 has A=3; A002450 has A=4; A003463 has A=5; A003464 has A=6; A023000 has A=7; A023001 has A=8; A002452 has A=9; A002275 has A=10; A016123 has A=11; A016125 has A=12; A091030 has A=13; A135519 has A=14; A135518 has A=15; A131865 has A=16; A091045 has A=17; A064108 has A=20. - Ctibor O. Zizka, Mar 03 2008
a(n) is also a Mersenne prime A000668 when n is a prime number in A000043. - Omar E. Pol, Aug 31 2008
a(n) is also a Mersenne number A001348 when n is prime. - Omar E. Pol, Sep 05 2008
With offset 1, = row sums of triangle A144081; and INVERT transform of A009545 starting with offset 1; where A009545 = expansion of sin(x)*exp(x). - Gary W. Adamson, Sep 10 2008
Numbers n such that A000120(n)/A070939(n) = 1. - Ctibor O. Zizka, Oct 15 2008
For n > 0, sequence is equal to partial sums of A000079; a(n) = A000203(A000079(n-1)). - Lekraj Beedassy, May 02 2009
Starting with offset 1 = the Jacobsthal sequence, A001045, (1, 1, 3, 5, 11, 21, ...) convolved with (1, 2, 2, 2, ...). - Gary W. Adamson, May 23 2009
Numbers n such that n=2*phi(n+1)-1. - Farideh Firoozbakht, Jul 23 2009
a(n) = (a(n-1)+1)-th odd numbers = A005408(a(n-1)) for n >= 1. - Jaroslav Krizek, Sep 11 2009
Partial sums of a(n) for n >= 0 are A000295(n+1). Partial sums of a(n) for n >= 1 are A000295(n+1) and A130103(n+1). a(n) = A006127(n) - (n+1). - Jaroslav Krizek, Oct 16 2009
If n is even a(n) mod 3 = 0. This follows from the congruences 2^(2k) - 1 ~ 2*2*...*2 - 1 ~ 4*4*...*4 - 1 ~ 1*1*...*1 - 1 ~ 0 (mod 3). (Note that 2*2*...*2 has an even number of terms.) - Washington Bomfim, Oct 31 2009
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=2,(i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n >= 1, a(n)=det(A). - Milan Janjic, Jan 26 2010
This is the sequence A(0,1;1,2;2) = A(0,1;3,-2;0) of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
a(n) = S(n+1,2), a Stirling number of the second kind. See the example below. - Dennis P. Walsh, Mar 29 2011
Entries of row a(n) in Pascal's triangle are all odd, while entries of row a(n)-1 have alternating parities of the form odd, even, odd, even, ..., odd.
Define the bar operation as an operation on signed permutations that flips the sign of each entry. Then a(n+1) is the number of signed permutations of length 2n that are equal to the bar of their reverse-complements and avoid the set of patterns {(-2,-1), (-1,+2), (+2,+1)}.  (See the Hardt and Troyka reference.) - Justin M. Troyka, Aug 13 2011
A159780(a(n)) = n and A159780(m) < n for m < a(n). - Reinhard Zumkeller, Oct 21 2011
This sequence is also the number of proper subsets of a set with n elements. - Mohammad K. Azarian, Oct 27 2011
a(n) is the number k such that the number of iterations of the map k -> (3k +1)/2 == 1 (mod 2) until reaching (3k +1)/2 == 0 (mod 2) equals n. (see the Collatz problem). - Michel Lagneau, Jan 18 2012
For integers a, b, denote by a<+>b the least c >= a such that Hd(a,c) = b (note that, generally speaking, a<+>b differs from b<+>a). Then a(n+1)=a(n)<+>1. Thus this sequence is the Hamming analog of nonnegative integers. - Vladimir Shevelev, Feb 13 2012
Pisano period lengths: 1, 1, 2, 1, 4, 2, 3, 1, 6, 4, 10, 2, 12, 3, 4, 1, 8, 6, 18, 4, ... apparently A007733. - R. J. Mathar, Aug 10 2012
Start with n. Each n generates a sublist {n-1,n-2,...,1}. Each element of each sublist also generates a sublist. Take the sum of all. E.g., 3->{2,1} and 2->{1}, so a(3)=3+2+1+1=7. - Jon Perry, Sep 02 2012
This is the Lucas U(P=3,Q=2) sequence. - R. J. Mathar, Oct 24 2012
The Mersenne numbers >= 7 are all Brazilian numbers, as repunits in base two. See Proposition 1 & 5.2 in Links: "Les nombres brésiliens". - Bernard Schott, Dec 26 2012
Number of line segments after n-th stage in the H tree. - Omar E. Pol, Feb 16 2013
Row sums of triangle in A162741. - Reinhard Zumkeller, Jul 16 2013
a(n) is the highest power of 2 such that 2^a(n) divides (2^n)!. - Ivan N. Ianakiev, Aug 17 2013
In computer programming, these are the only unsigned numbers such that k&(k+1)=0, where & is the bitwise AND operator and numbers are expressed in binary. - Stanislav Sykora, Nov 29 2013
Minimal number of moves needed to interchange n frogs in the frogs problem (see for example the NRICH 1246 link or the Britton link below). - N. J. A. Sloane, Jan 04 2014
a(n) !== 4 (mod 5); a(n) !== 10 (mod 11); a(n) !== 2, 4, 5, 6 (mod 7). - Carmine Suriano, Apr 06 2014
After 0, antidiagonal sums of the array formed by partial sums of integers (1, 2, 3, 4, ...). - Luciano Ancora, Apr 24 2015
a(n+1) equals the number of ternary words of length n avoiding 01,02. - Milan Janjic, Dec 16 2015
With offset 0 and another initial 0, the n-th term of 0, 0, 1, 3, 7, 15, ... is the number of commas required in the fully-expanded von Neumann definition of the ordinal number n. For example, 4 := {0, 1, 2, 3} := {{}, {{}}, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}}, which uses seven commas. Also, for n>0, a(n) is the total number of symbols required in the fully-expanded von Neumann definition of ordinal n - 1, where a single symbol (as usual) is always used to represent the empty set and spaces are ignored. E.g., a(5) = 31, the total such symbols for the ordinal 4. - Rick L. Shepherd, May 07 2016
With the quantum integers defined by [n+1]A001045%20are%20given%20by%20q%20=%20i%20*%20sqrt(2)%20for%20i%5E2%20=%20-1.%20Cf.%20A239473.%20-%20_Tom%20Copeland">q = (q^(n+1) - q^(-n-1)) / (q - q^(-1)), the Mersenne numbers are a(n+1) = q^n [n+1]_q with q = sqrt(2), whereas the signed Jacobsthal numbers A001045 are given by q = i * sqrt(2) for i^2 = -1. Cf. A239473. - _Tom Copeland, Sep 05 2016
For n>1: numbers n such that n - 1 divides sigma(n + 1). - Juri-Stepan Gerasimov, Oct 08 2016
This is also the second column of the Stirling2 triangle A008277 (see also A048993). - Wolfdieter Lang, Feb 21 2017
Except for the initial terms, the decimal representation of the x-axis of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 659", "Rule 721" and "Rule 734", based on the 5-celled von Neumann neighborhood initialized with a single on cell. - Robert Price, Mar 14 2017
a(n), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving partial injective mappings on a set with n elements. - James Mitchell and Wilf A. Wilson, Jul 21 2017
Also the number of independent vertex sets and vertex covers in the complete bipartite graph K_{n-1,n-1}. - Eric W. Weisstein, Sep 21 2017
Sum_{k=0..n} p^k is the determinant of n X n matrix M_(i, j) = binomial(i + j - 1, j)*p + binomial(i+j-1, i), in this case p=2 (empirical observation). - Tony Foster III, May 11 2019
The rational numbers r(n) = a(n+1)/2^(n+1) = a(n+1)/A000079(n+1) appear also as root of the n-th iteration f^{[n]}(c; x) = 2^(n+1)*x - a(n+1)*c of f(c; x) = f^{[0]}(c; x) = 2*x - c as r(n)*c. This entry is motivated by a riddle of Johann Peter Hebel (1760 - 1826): Erstes Rechnungsexempel(Ein merkwürdiges Rechnungs-Exempel) from 1803, with c = 24 and n = 2, leading to the root r(2)*24 = 21 as solution. See the link and reference. For the second problem, also involving the present sequence, see a comment in A130330. - Wolfdieter Lang, Oct 28 2019
a(n) is the sum of the smallest elements of all subsets of {1,2,..,n} that contain n. For example, a(3)=7; the subsets of {1,2,3} that contain 3 are {3}, {1,3}, {2,3}, {1,2,3}, and the sum of smallest elements is 7. - Enrique Navarrete, Aug 21 2020
a(n-1) is the number of nonempty subsets of {1,2,..,n} which don't have an element that is the size of the set. For example, for n = 4, a(3) = 7 and the subsets are {2}, {3}, {4}, {1,3}, {1,4}, {3,4}, {1,2,4}. - Enrique Navarrete, Nov 21 2020
From Eric W. Weisstein, Sep 04 2021: (Start)
Also the number of dominating sets in the complete graph K_n.
Also the number of minimum dominating sets in the n-helm graph for n >= 3. (End)
Conjecture: except for a(2)=3, numbers m such that 2^(m+1) - 2^j - 2^k - 1 is composite for all 0 <= j < k <= m. - Chai Wah Wu, Sep 08 2021
a(n) is the number of three-in-a-rows passing through a corner cell in n-dimensional tic-tac-toe. - Ben Orlin, Mar 15 2022
From Vladimir Pletser, Jan 27 2023: (Start)
a(n) == 1 (mod 30) for n == 1 (mod 4);
a(n) == 7 (mod 120) for n == 3 (mod 4);
(a(n) - 1)/30 = (a(n+2) - 7)/120 for n odd;
(a(n) - 1)/30 = (a(n+2) - 7)/120 = A131865(m) for n == 1 (mod 4) and m >= 0 with A131865(0) = 0. (End)
a(n) is the number of n-digit numbers whose smallest decimal digit is 8. - Stefano Spezia, Nov 15 2023
Also, number of nodes in a perfect binary tree of height n-1, or: number of squares (or triangles) after the n-th step of the construction of a Pythagorean tree: Start with a segment. At each step, construct squares having the most recent segment(s) as base, and isosceles right triangles having the opposite side of the squares as hypotenuse ("on top" of each square). The legs of these triangles will serve as the segments which are the bases of the squares in the next step. - M. F. Hasler, Mar 11 2024
a(n) is the length of the longest path in the n-dimensional hypercube. - Christian Barrientos, Apr 13 2024
a(n) is the diameter of the n-Hanoi graph.  Equivalently, a(n) is the largest minimum number of moves between any two states of the Towers of Hanoi problem (aka problem of Benares Temple described above). - Allan Bickle, Aug 09 2024

			For n=3, a(3)=S(4,2)=7, a Stirling number of the second kind, since there are 7 ways to partition {a,b,c,d} into 2 nonempty subsets, namely,
  {a}U{b,c,d}, {b}U{a,c,d}, {c}U{a,b,d}, {d}U{a,b,c}, {a,b}U{c,d}, {a,c}U{b,d}, and {a,d}U{b,c}. - _Dennis P. Walsh_, Mar 29 2011
From _Justin M. Troyka_, Aug 13 2011: (Start)
Since a(3) = 7, there are 7 signed permutations of 4 that are equal to the bar of their reverse-complements and avoid {(-2,-1), (-1,+2), (+2,+1)}. These are:
  (+1,+2,-3,-4),
  (+1,+3,-2,-4),
  (+1,-3,+2,-4),
  (+2,+4,-1,-3),
  (+3,+4,-1,-2),
  (-3,+1,-4,+2),
  (-3,-4,+1,+2). (End)
G.f. = x + 3*x^2 + 7*x^3 + 15*x^4 + 31*x^5 + 63*x^6 + 127*x^7 + ...
For the Towers of Hanoi problem with 2 disks, the moves are as follows, so a(2) = 3.
12|_|_ -> 2|1|_ -> _|1|2 -> _|_|12  - _Allan Bickle_, Aug 07 2024

P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 75.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 79.
Johann Peter Hebel, Gesammelte Werke in sechs Bänden, Herausgeber: Jan Knopf, Franz Littmann und Hansgeorg Schmidt-Bergmann unter Mitarbeit von Ester Stern, Wallstein Verlag, 2019. Band 3, S. 20-21, Loesung, S. 36-37. See also the link below.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 46, 60, 75-83.
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, page 141.
D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, "Tower of Hanoi", Penguin Books, 1987, pp. 112-113.

Franklin T. Adams-Watters, Table of n, a(n) for n = 0..1000
Omran Ahmadi and Robert Granger, An efficient deterministic test for Kloosterman sum zeros, Math. Comp. 83 (2014), 347-363, arXiv:1104.3882 [math.NT], 2011-2012. See 1st and 2nd column of Table 1 p. 9.
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
Anonymous, The Tower of Hanoi
M. Baake, F. Gahler and U. Grimm, Examples of substitution systems and their factors, arXiv:1211.5466 [math.DS], 2012-2013.
Michael Baake, Franz Gähler, and Uwe Grimm, Examples of Substitution Systems and Their Factors, Journal of Integer Sequences, Vol. 16 (2013), #13.2.14.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.
J. Bernheiden, Mersennesche Zahlen, (Text in German) [Wayback Machine cached version].
Michael Boardman, The Egg-Drop Numbers, Mathematics Magazine, 77 (2004), 368-372.
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100, CWI Report 9212, 1992 [Wayback Machine cached version].
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100: Update 2
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations Of Cunningham Numbers With Bases 13 To 99. Millennium Edition [BROKEN LINK]
R. P. Brent, P. L. Montgomery and H. J. J. te Riele, Factorizations of Cunningham numbers with bases 13 to 99: Millennium edition
R. P. Brent and H. J. J. te Riele, Factorizations of a^n +- 1, 13 <= a < 100
John Brillhart et al., Cunningham Project [Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers] [Subscription required].
Jill Britton, The Tower of Hanoi [Video file, Wayback Machine cached version].
Jill Britton, The Frog Puzzle [Wayback Machine cached version].
C. K. Caldwell, The Prime Glossary, Mersenne number
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. Catarino, H. Campos, and P. Vasco, On the Mersenne sequence, Annales Mathematicae et Informaticae, 46 (2016) pp. 37-53.
Robert George Cowell, A unifying framework for the modelling and analysis of STR DNA samples arising in forensic casework, arXiv:1802.09863 [stat.AP], 2018.
F. Javier de Vega, An extension of Furstenberg's theorem of the infinitude of primes, arXiv:2003.13378 [math.NT], 2020.
W. M. B. Dukes, On the number of matroids on a finite set, arXiv:math/0411557 [math.CO], 2004.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_James Mitchell_ and _Wilf A. Wilson_, Jul 21 2017]
W. Edgington, Mersenne Page [BROKEN LINK]
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
T. Eveilleau, Animated solution to the Tower of Hanoi problem
G. Everest et al., Primes generated by recurrence sequences, Amer. Math. Monthly, 114 (No. 5, 2007), 417-431.
G. Everest, S. Stevens, D. Tamsett and T. Ward, Primitive divisors of quadratic polynomial sequences, arXiv:math/0412079 [math.NT], 2004-2006.
G. Everest, A. J. van der Poorten, Y. Puri and T. Ward, Integer Sequences and Periodic Points, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.3.
Bakir Farhi, Summation of Certain Infinite Lucas-Related Series, J. Int. Seq., Vol. 22 (2019), Article 19.1.6.
Emmanuel Ferrand, Deformations of the Taylor Formula, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.7.
Carrie E. Finch-Smith and R. Scottfield Groth, Arbitrarily Long Sequences of Sierpiński Numbers that are the Sum of a Sierpiński Number and a Mersenne Number, Journal of Integer Sequences, Vol. 28 (2025), Article 25.2.4. See p. 22.
Robert Frontczak and Taras Goy, Mersenne-Horadam identities using generating functions, Carpathian Mathematical Publications, Vol. 12, no. 1, (2020), 34-45.
Robert Granger, On the Enumeration of Irreducible Polynomials over GF(q) with Prescribed Coefficients, arXiv:1610.06878 [math.AG], 2016. See 1st and 2nd column of Table 1 p. 13.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
Taras Goy, On new identities for Mersenne numbers, Applied Mathematics E-Notes, 18 (2018), 100-105.
R. K. Guy, Letter to N. J. A. Sloane
A. Hardt and J. M. Troyka, Restricted symmetric signed permutations, Pure Mathematics and Applications, Vol. 23 (No. 3, 2012), pp. 179--217.
A. Hardt and J. M. Troyka, Slides (associated with the Hardt and Troyka reference above).
Johann Peter Hebel, Erstes Rechnungsexempel, 1803; Solution: Auflösung des ersten Rechnungsexempels und ein zweites, 1804.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 11. Book's website
A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 138, 345, 371, and 880
Jiří Klaška, Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
J. Loy, The Tower of Hanoi
Edouard Lucas, The Theory of Simply Periodic Numerical Functions, Fibonacci Association, 1969. English translation of article "Théorie des Fonctions Numériques Simplement Périodiques, I", Amer. J. Math., 1 (1878), 184-240.
Mathforum, Tower of Hanoi
Mathforum, Problem of the Week, The Tower of Hanoi Puzzle
Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
R. Mestrovic, 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
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
N. Neumarker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, JIS 12 (2009) 09.4.5, Example 11.
NRICH 1246, Frogs
Ahmet Öteleş, Bipartite Graphs Associated with Pell, Mersenne and Perrin Numbers, An. Şt. Univ. Ovidius Constantą, (2019) Vol. 27, Issue 2, 109-120.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See pp. 1, 4.
Bernard Schott, Les nombres brésiliens, Reprinted from Quadrature, no. 76, avril-juin 2010, pages 30-38, included here with permission from the editors of Quadrature.
R. R. Snapp, The Tower of Hanoi.
Amelia Carolina Sparavigna, On the generalized sums of Mersenne, Fermat, Cullen and Woodall Numbers, Politecnico di Torino (Italy, 2019).
Amelia Carolina Sparavigna, Composition Operations of Generalized Entropies Applied to the Study of Numbers, International Journal of Sciences (2019) Vol. 8, No. 4, 87-92.
Amelia Carolina Sparavigna, The groupoids of Mersenne, Fermat, Cullen, Woodall and other Numbers and their representations by means of integer sequences, Politecnico di Torino, Italy (2019), [math.NT].
Amelia Carolina Sparavigna, Some Groupoids and their Representations by Means of Integer Sequences, International Journal of Sciences (2019) Vol. 8, No. 10.
Thesaurus.maths.org, Mersenne Number
Thinks.com, Tower of Hanoi, A classic puzzle game
A. Umar, Combinatorial Results for Semigroups of Orientation-Preserving Partial Transformations, Journal of Integer Sequences, 14 (2011), #11.7.5.
Eric Weisstein's World of Mathematics, Coin Tossing, Digit, Repunit, Rule 222, Run, and Tower of Hanoi
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Helm Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Mersenne Number
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, H tree, Lucas sequence, and Tower of Hanoi
K. K. Wong, Tower Of Hanoi:Online Game
K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math., 3 (1892), 265-284.
Index entries for "core" sequences
Index to divisibility sequences
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000043 (Mersenne exponents).
Cf. A000668 (Mersenne primes).
Cf. A001348 (Mersenne numbers with n prime).
Cf. A000079, A001045, A009545, A016189, A052955, A083329, A085104, A144081.
Cf. a(n)=A112492(n, 2). Rightmost column of A008969.
a(n) = A118654(n, 1) = A118654(n-1, 3), for n > 0.
Subsequence of A132781.
Smallest number whose base b sum of digits is n: this sequence (b=2), A062318 (b=3), A180516 (b=4), A181287 (b=5), A181288 (b=6), A181303 (b=7), A165804 (b=8), A140576 (b=9), A051885 (b=10).
Cf. A000203, A239473, A279396.
Cf. A008277, A048993 (columns k=2), A000918, A130330.
Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

a000225 = (subtract 1) . (2 ^)
a000225_list = iterate ((+ 1) . (* 2)) 0
-- Reinhard Zumkeller, Mar 20 2012

A000225 := n->2^n-1; [ seq(2^n-1,n=0..50) ];
A000225:=1/(2*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, sequence starting at a(1)

a[n_] := 2^n - 1; Table[a[n], {n, 0, 30}] (* Stefan Steinerberger, Mar 30 2006 *)
Array[2^# - 1 &, 50, 0] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Dec 26 2006 *)
NestList[2 # + 1 &, 0, 32] (* Robert G. Wilson v, Feb 28 2011 *)
2^Range[0, 20] - 1 (* Eric W. Weisstein, Jul 17 2017 *)
LinearRecurrence[{3, -2}, {1, 3}, 20] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 3 x + 2 x^2), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)

A000225(n) = 2^n-1  \\ Michael B. Porter, Oct 27 2009

concat(0, Vec(x/((1-2*x)*(1-x)) + O(x^100))) \\ Altug Alkan, Oct 28 2015

def A000225(n): return (1<Chai Wah Wu, Jul 06 2022

def isMersenne(n): return n == sum([(1 - b) << s for (s, b) in enumerate((n+1).bits())]) # Peter Luschny, Sep 01 2019

G.f.: x/((1-2*x)*(1-x)).
E.g.f.: exp(2*x) - exp(x).
E.g.f. if offset 1: ((exp(x)-1)^2)/2.
a(n) = Sum_{k=0..n-1} 2^k. - Paul Barry, May 26 2003
a(n) = a(n-1) + 2*a(n-2) + 2, a(0)=0, a(1)=1. - Paul Barry, Jun 06 2003
Let b(n) = (-1)^(n-1)*a(n). Then b(n) = Sum_{i=1..n} i!*i*Stirling2(n,i)*(-1)^(i-1). E.g.f. of b(n): (exp(x)-1)/exp(2x). - Mario Catalani (mario.catalani(AT)unito.it), Dec 19 2003
a(n+1) = 2*a(n) + 1, a(0) = 0.
a(n) = Sum_{k=1..n} binomial(n, k).
a(n) = n + Sum_{i=0..n-1} a(i); a(0) = 0. - Rick L. Shepherd, Aug 04 2004
a(n+1) = (n+1)*Sum_{k=0..n} binomial(n, k)/(k+1). - Paul Barry, Aug 06 2004
a(n+1) = Sum_{k=0..n} binomial(n+1, k+1). - Paul Barry, Aug 23 2004
Inverse binomial transform of A001047. Also U sequence of Lucas sequence L(3, 2). - Ross La Haye, Feb 07 2005
a(n) = A099393(n-1) - A020522(n-1) for n > 0. - Reinhard Zumkeller, Feb 07 2006
a(n) = A119258(n,n-1) for n > 0. - Reinhard Zumkeller, May 11 2006
a(n) = 3*a(n-1) - 2*a(n-2); a(0)=0, a(1)=1. - Lekraj Beedassy, Jun 07 2006
Sum_{n>0} 1/a(n) = 1.606695152... = A065442, see A038631. - Philippe Deléham, Jun 27 2006
Stirling_2(n-k,2) starting from n=k+1. - Artur Jasinski, Nov 18 2006
a(n) = A125118(n,1) for n > 0. - Reinhard Zumkeller, Nov 21 2006
a(n) = StirlingS2(n+1,2). - Ross La Haye, Jan 10 2008
a(n) = A024036(n)/A000051(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A024088(n)/A001576(n). -Reinhard Zumkeller, Feb 15 2009
a(2*n) = a(n)*A000051(n); a(n) = A173787(n,0). - Reinhard Zumkeller, Feb 28 2010
For n > 0: A179857(a(n)) = A024036(n) and A179857(m) < A024036(n) for m < a(n). - Reinhard Zumkeller, Jul 31 2010
From Enrique Pérez Herrero, Aug 21 2010: (Start)
a(n) = J_n(2), where J_n is the n-th Jordan Totient function: (A007434, is J_2).
a(n) = Sum_{d|2} d^n*mu(2/d). (End)
A036987(a(n)) = 1. - Reinhard Zumkeller, Mar 06 2012
a(n+1) = A044432(n) + A182028(n). - Reinhard Zumkeller, Apr 07 2012
a(n) = A007283(n)/3 - 1. - Martin Ettl, Nov 11 2012
a(n+1) = A001317(n) + A219843(n); A219843(a(n)) = 0. - Reinhard Zumkeller, Nov 30 2012
a(n) = det(|s(i+2,j+1)|, 1 <= i,j <= n-1), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 06 2013
G.f.: Q(0), where Q(k) = 1 - 1/(4^k - 2*x*16^k/(2*x*4^k - 1/(1 - 1/(2*4^k - 8*x*16^k/(4*x*4^k - 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013
E.g.f.: Q(0), where Q(k) = 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - (k+1)/Q(k+1))); (continued fraction).
G.f.: Q(0), where Q(k) = 1 - 1/(2^k - 2*x*4^k/(2*x*2^k - 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 23 2013
a(n) = A000203(2^(n-1)), n >= 1. - Ivan N. Ianakiev, Aug 17 2013
a(n) = Sum_{t_1+2*t_2+...+n*t_n=n} n*multinomial(t_1+t_2 +...+t_n,t_1,t_2,...,t_n)/(t_1+t_2 +...+t_n). - Mircea Merca, Dec 06 2013
a(0) = 0; a(n) = a(n-1) + 2^(n-1) for n >= 1. - Fred Daniel Kline, Feb 09 2014
a(n) = A125128(n) - A000325(n) + 1. - Miquel Cerda, Aug 07 2016
From Ilya Gutkovskiy, Aug 07 2016: (Start)
Binomial transform of A057427.
Sum_{n>=0} a(n)/n! = A090142. (End)
a(n) = A000918(n) + 1. - Miquel Cerda, Aug 09 2016
a(n+1) = (A095151(n+1) - A125128(n))/2. - Miquel Cerda, Aug 12 2016
a(n) = (A079583(n) - A000325(n+1))/2. - Miquel Cerda, Aug 15 2016
Convolution of binomial coefficient C(n,a(k)) with itself is C(n,a(k+1)) for all k >= 3. - Anton Zakharov, Sep 05 2016
a(n) = (A083706(n-1) + A000325(n))/2. - Miquel Cerda, Sep 30 2016
a(n) = A005803(n) + A005408(n-1). - Miquel Cerda, Nov 25 2016
a(n) = A279396(n+2,2). - Wolfdieter Lang, Jan 10 2017
a(n) = n + Sum_{j=1..n-1} (n-j)*2^(j-1). See a Jun 14 2017 formula for A000918(n+1) with an interpretation. - Wolfdieter Lang, Jun 14 2017
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k,i). - Wesley Ivan Hurt, Sep 21 2017
a(n+m) = a(n)*a(m) + a(n) + a(m). - Yuchun Ji, Jul 27 2018
a(n+m) = a(n+1)*a(m) - 2*a(n)*a(m-1). - Taras Goy, Dec 23 2018
a(n+1) is the determinant of n X n matrix M_(i, j) = binomial(i + j - 1, j)*2 + binomial(i+j-1, i) (empirical observation). - Tony Foster III, May 11 2019
From Peter Bala, Jun 27 2025: (Start)
For n >= 1, a(3*n)/a(n) = A001576(n), a(4*n)/a(n) = A034496(n), a(5*n)/a(n) = A020514(n) a(6*n)/a(n) = A034665(n), a(7*n)/a(n) = A020516(n) and a(8*n)/a(n) = A034674(n).
exp( Sum_{n >= 1} a(2*n)/a(n)*x^n/n ) = Sum_{n >= 0} a(n+1)*x^n.
Modulo differences in offsets, exp( Sum_{n >= 1} a(k*n)/a(n)*x^n/n ) is the o.g.f. of A006095 (k = 3), A006096 (k = 4), A006097 (k = 5), A006110 (k = 6), A022189 (k = 7), A022190 (k = 8), A022191 (k = 9) and A022192 (k = 10).
The following are all examples of telescoping series:
Sum_{n >= 1} 2^n/(a(n)*a(n+1)) = 1; Sum_{n >= 1} 2^n/(a(n)*a(n+1)*a(n+2)) = 1/9.
In general, for k >= 1, Sum_{n >= 1} 2^n/(a(n)*a(n+1)*...*a(n+k)) = 1/(a(1)*a(2)*...*a(k)*a(k)).
Sum_{n >= 1} 2^n/(a(n)*a(n+2)) = 4/9, since 2^n/(a(n)*a(n+2)) = b(n) - b(n+1), where b(n) = (2/3)*(3*2^(n-1) - 1)/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+2)) = -2/9, since (-2)^n/(a(n)*a(n+2)) = c(n) - c(n+1), where c(n) = (1/3)*(-2)^n/((2^(n+1) - 1)*(2^n - 1)).
Sum_{n >= 1} 2^n/(a(n)*a(n+4)) = 18/175, since 2^n/(a(n)*a(n+4)) = d(n) - d(n+1), where d(n) = (120*8^n - 140*4^n + 45*2^n - 4)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)).
Sum_{n >= 1} (-2)^n/(a(n)*a(n+4)) = -26/525, since (-2)^n/(a(n)*a(n+4)) = e(n) - e(n+1), where e(n) = (-1)^n*(40*8^n - 24*4^n + 5*2^n)/(15*(2^n - 1)*(2^(n+1) - 1)*(2^(n+2) - 1)*(2^(n+3) - 1)). (End)

Name partially edited by Eric W. Weisstein, Sep 04 2021

cp's OEIS Frontend

A046970 Dirichlet inverse of the Jordan function J_2 (A007434).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A301876 Expansion of Product_{k>=1} (1 + x^k)^A007434(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A379716 The second Jordan totient function applied to the powerful numbers: a(n) = A007434(A001694(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A379718 The second Jordan totient function applied to the cubefull numbers: a(n) = A007434(A036966(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A301875 Expansion of Product_{k>=1} 1/(1 - x^k)^A007434(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A321322 a(n) = Sum_{d|n} mu(n/d)*J_2(d), where J_2() is the Jordan function (A007434).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A323399 Sum of Jordan function J_2(n), A007434 and its Dirichlet inverse, A046970.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A220345 Ratio of Jordan's totient to Carmichael's lambda function: a(n) = A007434(n) / A002322(n).

Views