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

A001065 Sum of proper divisors (or aliquot parts) of n: sum of divisors of n that are less than n.

Original entry on oeis.org

0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, 1, 10, 9, 15, 1, 21, 1, 22, 11, 14, 1, 36, 6, 16, 13, 28, 1, 42, 1, 31, 15, 20, 13, 55, 1, 22, 17, 50, 1, 54, 1, 40, 33, 26, 1, 76, 8, 43, 21, 46, 1, 66, 17, 64, 23, 32, 1, 108, 1, 34, 41, 63, 19, 78, 1, 58, 27, 74, 1, 123, 1, 40, 49, 64, 19, 90, 1, 106

Offset: 1

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

Also total number of parts in all partitions of n into equal parts that do not contain 1 as a part. - Omar E. Pol, Jan 16 2013
Related concepts: If a(n) < n, n is said to be deficient, if a(n) > n, n is abundant, and if a(n) = n, n is perfect. If there is a cycle of length 2, so that a(n) = b and a(b) = n, b and n are said to be amicable. If there is a longer cycle, the numbers in the cycle are said to be sociable. See examples. - Juhani Heino, Jul 17 2017
Sum of the smallest parts in the partitions of n into two parts such that the smallest part divides the largest. - Wesley Ivan Hurt, Dec 22 2017
a(n) is also the total number of parts congruent to 0 mod k in the partitions of k*n into equal parts that do not contain k as a part (the comment dated Jan 16 2013 is the case for k = 1). - Omar E. Pol, Nov 23 2019
Fixed points are in A000396. - Alois P. Heinz, Mar 10 2024

			x^2 + x^3 + 3*x^4 + x^5 + 6*x^6 + x^7 + 7*x^8 + 4*x^9 + 8*x^10 + x^11 + ...
For n = 44, sum of divisors of n = sigma(n) = 84; so a(44) = 84-44 = 40.
Related concepts: (Start)
From 1 to 17, all n are deficient, except 6 and 12 seen below. See A005100.
Abundant numbers: a(12) = 16, a(18) = 21. See A005101.
Perfect numbers: a(6) = 6, a(28) = 28. See A000396.
Amicable numbers: a(220) = 284, a(284) = 220. See A259180.
Sociable numbers: 12496 -> 14288 -> 15472 -> 14536 -> 14264 -> 12496. See A122726. (End)
For n = 10 the sum of the divisors of 10 that are less than 10 is 1 + 2 + 5 = 8. On the other hand, the partitions of 10 into equal parts that do not contain 1 as a part are [10], [5,5], [2,2,2,2,2], there are 8 parts, so a(10) = 8. - _Omar E. Pol_, Nov 24 2019

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.
George E. Andrews, Number Theory. New York: Dover, 1994; Pages 1, 75-92; p. 92 #15: Sigma(n) / d(n) >= n^(1/2).
Carl Pomerance, The first function and its iterates, pp. 125-138 in Connections in Discrete Mathematics, ed. S. Butler et al., Cambridge, 2018.
H. J. J. te Riele, Perfect numbers and aliquot sequences, pp. 77-94 in J. van de Lune, ed., Studieweek "Getaltheorie en Computers", published by Math. Centrum, Amsterdam, Sept. 1980.
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 91.

T. D. Noe, Table of n, a(n) for n = 1..10000
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972. [alternative scanned copy].
Joerg Arndt, On computing the generalized Lambert series, arXiv:1202.6525v3 [math.CA], (2012).
Henry Bottomley, Illustration of initial terms
K. Chum, R. K. Guy, M. J. Jacobson, Jr., and A. S. Mosunov, Numerical and statistical analysis of aliquot sequences, Exper. Math. 29 (2020), no. 4, 414-425; arXiv:2110.14136, Oct. 2021 [math.NT].
Don Coppersmith, An answer to the problem of Don Saari, 1987.
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]
Passawan Noppakaew and Prapanpong Pongsriiam, Product of Some Polynomials and Arithmetic Functions, J. Int. Seq. (2023) Vol. 26, Art. 23.9.1.
P. Pollack and C. Pomerance, Some problems of Erdős on the sum-of-divisors function, For Richard Guy on his 99th birthday: May his sequence be unbounded, Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26; errata.
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, Sums of Restricted Divisors for n=1 to 1000
F. Richman, Aliquot series: Abundant, deficient, perfect
Eric Weisstein's World of Mathematics, Restricted Divisor Function
Eric Weisstein's World of Mathematics, Divisor Function
Index entries for "core" sequences

Least inverse: A070015, A359132.
Values taken: A078923, values not taken: A005114.
Records: A034090, A034091.
First differences: A053246, partial sums: A153485.
a(n) = n - A033879(n) = n + A033880(n). - Omar E. Pol, Dec 30 2013
Row sums of A141846 and of A176891. - Gary W. Adamson, May 02 2010
Row sums of A176079. - Mats Granvik, May 20 2012
Alternating row sums of A231347. - Omar E. Pol, Jan 02 2014
a(n) = sum (A027751(n,k): k = 1..A000005(n)-1). - Reinhard Zumkeller, Apr 05 2013
For n > 1: a(n) = A240698(n,A000005(n)-1). - Reinhard Zumkeller, Apr 10 2014
A134675(n) = A007434(n) + a(n). - Conjectured by John Mason and proved by Max Alekseyev, Jan 07 2015
Cf. A032741, A000203, A048050, A000593, A027750.
Cf. A051953, A051731.
Cf. A037020 (primes), A053868, A053869 (odd and even terms).
Cf. A048138 (number of occurrences), A238895, A238896 (record values thereof).
Cf. A007956 (products of proper divisors).
Cf. A005100, A005101, A000396, A259180, A122726 (related concepts).

a001065 n = a000203 n - n  -- Reinhard Zumkeller, Sep 15 2011

[SumOfDivisors(n)-n: n in [1..100]]; // Vincenzo Librandi, May 06 2015

A001065 := proc(n)
    numtheory[sigma](n)-n ;
end proc:
seq( A001065(n),n=1..100) ;

Table[ Plus @@ Select[ Divisors[ n ], #Zak Seidov, Sep 10 2009 *)
Table[DivisorSigma[1, n] - n, {n, 1, 80}] (* Jean-François Alcover, Apr 25 2013 *)
Array[Plus @@ Most@ Divisors@# &, 80] (* Robert G. Wilson v, Dec 24 2017 *)

numlib::sigma(n)-n$ n=1..81 // Zerinvary Lajos, May 13 2008

{a(n) = if( n==0, 0, sigma(n) - n)} /* Michael Somos, Sep 20 2011 */

from sympy import divisor_sigma
def A001065(n): return divisor_sigma(n)-n # Chai Wah Wu, Nov 04 2022

[sigma(n, 1)-n for n in range(1, 81)] # Stefano Spezia, Jul 14 2025

G.f.: Sum_{k>0} k * x^(2*k)/(1 - x^k). - Michael Somos, Jul 05 2006
a(n) = sigma(n) - n = A000203(n) - n. - Lekraj Beedassy, Jun 02 2005
a(n) = A155085(-n). - Michael Somos, Sep 20 2011
Equals inverse Mobius transform of A051953 = A051731 * A051953. Example: a(6) = 6 = (1, 1, 1, 0, 0, 1) dot (0, 1, 1, 2, 1, 4) = (0 + 1 + 1 + 0 + 0 + 4), where A051953 = (0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, ...) and (1, 1, 1, 0, 0, 1) = row 6 of A051731 where the 1's positions indicate the factors of 6. - Gary W. Adamson, Jul 11 2008
a(n) = A006128(n) - A220477(n) - n. - Omar E. Pol Jan 17 2013
a(n) = Sum_{i=1..floor(n/2)} i*(1-ceiling(frac(n/i))). - Wesley Ivan Hurt, Oct 25 2013
Dirichlet g.f.: zeta(s-1)*(zeta(s) - 1). - Ilya Gutkovskiy, Aug 07 2016
a(n) = 1 + A048050(n), n > 1. - R. J. Mathar, Mar 13 2018
Erdős (Elem. Math. 28 (1973), 83-86) shows that the density of even integers in the range of a(n) is strictly less than 1/2. The argument of Coppersmith (1987) shows that the range of a(n) has density at most 47/48 < 1. - N. J. A. Sloane, Dec 21 2019
G.f.: Sum_{k >= 2} x^k/(1 - x^k)^2. Cf. A296955. (This follows from the fact that if g(z) = Sum_{n >= 1} a(n)*z^n and f(z) = Sum_{n >= 1} a(n)*z^(N*n)/(1 - z^n) then f(z) = Sum_{k >= N} g(z^k), taking a(n) = n and N = 2.) - Peter Bala, Jan 13 2021
Faster converging g.f.: Sum_{n >= 1} q^(n*(n+1))*(n*q^(3*n+2) - (n + 1)*q^(2*n+1) - (n - 1)*q^(n+1) + n)/((1 - q^n)*(1 - q^(n+1))^2). (In equation 1 in Arndt, after combining the two n = 0 summands to get -t/(1 - t), apply the operator t*d/dt to the resulting equation and then set t = q and x = 1.) - Peter Bala, Jan 22 2021
a(n) = Sum_{d|n} d * (1 - [n = d]), where [ ] is the Iverson bracket. - Wesley Ivan Hurt, Jan 28 2021
a(n) = Sum_{i=1..n} ((n-1) mod i) - (n mod i). [See also A176079.] - José de Jesús Camacho Medina, Feb 23 2021

A246655 Prime powers: numbers of the form p^k where p is a prime and k >= 1.

Original entry on oeis.org

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

Offset: 1

Peter Luschny and Franklin T. Adams-Watters, Sep 01 2014

The elements are called prime powers in contrast to the powers of primes which are the numbers of the same form but with k >= 0, cf. A000961.
Every nonzero integer is the product of elements of this sequence which are relatively prime and an element of {-1, 1}. This product is up to a rearrangement of the factors unique. (This statement is the fundamental theorem of arithmetic.)
These numbers are the numbers such that the von Mangoldt function is nonzero.
These numbers are the numbers of elements in finite fields. - Franz Vrabec, Aug 11 2004
A positive integer n is a prime power if and only if nZ is a primary ideal of Z. - John Cremona, Sep 02 2014
Also, numbers n divisible by their cototients A051953(n). - Ivan Neretin, May 29 2016
Numbers n such that (theta_3(q) - theta_3(q^n)) / 2 is the g.f. of a multiplicative sequence. - Michael Somos, Oct 17 2016
Numbers that are evenly divisible by exactly one prime number. - Lee A. Newberg, May 07 2018
Ram proved that these are precisely the numbers n such that the binomial coefficients n!/(m!(n-m)!) for m = 1..n-1 have a common factor greater than 1 (which is the unique prime dividing n). See Joris, Oestreicher & Steinig for a generalization. - Charles R Greathouse IV, Apr 24 2019
Blagojević & Ziegler prove that for these n and for any convex polygon in the plane, the polygon can be partitioned into n polygons with equal area and equal perimeter. The result is conjectured (by Nandakumar & Rao, who proved the case n = 2) to hold for all n. - Charles R Greathouse IV, Apr 24 2019
Numbers n such that A367064(n) < 0. - Chai Wah Wu, Nov 06 2023
This sequence represents all positive high amplitude peaks of the inverse Riemann spectrum R(x)= Sum_{k=1..oo} -cos(log(x)*Im(z_k)) going over the imaginary part of the nontrivial zeros "Im(z_k)" in the Riemann zeta function. - Marc Morgenegg, Jul 29 2025

Robert Israel, Table of n, a(n) for n = 1..10000
Brady Haran and Günter Ziegler, Cannons and Sparrows, Numberphile video (2018)
H. Joris, C. Oestreicher and J. Steinig, The greatest common divisor of certain sets of binomial coefficients, Journal of Number Theory 21 (1985), pp. 101-119.
Pavle V. M. Blagojević and Günter M. Ziegler, Convex equipartitions via equivariant obstruction theory, arXiv:1202.5504 [math.AT], 2012-2013; Israel Journal of Mathematics 200:1 (June 2014), pp 49-77.
Karl-Heinz Kuhl, Inverse Riemann Spectrum
Hans Montanus and Ron Westdijk, Cellular Automation and Binomials, Green Blue Mathematics (2022), p. 90.
Laurentiu Panaitopol, Some of the properties of the sequence of powers of prime numbers, Rocky Mountain Journal of Mathematics, Volume 31, Number 4, Winter 2001.
Balak Ram, Common factors of n!/(m!(n-m)!), (m = 1, 2, ... n-1), Journal of the Indian Mathematical Club (Madras) 1 (1909), pp. 39-43.
Eric Weisstein's World of Mathematics, Prime Power
Eric Weisstein's World of Mathematics, Projective Plane
Chai Wah Wu, Algorithms for complementary sequences, arXiv:2409.05844 [math.NT], 2024.
Wikipedia, Prime power
Index entries for "core" sequences

There are four different sequences which may legitimately be called "prime powers": A000961 (p^k, k >= 0), A246655 (p^k, k >= 1), A246547 (p^k, k >= 2), A025475 (p^k, k=0 and k >= 2). When you refer to "prime powers", be sure to specify which of these you mean. Also A001597 is the sequence of nontrivial powers n^k, n >= 1, k >= 2. - N. J. A. Sloane, Mar 24 2018
Cf. A001221, A014963, A069513, A367064.
Partial sums of A275120.

select(t -> nops(numtheory:-factorset(t))=1, [$1..1000]); # Robert Israel, Sep 01 2014
A246655 := proc(n) A000961(n+1) end proc: # R. J. Mathar, Jan 09 2017
isprimepower := n -> nops(NumberTheory:-PrimeFactors(n)) = 1: # Peter Luschny, Oct 09 2022

Mathematica
```
Select[Range[222], PrimePowerQ]
```
PARI
```
[p| p <- [1..222], isprimepower(p)]
```

list(lim)=my(v=List(primes([2,lim\=1]))); for(e=2,logint(lim,2), forprime(p=2,sqrtnint(lim,e), listput(v,p^e))); Set(v) \\ Charles R Greathouse IV, Feb 03 2023

from sympy import primerange
m = 10**5
A246655 = []
for p in primerange(1,m):
    pe = p
    while pe < m:
        A246655.append(pe)
        pe *= p
A246655 = sorted(A246655) # Chai Wah Wu, Sep 04 2014

from sympy import primepi, integer_nthroot
def A246655(n):
    def f(x): return int(n-1+x-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    kmin, kmax = 1,2
    while f(kmax) >= kmax:
        kmax <<= 1
    while True:
        kmid = kmax+kmin>>1
        if f(kmid) < kmid:
            kmax = kmid
        else:
            kmin = kmid
        if kmax-kmin <= 1:
            break
    return kmax # Chai Wah Wu, Aug 20 2024

[n for n in (1..222) if sloane.A001221(n) == 1]

a(n) is characterized by A001221(a(n)) = 1.
a(n) is characterized by A014963(a(n)) != 1.
Euler's A000010(a(n)) = a(n)*(1 - 1/A014963(a(n))).
All three relations above are not true for A000961(n) instead of a(n).
Sum_{k=1..n} 1/a(k) ~ log(log(a(n))) + A077761 + A136141. - François Huppé, Jul 31 2024

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

Original entry on oeis.org

0, 1, 2, 2, 4, 3, 8, 3, 4, 5, 16, 4, 32, 9, 6, 4, 64, 5, 128, 6, 10, 17, 256, 5, 8, 33, 6, 10, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.
However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.
The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020
If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024

			From _Gus Wiseman_, May 22 2024: (Start)
The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
   30: {1,2,3}
   40: {1,1,1,3}
   54: {1,2,2,2}
   72: {1,1,1,2,2}
   96: {1,1,1,1,1,2}
  128: {1,1,1,1,1,1,1}
(End)

Antti Karttunen, Table of n, a(n) for n = 1..1024
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]

Row 2 of A104244.
Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.
Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.
A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.
Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.
Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A248692,A056239), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).
See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.
The formula section details how the sequence maps the terms of A329050, A329332.
A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.
The term k appears A018819(k) times.
The inverse transformation is A019565 (Heinz number of binary indices).
The version for distinct prime indices is A087207.
Numbers k such that a(k) is prime are A277319, counts A372688.
Grouping by image gives A277905.
A014499 lists binary indices of prime numbers.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
Binary indices:
- listed A048793, sum A029931
- reversed A272020
- opposite A371572, sum A230877
- length A000120, complement A023416
- min A001511, opposite A000012
- max A070939, opposite A070940
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
Cf. A000720, A035100, A071814, A096111, A225620, A243055, A304818, A355536, A358136, A372890.
Cf. A087207, A097248.

nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.
A048675 := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;
# simpler alternative
f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
map(f, [$1..100]); # Robert Israel, Oct 10 2016

a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-François Alcover, Mar 15 2016 *)

a(n) = my(f = factor(n)); sum(k=1, #f~, f[k,2]*2^primepi(f[k,1]))/2; \\ Michel Marcus, Oct 10 2016

\\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
v048675sigs = readvec("a048675.txt");
A048675(n) = if(n<=2,n-1,my(prsig=v048675sigs[n],ps=prsig[1],es=prsig[2]); prod(i=1,#ps,ps[i]^es[i])); \\ Antti Karttunen, Feb 02 2020

from sympy import factorint, primepi
def a(n):
    if n==1: return 0
    f=factorint(n)
    return sum([f[i]*2**(primepi(i) - 1) for i in f])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jun 19 2017

a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).
Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by Antti Karttunen, Jul 29 2015]
From Antti Karttunen, Jul 29 2015: (Start)
a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]
a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).
Other identities. For all n >= 0:
a(A019565(n)) = n.
a(A260443(n)) = n.
a(A206296(n)) = A000129(n).
a(A005940(n+1)) = A087808(n).
a(A007913(n)) = A248663(n).
a(A007947(n)) = A087207(n).
a(A283477(n)) = A005187(n).
a(A284003(n)) = A006068(n).
a(A285101(n)) = A028362(1+n).
a(A285102(n)) = A068052(n).
Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)
a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - Antti Karttunen, Oct 11 2016
From Peter Munn, Jan 31 2020: (Start)
a(n^2) = a(A003961(n)) = 2 * a(n).
a(A297845(n,k)) = a(n) * a(k).
a(n) = a(A225546(n)).
a(A329332(n,k)) = n * k.
a(A329050(n,k)) = 2^(n+k).
(End)
From Antti Karttunen, Feb 02-25 2020, Feb 01 2021: (Start)
a(n) = Sum_{d|n} A297108(d) = Sum_{d|A225546(n)} A297108(d).
a(n) = a(A097248(n)).
For n >= 2:
A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).
A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).
For n >= 1, A331750(n) = a(A000203(n)).
For n >= 1, the following chains hold:
A293447(n) >= a(n) >= A331740(n) >= A331591(n).
a(n) >= A087207(n) >= A248663(n).
(End)
a(n) = A087207(A097248(n)). - Flávio V. Fernandes, Jul 16 2025

Entry revised by Antti Karttunen, Jul 29 2015

More linking formulas added by Antti Karttunen, Apr 18 2017

A049820 a(n) = n - d(n), where d(n) is the number of divisors of n (A000005).

Original entry on oeis.org

0, 0, 1, 1, 3, 2, 5, 4, 6, 6, 9, 6, 11, 10, 11, 11, 15, 12, 17, 14, 17, 18, 21, 16, 22, 22, 23, 22, 27, 22, 29, 26, 29, 30, 31, 27, 35, 34, 35, 32, 39, 34, 41, 38, 39, 42, 45, 38, 46, 44, 47, 46, 51, 46, 51, 48, 53, 54, 57, 48, 59, 58, 57, 57, 61, 58, 65

Offset: 1

Clark Kimberling

a(n) is the number of non-divisors of n in 1..n. - Jaroslav Krizek, Nov 14 2009
Also equal to the number of partitions p of n such that max(p)-min(p) = 1. The number of partitions of n with max(p)-min(p) <= 1 is n; there is one with k parts for each 1 <= k <= n. max(p)-min(p) = 0 iff k divides n, leaving n-d(n) with a difference of 1. It is easiest to see this by looking at fixed k with increasing n: for k=3, starting with n=3 the partitions are [1,1,1], [2,1,1], [2,2,1], [2,2,2], [3,2,2], etc. - Giovanni Resta, Feb 06 2006 and Franklin T. Adams-Watters, Jan 30 2011
Number of positive numbers in n-th row of array T given by A049816.
Number of proper non-divisors of n. - Omar E. Pol, May 25 2010
a(n+2) is the sum of the n-th antidiagonal of A225145. - Richard R. Forberg, May 02 2013
For n > 2, number of nonzero terms in n-th row of triangle A051778. - Reinhard Zumkeller, Dec 03 2014
Number of partitions of n of the form [j,j,...,j,i] (j > i). Example: a(7)=5 because we have [6,1], [5,2], [4,3], [3,3,1], and [2,2,2,1]. - Emeric Deutsch, Sep 22 2016

			a(7) = 5; the 5 non-divisors of 7 in 1..7 are 2, 3, 4, 5, and 6.
The 5 partitions of 7 with max(p) - min(p) = 1 are [4,3], [3,2,2], [2,2,2,1], [2,2,1,1,1] and [2,1,1,1,1,1]. - _Emeric Deutsch_, Mar 01 2006

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
G. E. Andrews, M. Beck, N. Robbins, Partitions with fixed differences between largest and smallest parts, arXiv preprint arXiv:1406.3374 [math.NT], 2014-2015.

Cf. A000005.
One less than A062968, two less than A059292.
Cf. A161664 (partial sums).
Cf. A060990 (number of solutions to a(x) = n).
Cf. A045765 (numbers not occurring in this sequence).
Cf. A236561 (same sequence sorted into ascending order), A236562 (with also duplicates removed), A236565, A262901 and A262903.
Cf. A262511 (numbers that occur only once).
Cf. A055927 (positions of repeated terms).
Cf. A245388 (positions of squares).
Cf. A155043 (number of steps needed to reach zero when iterating a(n)), A262680 (number of nonzero squares encountered).
Cf. A259934 (an infinite trunk of the tree defined by edge-relation a(child) = parent, conjectured to be unique).
Cf. tables and arrays A047916, A051731, A051778, A173540, A173541.
Cf. also arrays A225145, A262898, A263255 and tables A263265, A263267.
Other related sequences: A006218, A006590, A051953, A070824, A094181, A062249, A067391, A076627, A128508, A131187, A134156, A140826, A161886, A177235, A177236, A227874, A228453, A230653, A230654, A231167, A245197, A253473.

List([1..80],n->n-Tau(n)); # Muniru A Asiru, Sep 28 2018

a049820 n = n - a000005 n  -- Reinhard Zumkeller, Feb 06 2012

A049820 := n->n-numtheory[tau](n):
seq(A049820(n), n=1..100);

Table[n - DivisorSigma[0, n], {n, 100}] (* Wesley Ivan Hurt, Nov 19 2014 *)
Array[(# - DivisorSigma[0, #])&, 70] (* Vincenzo Librandi, Dec 29 2015 *)

PARI
```
a(n)=n-numdiv(n)
```

(define (A049820 n) (- n (A000005 n))) ;; Antti Karttunen, Nov 27 2015

a(n) = Sum_{k=1..n} ceiling(n/k)-floor(n/k). - Benoit Cloitre, May 11 2003
G.f.: Sum_{k>0} x^(2*k+1)/(1-x^k)/(1-x^(k+1)). - Emeric Deutsch, Mar 01 2006
a(n) = A006590(n) - A006218(n) = A161886(n) - A000005(n) - A006218(n) + 1 for n >= 1. - Jaroslav Krizek, Nov 14 2009
a(n) = Sum_{k=1..n} A000007(A051731(n,k)). - Reinhard Zumkeller, Mar 09 2010
a(n) = A076627(n) / A000005(n). - Reinhard Zumkeller, Feb 06 2012
For n >= 2, a(n) = A094181(n) / A051953(n). - Antti Karttunen, Nov 27 2015
a(n) = Sum_{k=1..n} ((n mod k) + (-n mod k))/k. - Wesley Ivan Hurt, Dec 28 2015
G.f.: Sum_{j>=2} (x^(j+1)*(1-x^(j-1))/(1-x^j))/(1-x). - Emeric Deutsch, Sep 22 2016
Dirichlet g.f.: zeta(s-1)- zeta(s)^2. - Ilya Gutkovskiy, Apr 12 2017
a(n) = Sum_{i=1..n-1} sign(i mod n-i). - Wesley Ivan Hurt, Sep 27 2018

Edited by Franklin T. Adams-Watters, Jan 30 2012

A276085 Primorial base log-function: fully additive with a(p) = p#/p, where p# = A034386(p).

Original entry on oeis.org

0, 1, 2, 2, 6, 3, 30, 3, 4, 7, 210, 4, 2310, 31, 8, 4, 30030, 5, 510510, 8, 32, 211, 9699690, 5, 12, 2311, 6, 32, 223092870, 9, 6469693230, 5, 212, 30031, 36, 6, 200560490130, 510511, 2312, 9, 7420738134810, 33, 304250263527210, 212, 10, 9699691, 13082761331670030, 6, 60, 13, 30032, 2312, 614889782588491410, 7, 216, 33, 510512, 223092871, 32589158477190044730, 10

Offset: 1

Antti Karttunen, Aug 21 2016

nonn

Completely additive with a(p^e) = e * A002110(A000720(p)-1).
This is a left inverse of A276086 ("primorial base exp-function"), hence the name "primorial base log-function". When the domain is restricted to the terms of A048103, this works also as a right inverse, as A276086(a(A048103(n))) = A048103(n) for all n >= 1. - Antti Karttunen, Apr 24 2022
On average, every third term is a multiple of 4. See A369001. - Antti Karttunen, May 26 2024

A left inverse of A276086.
Cf. A000040, A000720, A002110, A028234, A034386, A048103, A049345, A055396, A067029, A108951, A143293, A276154, A328316, A328624, A328625, A328768, A328832, A346105, A351576, A376398 (partial sums).
Positions of multiples of k in this sequence, for k=2, 3, 4, 5, 8, 27, 3125: A003159, A339746, A369002, A373140, A373138, A377872, A377878.
Cf. A036554 (positions of odd terms), A035263, A096268 (parity of terms).
Cf. A372575 (rgs-transform), A372576 [a(n) mod 360], A373842 [= A003415(a(n))].
Cf. A373145 [= gcd(A003415(n), a(n))], A373361 [= gcd(n, a(n))], A373362 [= gcd(A001414(n), a(n))], A373485 [= gcd(A083345(n), a(n))], A373835 [= gcd(bigomega(n), a(n))], and also A373367 and A373147 [= A003415(n) mod a(n)], A373148 [= a(n) mod A003415(n)].
Other completely additive sequences with primes p mapped to a function of p include: A001222 (with a(p)=1), A001414 (with a(p)=p), A059975 (with a(p)=p-1), A341885 (with a(p)=p*(p+1)/2), A373149 (with a(p)=prevprime(p)), A373158 (with a(p)=p#).
Cf. also A276075 for factorial base and A048675, A054841 for base-2 and base-10 analogs.

nn = 60; b = MixedRadix[Reverse@ Prime@ Range@ PrimePi[nn + 1]]; Table[FromDigits[#, b] &@ Reverse@ If[n == 1, {0}, Function[k, ReplacePart[Table[0, {PrimePi[k[[-1, 1]]]}], #] &@ Map[PrimePi@ First@ # -> Last@ # &, k]]@ FactorInteger@ n], {n, nn}] (* Version 10.2, or *)
f[w_List] := Total[Times @@@ Transpose@ {Map[Times @@ # &, Prime@ Range@ Range[0, Length@ w - 1]], Reverse@ w}]; Table[f@ Reverse@ If[n == 1, {0}, Function[k, ReplacePart[Table[0, {PrimePi[k[[-1, 1]]]}], #] &@ Map[PrimePi@ First@ # -> Last@ # &, k]]@ FactorInteger@ n], {n, 60}] (* Michael De Vlieger, Aug 30 2016 *)

A276085(n) = { my(f = factor(n), pr=1, i=1, s=0); for(k=1, #f~, while(i <= primepi(f[k, 1])-1, pr *= prime(i); i++); s += f[k, 2]*pr); (s); }; \\ Antti Karttunen, Nov 11 2024

from sympy import primorial, primepi, factorint
def a002110(n):
    return 1 if n<1 else primorial(n)
def a(n):
    f=factorint(n)
    return sum(f[i]*a002110(primepi(i) - 1) for i in f)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Jun 22 2017

a(1) = 0; for n > 1, a(n) = a(A028234(n)) + (A067029(n) * A002110(A055396(n)-1)).
a(1) = 0, a(n) = (e1*A002110(i1-1) + ... + ez*A002110(iz-1)) when n = prime(i1)^e1 * ... * prime(iz)^ez.
Other identities.
For all n >= 0:
a(A276086(n)) = n.
a(A000040(1+n)) = A002110(n).
a(A002110(1+n)) = A143293(n).
From Antti Karttunen, Apr 24 & Apr 29 2022: (Start)
a(A283477(n)) = A283985(n).
a(A108951(n)) = A346105(n). [The latter has a similar additive formula as this sequence, but instead of primorials, uses their partial sums]
When applied to sequences where a certain subset of the divisors of n has been multiplicatively encoded with the help of A276086, this yields a corresponding number-theoretical sequence, i.e. completes their computation:
a(A319708(n)) = A001065(n) and a(A353564(n)) = A051953(n).
a(A329350(n)) = A069359(n) and a(A329380(n)) = A323599(n).
In the following group, the sum of the rhs-sequences is n [on each row, as say, A328841(n)+A328842(n)=n], because the pointwise product of the corresponding lhs-sequences is A276086:
a(A053669(n)) = A053589(n) and a(A324895(n)) = A276151(n).
a(A328571(n)) = A328841(n) and a(A328572(n)) = A328842(n).
a(A351231(n)) = A351233(n) and a(A327858(n)) = A351234(n).
a(A351251(n)) = A351253(n) and a(A324198(n)) = A351254(n).
The sum or difference of the rhs-sequences is A108951:
a(A344592(n)) = A346092(n) and a(A346091(n)) = A346093(n).
a(A346106(n)) = A346108(n) and a(A346107(n)) = A346109(n).
Here the two sequences are inverse permutations of each other:
a(A328624(n)) = A328625(n) and a(A328627(n)) = A328626(n).
a(A346102(n)) = A328622(n) and a(A346233(n)) = A328623(n).
a(A346101(n)) = A289234(n). [Self-inverse]
Other correspondences:
a(A324350(x,y)) = A324351(x,y).
a(A003961(A276086(n))) = A276154(n). [The primorial base left shift]
a(A276076(n)) = A351576(n). [Sequence reinterpreting factorial base representation as a primorial base representation]
(End)

Name amended by Antti Karttunen, Apr 24 2022

Name simplified, the old name moved to the comments - Antti Karttunen, Jun 23 2024

cp's OEIS Frontend

A098197 Smallest number m such that the trajectory of m under iteration of cototient function[=A051953] contains exactly n distinct numbers (including m and the fixed point=0). Or: the required number of iterations[=operations,transitions] is n-1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A194284 Entries n of A194234 for which the cototient A051953(n) is a composite number.

Views

Author

Keywords

A292283 Numbers n such that f(g(n)) - g(f(n)) = n where f = A001065 and g = A051953.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

A001065 Sum of proper divisors (or aliquot parts) of n: sum of divisors of n that are less than n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

MuPAD

PARI

Python

Sage

Formula

A246655 Prime powers: numbers of the form p^k where p is a prime and k >= 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Python

Sage

Formula

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).