cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 11 results. Next

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

			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)

References

  • 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.

Links

Crossrefs

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).

Programs

  • Axiom
    [eulerPhi(n) for n in 1..100]
  • Haskell
    a n = length (filter (==1) (map (gcd n) [1..n])) -- Allan C. Wechsler, Dec 29 2014
  • Julia
    # 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
  • Magma
    [ EulerPhi(n) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
  • Maple
    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]
  • Maxima
    makelist(totient(n),n,0,1000); /* Emanuele Munarini, Mar 26 2011 */
  • PARI
    {a(n) = if( n==0, 0, eulerphi(n))}; /* Michael Somos, Feb 05 2011 */
  • Python
    from sympy.ntheory import totient
print([totient(i) for i in range(1, 70)])  # Indranil Ghosh, Mar 17 2017
  • Python
    # Note also the implementation in A365339.
  • Sage
    def A000010(n): return euler_phi(n) # Jaap Spies, Jan 07 2007
  • Sage
    [euler_phi(n) for n in range(1, 70)]  # Zerinvary Lajos, Jun 06 2009

Formula

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]

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

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

Examples

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

References

  • Peter Giblin, Primes and Programming: An Introduction to Number Theory with Computing. Cambridge: Cambridge University Press (1993) p. 116, Exercise 1.10.
  • J. L. Lagrange, Oeuvres, Vol. III Paris 1869.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

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

Programs

Formula

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

Extensions

Better description from Labos Elemer, Feb 18 2000

A005598 a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).

Original entry on oeis.org

1, 2, 4, 8, 14, 24, 36, 54, 76, 104, 136, 178, 224, 282, 346, 418, 498, 594, 696, 816, 944, 1084, 1234, 1406, 1586, 1786, 1998, 2228, 2470, 2740, 3018, 3326, 3650, 3994, 4354, 4738, 5134, 5566, 6016, 6490, 6980, 7510, 8052, 8636, 9240, 9868, 10518, 11214
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of possible interleaving orders for n consecutive distinct values from two arithmetic progressions. ABABBBA is impossible, for example, because "ABA" implies that the spacing between B's must be greater than 1/2 the spacing between A's. But "ABBBA" implies that the B-spacing must be less than 1/2 the A-spacing. - Allan C. Wechsler, Mar 16 2005. Since the interchange of A's and B's gives essentially the same order pattern, all terms will be even for n>0.
The SemialgebraicComponents procedure in the Algebra`AlgebraicInequalities` package of Mathematica may be used to determine whether a particular pattern is possible. - John W. Layman, Mar 30 2005
Also, "digital lines": number of straight binary strings of length n [Dorst]. This was the original source for this sequence.
Also, the number of finite Sturmian words of length n. The considered orders are exactly the balanced words, which have been proved to be the factors of Sturmian sequences. An explicit formula was exhibited by Mignosi in 1991. Berstel and Pocchiola gave a geometric proof of this, using Euler's function for counting partitions of a unit cube. - Damien Jamet (jamet(AT)lirmm.fr), Apr 01 2005
The first difference of a(n) is the number of 'special' words, prefix of two Sturmian words of length n+1; see A002088. The second difference of a(n) is the number of palindromic 'bispecial' words, prefix and suffix of two Sturmian words of length n+1; see A000010. - Fred Lunnon, Sep 05 2010
Conjectured to be the number of regions in a Farey fan of order n. See A360042 for further details. - Scott R. Shannon, Jan 24 2023

Examples

			a(4) = 14 because of the 16 possible four-letter words from an alphabet of two letters, only AABB and BBAA are not possible interleaving orders for two arithmetic progressions.
For n=7, the pattern BAAAABA gives a possible ordering for the two arithmetic progressions {A, A+a, A+2a, A+3a,...} and {B, B+b, B+2b, B+3b,...} if the system of inequalities {a>0, b>0, A<B, B < A+a, A+4a<B+b, B+b < A+5a, A+5a<B+2b} has a solution. (Note: A<B is included to preclude a fifth A-term from lying between the two B-terms; similarly, A+5a<B+2b is included to preclude a second B-term from lying between the final two A-terms.) The SemialgebraicComponents procedure gives the solution {A,a,B,b}={0,1,1/8,4}; thus BAAAABA is one of the 54 possible orders of length 7. - _John W. Layman_, Mar 30 2005

References

  • L. Dorst and A. W. M. Smeulders, Discrete straight line segments: parameters, primitives and properties. Vision geometry (Hoboken, NJ, 1989), 45-62, Contemp. Math., 119, Amer. Math. Soc., Providence, RI, 1991.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000010, A002088, A011755, A049695, A049703, A103116.

Programs

  • Haskell
    a005598 n = 1 + sum (zipWith (*) [n, n - 1 .. 1] a000010_list)
-- Reinhard Zumkeller, Apr 14 2013
  • Magma
    A005598:= func< n | n eq 0 select 1 else 1 +(&+[(n-j+1)*EulerPhi(j): j in [1..n]]) >;
[A005598(n): n in [0..60]]; // G. C. Greubel, Dec 07 2022
  • Maple
    f:= m -> add((m-i+1)*phi(i),i=1..m)+1; (Jamet)
  • Mathematica
    Accumulate@Accumulate@EulerPhi@Range[0,100]+1 (* Vladimir Joseph Stephan Orlovsky, Apr 21 2011 *)
Nest[Accumulate[#]&,EulerPhi[Range[0,50]],2]+1 (* Harvey P. Dale, Feb 07 2015 *)
  • PARI
    a(n) = 1 + sum(i=1, n, (n-i+1)*eulerphi(i)); \\ Michel Marcus, Aug 04 2016
  • SageMath
    @CachedFunction
def A005598(n): return 1 + sum( (n-j+1)*euler_phi(j) for j in range(1,n+1) )
[A005598(n) for n in range(61)] # G. C. Greubel, Dec 07 2022

Formula

a(n) = 2*A049703(n) for n >= 1.
a(n) = Sum_{i=0..n} A049695(i,n-i). - Clark Kimberling
Asymptotically, a(n) behaves like n^3/Pi^2. - Leo Dorst (leo(AT)science.uva.nl), Apr 02 2007
G.f.: 1/(1 - x) + (1/(1 - x)^2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 16 2017
a(n) = 1 + (n+1)*A002088(n) - A011755(n). - G. C. Greubel, Dec 07 2022

Extensions

Extended by John W. Layman, Mar 30 2005
More terms from Emeric Deutsch, Feb 04 2006
Entry revised by N. J. A. Sloane, Apr 04 2007
Minor English revisions by Jeffrey Shallit, Aug 04 2016

A240877 Sum of the denominators of the Farey series of order n (A006843).

Original entry on oeis.org

1, 2, 4, 10, 18, 38, 50, 92, 124, 178, 218, 328, 376, 532, 616, 736, 864, 1136, 1244, 1586, 1746, 1998, 2218, 2724, 2916, 3416, 3728, 4214, 4550, 5362, 5602, 6532, 7044, 7704, 8248, 9088, 9520, 10852, 11536, 12472, 13112, 14752, 15256, 17062, 17942, 19022, 20034, 22196, 22964, 25022, 26022
Offset: 0

Views

Author

Robert G. Wilson v, Apr 13 2014

Keywords

Comments

All terms except a(0) are even.

Links

Crossrefs

Cf. A000010, A006842, A006843, A011755, A185197, A213544.

Programs

  • Mathematica
    Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Table[ Total[ Denominator[ Farey[ n]]], {n, 0, 50}]
  • PARI
    first(n)=my(s=1,v=vector(n+1)); v[1]=1; forfactored(k=1,n, v[k[1]+1]=s+=k[1]*eulerphi(k)); v \\ Charles R Greathouse IV, Dec 27 2017

Formula

a(n) = 1 + Sum_{k=1..n} k*A000010(k). - Isaac Saffold, Dec 03 2017
a(n) = 1 + A011755(n). - Michel Marcus, Dec 23 2017
a(n) ~ c * n^3, where c = 2/Pi^2 (A185197). - Amiram Eldar, Dec 01 2023

A319087 a(n) = Sum_{k=1..n} k^2*phi(k), where phi is the Euler totient function A000010.

Original entry on oeis.org

1, 5, 23, 55, 155, 227, 521, 777, 1263, 1663, 2873, 3449, 5477, 6653, 8453, 10501, 15125, 17069, 23567, 26767, 32059, 36899, 48537, 53145, 65645, 73757, 86879, 96287, 119835, 127035, 155865, 172249, 194029, 212525, 241925, 257477, 306761, 332753, 369257
Offset: 1

Views

Author

Vaclav Kotesovec, Sep 10 2018

Keywords

Comments

Comment from N. J. A. Sloane, Mar 22 2020: (Start)
Theorem: Sum_{ 1<=i<=n, 1<=j<=n, gcd(i,j)=1 } i*j = a(n).
Proof: From the Apostol reference we know that:
Sum_{ 1<=i<=n, gcd(i,n)=1 } i = n*phi(n)/2 (see A023896).
We use induction on n. The result is true for n=1.
Then a(n) - a(n-1) = 2*Sum_{ i=1..n-1, gcd(i,n)=1 } n*i = n^2*phi(n). QED (End)

References

  • T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).

Links

Crossrefs

Cf. A000010, A002088, A011755, A023896, A053191.

Programs

  • Mathematica
    Accumulate[Table[k^2*EulerPhi[k], {k, 1, 50}]]
  • PARI
    a(n) = sum(k=1, n, k^2*eulerphi(k)); \\ Michel Marcus, Sep 12 2018

Formula

a(n) ~ 3*n^4 / (2*Pi^2).

A213544 Sum of numerators of Farey Sequence of order n.

Original entry on oeis.org

1, 2, 5, 9, 19, 25, 46, 62, 89, 109, 164, 188, 266, 308, 368, 432, 568, 622, 793, 873, 999, 1109, 1362, 1458, 1708, 1864, 2107, 2275, 2681, 2801, 3266, 3522, 3852, 4124, 4544, 4760, 5426, 5768, 6236, 6556, 7376, 7628, 8531, 8971, 9511, 10017, 11098, 11482
Offset: 1

Views

Author

Anunay Kulshrestha, Jun 14 2012

Keywords

Examples

			For n = 3, the Farey Sequence is 0/1, 1/3, 1/2, 2/3, 1/1. Thus a(3) = 0 + 1 + 1 + 2 + 1 = 5.

Links

Crossrefs

Similar to A133404 and A191607.
Partial sums of A023896.
Cf. A006842, A006843, A011755, A240877.

Programs

  • Maple
    with(numtheory):
b:= n-> `if`(n=1, 1, n*phi(n)/2):
a:= proc(n) option remember; b(n) +`if`(n>1, a(n-1), 0) end:
seq(a(n), n=1..60);  # Alois P. Heinz, Jun 14 2012
  • Mathematica
    Farey[n_] := Union[ Flatten[ Join[{0}, Table[a/b, {b, n}, {a, b}]]]]; Table[ Total[ Numerator[ Farey[ n]]], {n, 0, 53}] (* Robert G. Wilson v, Apr 15 2014 *)
a[n_] := Sum[If[CoprimeQ[j, k], j, 0], {k, 1, n}, {j, 1, k}]; Table[a[n], {n, 1, 48}] (* Jean-François Alcover, Dec 29 2014 *)
Table[Total[Numerator[FareySequence[n]]],{n,50}] (* Harvey P. Dale, Apr 21 2025 *)

Formula

a(n) = Sum_{k=1..n} A023896(k).
a(n) = A240877(n)/2. - Robert G. Wilson v, Apr 15 2014
a(n) ~ n^3/Pi^2 - Jean-François Alcover, Dec 29 2014
a(n) = (A011755(n)+1)/2. - Chai Wah Wu, Apr 04 2022

A049703 a(0) = 0; for n>0, a(n) = A005598(n)/2.

Original entry on oeis.org

0, 1, 2, 4, 7, 12, 18, 27, 38, 52, 68, 89, 112, 141, 173, 209, 249, 297, 348, 408, 472, 542, 617, 703, 793, 893, 999, 1114, 1235, 1370, 1509, 1663, 1825, 1997, 2177, 2369, 2567, 2783, 3008, 3245, 3490, 3755, 4026, 4318
Offset: 0

Views

Author

Clark Kimberling

Keywords

Links

Crossrefs

Cf. A005598, A046657, A049695.

Programs

  • Magma
    A049703:= func< n | n eq 0 select 0 else (1 +(&+[(n-j+1)*EulerPhi(j): j in [1..n]]))/2 >;
[A049703(n): n in [0..60]]; // G. C. Greubel, Dec 08 2022
  • Mathematica
    A005598[n_]:= A005598[n]= 1 +Sum[(n-j+1)*EulerPhi[j], {j,n}];
A049703[n_]:= If[n==0, 0, A005598[n]/2];
Table[A049703[n], {n,0,50}] (* G. C. Greubel, Dec 08 2022 *)
  • SageMath
    @CachedFunction
def A049703(n): return 0 if (n==0) else (1 + sum((n-j+1)*euler_phi(j) for j in range(1,n+1)))/2
[A049703(n) for n in range(61)] # G. C. Greubel, Dec 08 2022

Formula

a(n) = (1/2)*Sum_{j=0..n} T(j, n-j), for array T in A049695.
a(n) = (1/2)*(1 + (n+1)*A002088(n) - A011755(n)), with a(0) = 0. - G. C. Greubel, Dec 08 2022

Extensions

Edited by N. J. A. Sloane, Apr 04 2007.

A333291 a(n) = Sum_{i=1..n, gcd(i,n)=1} i*phi(i) where phi is Euler's totient function A000010.

Original entry on oeis.org

1, 1, 3, 7, 17, 21, 49, 69, 105, 103, 217, 173, 375, 347, 435, 509, 863, 601, 1243, 983, 1271, 1265, 2217, 1449, 2575, 2225, 2935, 2573, 4549, 2241, 5601, 4609, 5195, 4997, 6453, 4531, 9519, 7099, 8457, 6897, 13111, 6621, 15255, 11053, 11691, 12397, 20033, 11471, 20905, 14563, 19307, 17663, 28901, 16285, 26119
Offset: 1

Views

Author

N. J. A. Sloane, Mar 22 2020

Keywords

Links

Crossrefs

Suggested by A023896 and A319087.
Cf. A000010, A011755.

Programs

  • Maple
    a:= n-> add(`if`(igcd(i, n)=1, i*numtheory[phi](i), 0), i=1..n):
seq(a(n), n=1..55);  # Alois P. Heinz, Mar 22 2020
  • Mathematica
    a[n_] := Sum[If[CoprimeQ[i, n], i * EulerPhi[i], 0], {i, 1, n}]; Array[a, 100] (* Amiram Eldar, Dec 01 2024 *)
  • PARI
    a(n) = sum(i=1, n, if (gcd(n, i) == 1, i*eulerphi(i))); \\ Michel Marcus, Mar 23 2020

A344526 a(n) = Sum_{k=1..n} k^3 * phi(k).

Original entry on oeis.org

1, 9, 63, 191, 691, 1123, 3181, 5229, 9603, 13603, 26913, 33825, 60189, 76653, 103653, 136421, 215029, 250021, 373483, 437483, 548615, 655095, 922769, 1033361, 1345861, 1556773, 1911067, 2174491, 2857383, 3073383, 3967113, 4491401, 5210141, 5839005, 6868005, 7427877, 9251385
Offset: 1

Views

Author

Seiichi Manyama, May 22 2021

Keywords

Crossrefs

Cf. A000010, A011755, A068970, A319087, A344522.

Programs

  • Mathematica
    a[n_] := Sum[k^3 * EulerPhi[k], {k, 1, n}]; Array[a, 40] (* Amiram Eldar, May 22 2021 *)
Accumulate[Table[k^3*EulerPhi[k], {k, 1, 40}]] (* Vaclav Kotesovec, May 22 2021 *)
  • PARI
    a(n) = sum(k=1, n, k^3*eulerphi(k));

Formula

a(n) ~ 6*n^5 / (5*Pi^2). - Vaclav Kotesovec, May 22 2021

A305397 Let k be the maximal number of vertices in an n X n lattice grid that form a convex polygon, then a(n) = floor(k/2).

Original entry on oeis.org

2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9, 10, 10, 10, 11, 12
Offset: 1

Views

Author

N. J. A. Sloane, Jun 27 2018

Keywords

Examples

			In a 3x3 square cells grid (which is rather 4x4 in the terms of vertices), one can choose eight vertices forming a convex octagon (namely, all non-corner boundary vertices) but no nine vertices to form a convex nonagon, therefore a(3) = floor(8/2) = 4, the "edge-diameter" of the octagon.

Links

  • Antoine Deza, George Manoussakis, Shmuel Onn, Primitive Zonotopes, Discrete & Computational Geometry, 60 (No. 1, 2018), 40-56; arXiv preprint arXiv:1512.08018 [math.OC], 2015-2017. See Table 1.

Crossrefs

Cf. A011755, A049696, A374975.

Formula

a(A011755(n)) = A049696(n). [Deza et al., Proposition 3.1] - Andrey Zabolotskiy, Sep 27 2024

Extensions

Name clarified by Andrey Zabolotskiy, Sep 27 2024
Showing 1-10 of 11 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.