A027748 -id:A027748 - cp's OEIS frontend

A000203 a(n) = sigma(n), the sum of the divisors of n. Also called sigma_1(n).

1, 3, 4, 7, 6, 12, 8, 15, 13, 18, 12, 28, 14, 24, 24, 31, 18, 39, 20, 42, 32, 36, 24, 60, 31, 42, 40, 56, 30, 72, 32, 63, 48, 54, 48, 91, 38, 60, 56, 90, 42, 96, 44, 84, 78, 72, 48, 124, 57, 93, 72, 98, 54, 120, 72, 120, 80, 90, 60, 168, 62, 96, 104, 127, 84, 144, 68, 126, 96, 144

Offset: 1

N. J. A. Sloane

Multiplicative: If the canonical factorization of n into prime powers is the product of p^e(p) then sigma_k(n) = Product_p ((p^((e(p)+1)*k))-1)/(p^k-1).
Sum_{d|n} 1/d^k is equal to sigma_k(n)/n^k. So sequences A017665-A017712 also give the numerators and denominators of sigma_k(n)/n^k for k = 1..24. The power sums sigma_k(n) are in sequences A000203 (this sequence) (k=1), A001157-A001160 (k=2,3,4,5), A013954-A013972 for k = 6,7,...,24. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 05 2001
A number n is abundant if sigma(n) > 2n (cf. A005101), perfect if sigma(n) = 2n (cf. A000396), deficient if sigma(n) < 2n (cf. A005100).
a(n) is the number of sublattices of index n in a generic 2-dimensional lattice. - Avi Peretz (njk(AT)netvision.net.il), Jan 29 2001 [In the language of group theory, a(n) is the number of index-n subgroups of Z x Z. - Jianing Song, Nov 05 2022]
The sublattices of index n are in one-to-one correspondence with matrices [a b; 0 d] with a>0, ad=n, b in [0..d-1]. The number of these is Sum_{d|n} d = sigma(n), which is a(n). A sublattice is primitive if gcd(a,b,d) = 1; the number of these is n * Product_{p|n} (1+1/p), which is A001615. [Cf. Grady reference.]
Sum of number of common divisors of n and m, where m runs from 1 to n. - Naohiro Nomoto, Jan 10 2004
a(n) is the cardinality of all extensions over Q_p with degree n in the algebraic closure of Q_p, where p>n. - Volker Schmitt (clamsi(AT)gmx.net), Nov 24 2004. Cf. A100976, A100977, A100978 (p-adic extensions).
Let s(n) = a(n-1) + a(n-2) - a(n-5) - a(n-7) + a(n-12) + a(n-15) - a(n-22) - a(n-26) + ..., then a(n) = s(n) if n is not pentagonal, i.e., n != (3 j^2 +- j)/2 (cf. A001318), and a(n) is instead s(n) - ((-1)^j)*n if n is pentagonal. - Gary W. Adamson, Oct 05 2008 [corrected Apr 27 2012 by William J. Keith based on Ewell and by Andrey Zabolotskiy, Apr 08 2022]
Write n as 2^k * d, where d is odd. Then a(n) is odd if and only if d is a square. - Jon Perry, Nov 08 2012
Also total number of parts in the partitions of n into equal parts. - Omar E. Pol, Jan 16 2013
Note that sigma(3^4) = 11^2. On the other hand, Kanold (1947) shows that the equation sigma(q^(p-1)) = b^p has no solutions b > 2, q prime, p odd prime. - N. J. A. Sloane, Dec 21 2013, based on postings to the Number Theory Mailing List by Vladimir Letsko and Luis H. Gallardo
Limit_{m->infinity} (Sum_{n=1..prime(m)} a(n)) / prime(m)^2 = zeta(2)/2 = Pi^2/12 (A072691). See more at A244583. - Richard R. Forberg, Jan 04 2015
a(n) + A000005(n) is an odd number iff n = 2m^2, m>=1. - Richard R. Forberg, Jan 15 2015
a(n) = a(n+1) for n = 14, 206, 957, 1334, 1364 (A002961). - Zak Seidov, May 03 2016
Equivalent to the Riemann hypothesis: a(n) < H(n) + exp(H(n))*log(H(n)), for all n>1, where H(n) is the n-th harmonic number (Jeffrey Lagarias). See A057641 for more details. - Ilya Gutkovskiy, Jul 05 2016
a(n) is the total number of even parts in the partitions of 2*n into equal parts. More generally, a(n) is the total number of parts congruent to 0 mod k in the partitions of k*n into equal parts (the comment dated Jan 16 2013 is the case for k = 1). - Omar E. Pol, Nov 18 2019
From Jianing Song, Nov 05 2022: (Start)
a(n) is also the number of order-n subgroups of C_n X C_n, where C_n is the cyclic group of order n. Proof: by the correspondence theorem in the group theory, there is a one-to-one correspondence between the order-n subgroups of C_n X C_n = (Z x Z)/(nZ x nZ) and the index-n subgroups of Z x Z containing nZ x nZ. But an index-n normal subgroup of a (multiplicative) group G contains {g^n : n in G} automatically. The desired result follows from the comment from Naohiro Nomoto above.
The number of subgroups of C_n X C_n that are isomorphic to C_n is A001615(n). (End)

			For example, 6 is divisible by 1, 2, 3 and 6, so sigma(6) = 1 + 2 + 3 + 6 = 12.
Let L = <V,W> be a 2-dimensional lattice. The 7 sublattices of index 4 are generated by <4V,W>, <V,4W>, <4V,W+-V>, <2V,2W>, <2V+W,2W>, <2V,2W+V>. Compare A001615.

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 38.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 116ff.
Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 407.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 162, #16, (6), 2nd formula.
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, AMS Chelsea Publishing, Providence, Rhode Island, 2002, pp. 141, 166.
H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Clarendon Press, Oxford, 2003.
Ross Honsberger, "Mathematical Gems, Number One," The Dolciani Mathematical Expositions, Published and Distributed by The Mathematical Association of America, page 116.
Kanold, Hans Joachim, Kreisteilungspolynome und ungerade vollkommene Zahlen. (German), Ber. Math.-Tagung Tübingen 1946, (1947). pp. 84-87.
M. Krasner, Le nombre des surcorps primitifs d'un degré donné et le nombre des surcorps métagaloisiens d'un degré donné d'un corps de nombres p-adiques. Comptes Rendus Hebdomadaires, Académie des Sciences, Paris 254, 255, 1962.
A. Lubotzky, Counting subgroups of finite index, Proceedings of the St. Andrews/Galway 93 group theory meeting, Th. 2.1. LMS Lecture Notes Series no. 212 Cambridge University Press 1995.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section III.1, page 77.
G. Pólya, Induction and Analogy in Mathematics, vol. 1 of Mathematics and Plausible Reasoning, Princeton Univ Press 1954, page 92.
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 91, 395.
Robert M. Young, Excursions in Calculus, The Mathematical Association of America, 1992 p. 361.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 20000 terms from N. J. A. Sloane)
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].
B. Apostol and L. Petrescu, Extremal Orders of Certain Functions Associated with Regular Integers (mod n), Journal of Integer Sequences, 2013, # 13.7.5.
Joerg Arndt, On computing the generalized Lambert series, arXiv:1202.6525v3 [math.CA], (2012).
M. Baake and U. Grimm, Quasicrystalline combinatorics
Henry Bottomley, Illustration of initial terms
C. K. Caldwell, The Prime Glossary, sigma function
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
D. Christopher and T. Nadu, Partitions with Fixed Number of Sizes, Journal of Integer Sequences, 15 (2015), #15.11.5.
J. N. Cooper and A. W. N. Riasanovsky, On the Reciprocal of the Binary Generating Function for the Sum of Divisors, 2012. - _N. J. A. Sloane_, Dec 25 2012
R. L. Duncan, Note on the Divisors of a Number, The American Mathematical Monthly, 68(4), 356-359, (1961).
Jason Earls, The Smarandache sum of composites between factors function, in Smarandache Notions Journal (2004), Vol. 14.1, page 243.
L. Euler, Discovery of a most extraordinary law of numbers, relating to the sum of their divisors
L. Euler, Observatio de summis divisorum
L. Euler, An observation on the sums of divisors, arXiv:math/0411587 [math.HO], 2004-2009.
J. A. Ewell, Recurrences for the sum of divisors, Proc. Amer. Math. Soc. 64 (2) 1977.
Farideh Firoozbakht and M. F. Hasler, Variations on Euclid's formula for Perfect Numbers, JIS 13 (2010) #10.3.1.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors ..., J. Integer Seqs., Vol. 6, 2003.
Johan Gielis and Ilia Tavkhelidze, The general case of cutting of GML surfaces and bodies, arXiv:1904.01414 [math.GM], 2019.
J. W. L. Glaisher, On the function chi(n), Quarterly Journal of Pure and Applied Mathematics, 20 (1884), 97-167.
J. W. L. Glaisher, On the function chi(n), Quarterly Journal of Pure and Applied Mathematics, 20 (1884), 97-167. [Annotated scanned copy]
M. J. Grady, A group theoretic approach to a famous partition formula, Amer. Math. Monthly, 112 (No. 7, 2005), 645-651.
Masazumi Honda and Takuya Yoda, String theory, N = 4 SYM and Riemann hypothesis, arXiv:2203.17091 [hep-th], 2022.
Douglas E. Iannucci, On sums of the small divisors of a natural number, arXiv:1910.11835 [math.NT], 2019.
Antti Karttunen, Scheme program for computing this sequence.
P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc., 19 (1921), 75-113.
M. Maia and M. Mendez, On the arithmetic product of combinatorial species, arXiv:math.CO/0503436, 2005.
K. Matthews, Factorizing n and calculating phi(n),omega(n),d(n),sigma(n) and mu(n)
Walter Nissen, Abundancy : Some Resources
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. 83 (2014), 1903-1913.
John S. Rutherford, The enumeration and symmetry-significant properties of derivative lattices, Act. Cryst. (1992) A48, 500-508. - _N. J. A. Sloane_, Mar 14 2009
John S. Rutherford, The enumeration and symmetry-significant properties of derivative lattices II, Acta Cryst. A49 (1993), 293-300. - _N. J. A. Sloane_, Mar 14 2009
John S. Rutherford, Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type, Acta Cryst. (2009). A65, 156-163. [See Table 1]. - _N. J. A. Sloane_, Feb 23 2009
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 3.
Eric Weisstein's World of Mathematics, Divisor Function
Wikipedia, Divisor function
Index entries for sequences related to sublattices
Index entries for sequences related to sigma(n)
Index entries for "core" sequences

See A034885, A002093 for records. Bisections give A008438, A062731. Values taken are listed in A007609. A054973 is an inverse function.
For partial sums see A024916.
Row sums of A127093.
sigma_i (i=0..25): A000005, A000203, A001157, A001158, A001159, A001160, A013954, A013955, A013956, A013957, A013958, A013959, A013960, A013961, A013962, A013963, A013964, A013965, A013966, A013967, A013968, A013969, A013970, A013971, A013972, A281959.
Cf. A144736, A158951, A158902, A174740, A147843, A001158, A001160, A001065, A002192, A001001, A001615 (primitive sublattices), A039653, A088580, A074400, A083728, A006352, A002659, A083238, A000593, A050449, A050452, A051731, A027748, A124010, A069192, A057641, A001318.
Cf. A009194, A082062 (gcd(a(n),n) and its largest prime factor), A179931, A192795 (gcd(a(n),A001157(n)) and largest prime factor).
Cf. also A034448 (sum of unitary divisors).
Cf. A007955 (products of divisors).
Cf. A144613, A144614, A144615, A146076.
A001227, A000593 and this sequence have the same parity: A053866. - Omar E. Pol, May 14 2016
Cf. A001221, A054533.

A000203:=List([1..10^2],n->Sigma(n)); # Muniru A Asiru, Oct 01 2017

a000203 n = product $ zipWith (\p e -> (p^(e+1)-1) `div` (p-1)) (a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, May 07 2012

Magma
```
[SumOfDivisors(n): n in [1..70]];
```

[DivisorSigma(1,n): n in [1..70]]; // Bruno Berselli, Sep 09 2015

with(numtheory): A000203 := n->sigma(n); seq(A000203(n), n=1..100);

Table[ DivisorSigma[1, n], {n, 100}]
a[ n_] := SeriesCoefficient[ QPolyGamma[ 1, 1, q] / Log[q]^2, {q, 0, n}]; (* Michael Somos, Apr 25 2013 *)

makelist(divsum(n),n,1,1000); /* Emanuele Munarini, Mar 26 2011 */

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

PARI
```
{a(n) = if( n<1, 0, sigma(n))};
```

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

{a(n) = if( n<1, 0, polcoeff( sum( k=1, n, x^k / (1 - x^k)^2, x * O(x^n)), n))}; /* Michael Somos, Jan 29 2005 */

max_n = 30; ser = - sum(k=1,max_n,log(1-x^k)); a(n) = polcoeff(ser,n)*n \\ Gottfried Helms, Aug 10 2009

from sympy import divisor_sigma
def a(n): return divisor_sigma(n, 1)
print([a(n) for n in range(1, 71)]) # Michael S. Branicky, Jan 03 2021

from math import prod
from sympy import factorint
def a(n): return prod((p**(e+1)-1)//(p-1) for p, e in factorint(n).items())
print([a(n) for n in range(1, 51)]) # Michael S. Branicky, Feb 25 2024
(APL, Dyalog dialect) A000203 ← +/{ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð,(⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð} ⍝ Antti Karttunen, Feb 20 2024

[sigma(n, 1) for n in range(1, 71)]  # Zerinvary Lajos, Jun 04 2009

(definec (A000203 n) (if (= 1 n) n (let ((p (A020639 n)) (e (A067029 n))) (* (/ (- (expt p (+ 1 e)) 1) (- p 1)) (A000203 (A028234 n)))))) ;; Uses macro definec from http://oeis.org/wiki/Memoization#Scheme - Antti Karttunen, Nov 25 2017

(define (A000203 n) (let ((r (sqrt n))) (let loop ((i (inexact->exact (floor r))) (s (if (integer? r) (- r) 0))) (cond ((zero? i) s) ((zero? (modulo n i)) (loop (- i 1) (+ s i (/ n i)))) (else (loop (- i 1) s)))))) ;; (Stand-alone program) - Antti Karttunen, Feb 20 2024

Multiplicative with a(p^e) = (p^(e+1)-1)/(p-1). - David W. Wilson, Aug 01 2001
For the following bounds and many others, see Mitrinovic et al. - N. J. A. Sloane, Oct 02 2017
If n is composite, a(n) > n + sqrt(n).
a(n) < n*sqrt(n) for all n.
a(n) < (6/Pi^2)*n^(3/2) for n > 12.
G.f.: -x*deriv(eta(x))/eta(x) where eta(x) = Product_{n>=1} (1-x^n). - Joerg Arndt, Mar 14 2010
L.g.f.: -log(Product_{j>=1} (1-x^j)) = Sum_{n>=1} a(n)/n*x^n. - Joerg Arndt, Feb 04 2011
Dirichlet convolution of phi(n) and tau(n), i.e., a(n) = sum_{d|n} phi(n/d)*tau(d), cf. A000010, A000005.
a(n) is odd iff n is a square or twice a square. - Robert G. Wilson v, Oct 03 2001
a(n) = a(n*prime(n)) - prime(n)*a(n). - Labos Elemer, Aug 14 2003 (Clarified by Omar E. Pol, Apr 27 2016)
a(n) = n*A000041(n) - Sum_{i=1..n-1} a(i)*A000041(n-i). - Jon Perry, Sep 11 2003
a(n) = -A010815(n)*n - Sum_{k=1..n-1} A010815(k)*a(n-k). - Reinhard Zumkeller, Nov 30 2003
a(n) = f(n, 1, 1, 1), where f(n, i, x, s) = if n = 1 then s*x else if p(i)|n then f(n/p(i), i, 1+p(i)*x, s) else f(n, i+1, 1, s*x) with p(i) = i-th prime (A000040). - Reinhard Zumkeller, Nov 17 2004
Recurrence: n^2*(n-1)*a(n) = 12*Sum_{k=1..n-1} (5*k*(n-k) - n^2)*a(k)*a(n-k), if n>1. - Dominique Giard (dominique.giard(AT)gmail.com), Jan 11 2005
G.f.: Sum_{k>0} k * x^k / (1 - x^k) = Sum_{k>0} x^k / (1 - x^k)^2. Dirichlet g.f.: zeta(s)*zeta(s-1). - Michael Somos, Apr 05 2003. See the Hardy-Wright reference, p. 312. first equation, and p. 250, Theorem 290. - Wolfdieter Lang, Dec 09 2016
For odd n, a(n) = A000593(n). For even n, a(n) = A000593(n) + A074400(n/2). - Jonathan Vos Post, Mar 26 2006
Equals the inverse Moebius transform of the natural numbers. Equals row sums of A127093. - Gary W. Adamson, May 20 2007
A127093 * [1/1, 1/2, 1/3, ...] = [1/1, 3/2, 4/3, 7/4, 6/5, 12/6, 8/7, ...]. Row sums of triangle A135539. - Gary W. Adamson, Oct 31 2007
a(n) = A054785(2*n) - A000593(2*n). - Reinhard Zumkeller, Apr 23 2008
a(n) = n*Sum_{k=1..n} A060642(n,k)/k*(-1)^(k+1). - Vladimir Kruchinin, Aug 10 2010
Dirichlet convolution of A037213 and A034448. - R. J. Mathar, Apr 13 2011
G.f.: A(x) = x/(1-x)*(1 - 2*x*(1-x)/(G(0) - 2*x^2 + 2*x)); G(k) = -2*x - 1 - (1+x)*k + (2*k+3)*(x^(k+2)) - x*(k+1)*(k+3)*((-1 + (x^(k+2)))^2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 06 2011
a(n) = A001065(n) + n. - Mats Granvik, May 20 2012
a(n) = A006128(n) - A220477(n). - Omar E. Pol, Jan 17 2013
a(n) = Sum_{k=1..A003056(n)} (-1)^(k-1)*A196020(n,k). - conjectured by Omar E. Pol, Feb 02 2013, and proved by Max Alekseyev, Nov 17 2013
a(n) = Sum_{k=1..A003056(n)} (-1)^(k-1)*A000330(k)*A000716(n-A000217(k)). - Mircea Merca, Mar 05 2014
a(n) = A240698(n, A000005(n)). - Reinhard Zumkeller, Apr 10 2014
a(n) = Sum_{d^2|n} A001615(n/d^2) = Sum_{d^3|n} A254981(n/d^3). - Álvar Ibeas, Mar 06 2015
a(3*n) = A144613(n). a(3*n + 1) = A144614(n). a(3*n + 2) = A144615(n). - Michael Somos, Jul 19 2015
a(n) = Sum{i=1..n} Sum{j=1..i} cos((2*Pi*n*j)/i). - Michel Lagneau, Oct 14 2015
a(n) = A000593(n) + A146076(n). - Omar E. Pol, Apr 05 2016
a(n) = A065475(n) + A048050(n). - Omar E. Pol, Nov 28 2016
a(n) = (Pi^2*n/6)*Sum_{q>=1} c_q(n)/q^2, with the Ramanujan sums c_q(n) given in A054533 as a c_n(k) table. See the Hardy reference, p. 141, or Hardy-Wright, Theorem 293, p. 251. - Wolfdieter Lang, Jan 06 2017
G.f. also (1 - E_2(q))/24, with the g.f. E_2 of A006352. See e.g., Hardy, p. 166, eq. (10.5.5). - Wolfdieter Lang, Jan 31 2017
From Antti Karttunen, Nov 25 2017: (Start)
a(n) = A048250(n) + A162296(n).
a(n) = A092261(n) * A295294(n). [This can be further expanded, see comment in A291750.] (End)
a(n) = A000593(n) * A038712(n). - Ivan N. Ianakiev and Omar E. Pol, Nov 26 2017
a(n) = Sum_{q=1..n} c_q(n) * floor(n/q), where c_q(n) is the Ramanujan's sum function given in A054533. - Daniel Suteu, Jun 14 2018
a(n) = Sum_{k=1..n} gcd(n, k) / phi(n / gcd(n, k)), where phi(k) is the Euler totient function. - Daniel Suteu, Jun 21 2018
a(n) = (2^(1 + (A000005(n) - A001227(n))/(A000005(n) - A183063(n))) - 1)*A000593(n) = (2^(1 + (A183063(n)/A001227(n))) - 1)*A000593(n). - Omar E. Pol, Nov 03 2018
a(n) = Sum_{i=1..n} tau(gcd(n, i)). - Ridouane Oudra, Oct 15 2019
From Peter Bala, Jan 19 2021: (Start)
G.f.: A(x) = Sum_{n >= 1} x^(n^2)*(x^n + n*(1 - x^(2*n)))/(1 - x^n)^2 - differentiate equation 5 in Arndt w.r.t. x, and set x = 1.
A(x) = F(x) + G(x), where F(x) is the g.f. of A079667 and G(x) is the g.f. of A117004. (End)
a(n) = Sum_{k=1..n} tau(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). - Richard L. Ollerton, May 07 2021
With the convention that a(n) = 0 for n <= 0 we have the recurrence a(n) = t(n) + Sum_{k >= 1} (-1)^(k+1)*(2*k + 1)*a(n - k*(k + 1)/2), where t(n) = (-1)^(m+1)*(2*m+1)*n/3 if n = m*(m + 1)/2, with m positive, is a triangular number else t(n) = 0. For example, n = 10 = (4*5)/2 is a triangular number, t(10) = -30, and so a(10) = -30 + 3*a(9) - 5*a(7) + 7*a(4) = -30 + 39 - 40 + 49 = 18. - Peter Bala, Apr 06 2022
Recurrence: a(p^x) = p*a(p^(x-1)) + 1, if p is prime and for any integer x. E.g., a(5^3) = 5*a(5^2) + 1 = 5*31 + 1 = 156. - Jules Beauchamp, Nov 11 2022
Sum_{n>=1} a(n)/exp(2*Pi*n) = 1/24 - 1/(8*Pi) = A319462. - Vaclav Kotesovec, May 07 2023
a(n) < (7n*A001221(n) + 10*n)/6 [Duncan, 1961] (see Duncan and Tattersall). - Stefano Spezia, Jul 13 2025

A001222 Number of prime divisors of n counted with multiplicity (also called big omega of n, bigomega(n) or Omega(n)).

Original entry on oeis.org

0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2, 3, 3, 1, 3, 1, 5, 2, 2, 2, 4, 1, 2, 2, 4, 1, 3, 1, 3, 3, 2, 1, 5, 2, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 4, 1, 2, 3, 6, 2, 3, 1, 3, 2, 3, 1, 5, 1, 2, 3, 3, 2, 3, 1, 5, 4, 2, 1, 4, 2, 2, 2, 4, 1, 4, 2, 3, 2, 2, 2, 6, 1, 3, 3, 4, 1, 3, 1, 4, 3, 2, 1, 5, 1, 3, 2

Offset: 1

N. J. A. Sloane

Maximal number of terms in any factorization of n.
Number of prime powers (not including 1) that divide n.
Sum of exponents in prime-power factorization of n. - Daniel Forgues, Mar 29 2009
Sum_{d|n} 2^(-A001221(d) - a(n/d)) = Sum_{d|n} 2^(-a(d) - A001221(n/d)) = 1 (see Dressler and van de Lune link). - Michel Marcus, Dec 18 2012
Row sums in A067255. - Reinhard Zumkeller, Jun 11 2013
Conjecture: Let f(n) = (x+y)^a(n), and g(n) = x^a(n), and h(n) = (x+y)^A046660(n) * y^A001221(n) with x, y complex numbers and 0^0 = 1. Then f(n) = Sum_{d|n} g(d)*h(n/d). This is proved for x = 1-y (see Dressler and van de Lune link). - Werner Schulte, Feb 10 2018
Let r, s be some fixed integers. Then we have:
  (1) The sequence b(n) = Dirichlet convolution of r^bigomega(n) and s^bigomega(n) is multiplicative with b(p^e) = (r^(e+1)-s^(e+1))/(r-s) for prime p and e >= 0. The case r = s leads to b(p^e) = (e+1)*r^e.
  (2) The sequence c(n) = Dirichlet convolution of r^bigomega(n) and mu(n)*s^bigomega(n) is multiplicative with c(p^e) = (r-s)*r^(e-1) and c(1) = 1 for prime p and e > 0 where mu(n) = A008683(n). - Werner Schulte, Feb 20 2019
a(n) is also the length of the composition series for every solvable group of order n. - Miles Englezou, Apr 25 2024

			16=2^4, so a(16)=4; 18=2*3^2, so a(18)=3.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 119, #12, omega(n).
G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 48-57.
M. Kac, Statistical Independence in Probability, Analysis and Number Theory, Carus Monograph 12, Math. Assoc. Amer., 1959, see p. 64.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 92.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from N. J. A. Sloane)
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], p. 844.
Benoit Cloitre, A tauberian approach to RH, arXiv:1107.0812 [math.NT], 2011.
Robert E. Dressler and Jan van de Lune, Some remarks concerning the number theoretic functions omega and Omega, Proc. Amer. Math. Soc. 41 (1973), 403-406.
G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number, Quart. J. Math. 48 (1917), 76-92. Also Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI (2000): 262-275.
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021. Section 1.1.1. pp. 4-5.
Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4, 1.10.
Eric Weisstein's World of Mathematics, Prime Factor
Eric Weisstein's World of Mathematics, Roundness
Wolfram Research, First 50 numbers factored
Index entries for "core" sequences
Index entries for sequences computed from exponents in factorization of n
Index entries for sequences computed from indices in prime factorization

Cf. A001221 (omega, primes counted without multiplicity), A008836 (Liouville's lambda, equal to (-1)^a(n)), A046660, A144494, A074946, A134334.
Bisections give A091304 and A073093. A086436 is essentially the same sequence. Cf. A022559 (partial sums), A066829 (parity), A092248 (parity of omega).
Sequences listing n such that a(n) = r: A000040 (r = 1), A001358 (r = 2), A014612 (r = 3), A014613 (r = 4), A014614 (r = 5), A046306 (r = 6), A046308 (r = 7), A046310 (r = 8), A046312 (r = 9), A046314 (r = 10), A069272 (r = 11), A069273 (r = 12), A069274 (r = 13),  A069275 (r = 14),  A069276 (r = 15),  A069277 (r = 16),  A069278 (r = 17),  A069279 (r = 18),  A069280 (r = 19),  A069281 (r = 20). - Jason Kimberley, Oct 02 2011
Cf. A079149 (primes adj. to integers with at most 2 prime factors, a(n)<=2).
Cf. A000120, A020639, A091202, A091222, A156552, A267116, A268387.
Cf. A027748 (without repetition).
Cf. A000010.

Concatenation([0],List([2..150],n->Length(Factors(n)))); # Muniru A Asiru, Feb 21 2019

import Math.NumberTheory.Primes.Factorisation (factorise)
a001222 = sum . snd . unzip . factorise
-- Reinhard Zumkeller, Nov 28 2015

using Nemo
function NumberOfPrimeFactors(n; distinct=true)
    distinct && return length(factor(ZZ(n)))
    sum(e for (p, e) in factor(ZZ(n)); init=0)
end
println([NumberOfPrimeFactors(n, distinct=false) for n in 1:60])  # Peter Luschny, Jan 02 2024

[n eq 1 select 0 else &+[p[2]: p in Factorization(n)]: n in [1..120]]; // Bruno Berselli, Nov 27 2013

with(numtheory): seq(bigomega(n), n=1..111);

Array[ Plus @@ Last /@ FactorInteger[ # ] &, 105]
PrimeOmega[Range[120]] (* Harvey P. Dale, Apr 25 2011 *)

PARI
```
vector(100,n,bigomega(n))
```

from sympy import primeomega
def a(n): return primeomega(n)
print([a(n) for n in range(1, 112)]) # Michael S. Branicky, Apr 30 2022

[sloane.A001222(n) for n in (1..120)] # Giuseppe Coppoletta, Jan 19 2015

[gp.bigomega(n) for n in range(1,131)] # G. C. Greubel, Jul 13 2024

(define (A001222 n) (let loop ((n n) (z 0)) (if (= 1 n) z (loop (/ n (A020639 n)) (+ 1 z)))))
;; Requires also A020639 for which an equally naive implementation can be found under that entry. - Antti Karttunen, Apr 12 2017

n = Product_(p_j^k_j) -> a(n) = Sum_(k_j).
Dirichlet g.f.: ppzeta(s)*zeta(s). Here ppzeta(s) = Sum_{p prime} Sum_{k>=1} 1/(p^k)^s. Note that ppzeta(s) = Sum_{p prime} 1/(p^s-1) and ppzeta(s) = Sum_{k>=1} primezeta(k*s). - Franklin T. Adams-Watters, Sep 11 2005
Totally additive with a(p) = 1.
a(n) = if n=1 then 0 else a(n/A020639(n)) + 1. - Reinhard Zumkeller, Feb 25 2008
a(n) = Sum_{k=1..A001221(n)} A124010(n,k). - Reinhard Zumkeller, Aug 27 2011
a(n) = A022559(n) - A022559(n-1).
G.f.: Sum_{p prime, k>=1} x^(p^k)/(1 - x^(p^k)). - Ilya Gutkovskiy, Jan 25 2017
a(n) = A091222(A091202(n)) = A000120(A156552(n)). - Antti Karttunen, circa 2004 and Mar 06 2017
a(n) >= A267116(n) >= A268387(n). - Antti Karttunen, Apr 12 2017
Sum_{k=1..n} 2^(-A001221(gcd(n,k)) - a(n/gcd(n,k)))/phi(n/gcd(n,k)) = Sum_{k=1..n} 2^(-a(gcd(n,k)) - A001221(n/gcd(n,k)))/phi(n/gcd(n,k)) = 1, where phi = A000010. - Richard L. Ollerton, May 13 2021
a(n) = a(A046523(n)) = A007814(A108951(n)) = A061395(A122111(n)) = A056239(A181819(n)) = A048675(A293442(n)). - Antti Karttunen, Apr 30 2022

More terms from David W. Wilson

A056239 If n = Product_{k >= 1} (p_k)^(c_k) where p_k is k-th prime and c_k >= 0 then a(n) = Sum_{k >= 1} k*c_k.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 6, 5, 5, 4, 7, 5, 8, 5, 6, 6, 9, 5, 6, 7, 6, 6, 10, 6, 11, 5, 7, 8, 7, 6, 12, 9, 8, 6, 13, 7, 14, 7, 7, 10, 15, 6, 8, 7, 9, 8, 16, 7, 8, 7, 10, 11, 17, 7, 18, 12, 8, 6, 9, 8, 19, 9, 11, 8, 20, 7, 21, 13, 8, 10, 9, 9, 22, 7, 8, 14, 23, 8, 10, 15, 12, 8, 24, 8, 10

Offset: 1

Leroy Quet, Aug 19 2000

A pseudo-logarithmic function in the sense that a(b*c) = a(b)+a(c) and so a(b^c) = c*a(b) and f(n) = k^a(n) is a multiplicative function. [Cf. A248692 for example.] Essentially a function from the positive integers onto the partitions of the nonnegative integers (1->0, 2->1, 3->2, 4->1+1, 5->3, 6->1+2, etc.) so each value a(n) appears A000041(a(n)) times, first with the a(n)-th prime and last with the a(n)-th power of 2. Produces triangular numbers from primorials. - Henry Bottomley, Nov 22 2001
Michael Nyvang writes (May 08 2006) that the Danish composer Karl Aage Rasmussen discovered this sequence in the 1990's: it has excellent musical properties.
All A000041(a(n)) different n's with the same value a(n) are listed in row a(n) of triangle A215366. - Alois P. Heinz, Aug 09 2012
a(n) is the sum of the parts of the partition having Heinz number n. We define the Heinz number of a partition p = [p_1, p_2, ..., p_r] as Product_{j=1..r} (p_j-th prime) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). For example, for the partition [1, 1, 2, 4, 10] we get 2*2*3*7*29 = 2436. Example: a(33) = 7 because the partition with Heinz number 33 = 3 * 11 is [2,5]. - Emeric Deutsch, May 19 2015

			a(12) = 1*2 + 2*1 = 4, since 12 = 2^2 *3^1 = (p_1)^2 *(p_2)^1.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Index entries for sequences computed from indices in prime factorization

Row sums of A112798.
Cf. A003963 (gives the corresponding products).
Cf. also A000041, A000217, A000720, A001221, A001222, A002110, A005940, A008475, A027748, A049084, A060437, A081401, A082090, A088314, A088318, A088850, A088880, A088881, A088887, A088902, A108951, A122111, A124010, A127668, A141128, A153734, A154351, A156552, A163517, A178503, A215366, A215369, A215501, A242422, A242423, A242424, A243070, A243353, A243354, A243503, A248692, A249336, A249337, A329605, A329902.

a056239 n = sum $ zipWith (*) (map a049084 $ a027748_row n) (a124010_row n)
-- Reinhard Zumkeller, Apr 27 2013

# To get 10000 terms. First make prime table: M:=10000; pl:=array(1..M); for i from 1 to M do pl[i]:=0; od: for i from 1 to M do if ithprime(i) > M then break; fi; pl[ithprime(i)]:=i; od:
# Decode Maple's amazing syntax for factoring integers: g:=proc(n) local e,p,t1,t2,t3,i,j,k; global pl; t1:=ifactor(n); t2:=nops(t1); if t2 = 2 and whattype(t1) <> `*` then p:=op(1,op(1,t1)); e:=op(2,t1); t3:=pl[p]*e; else
t3:=0; for i from 1 to t2 do j:=op(i,t1); if nops(j) = 1 then e:=1; p:=op(1,j); else e:=op(2,j); p:=op(1,op(1,j)); fi; t3:=t3+pl[p]*e; od: fi; t3; end; # N. J. A. Sloane, May 10 2006
A056239 := proc(n) add( numtheory[pi](op(1,p))*op(2,p), p = ifactors(n)[2]) ; end proc: # R. J. Mathar, Apr 20 2010
# alternative:
with(numtheory): a := proc (n) local B: B := proc (n) local nn, j, m: nn := op(2, ifactors(n)): for j to nops(nn) do m[j] := op(j, nn) end do: [seq(seq(pi(op(1, m[i])), q = 1 .. op(2, m[i])), i = 1 .. nops(nn))] end proc: add(B(n)[i], i = 1 .. nops(B(n))) end proc: seq(a(n), n = 1 .. 130); # Emeric Deutsch, May 19 2015

a[1] = 0; a[2] = 1; a[p_?PrimeQ] := a[p] = PrimePi[p];
a[n_] := a[n] = Total[#[[2]]*a[#[[1]]] & /@ FactorInteger[n]]; a /@ Range[91] (* Jean-François Alcover, May 19 2011 *)
Table[Total[FactorInteger[n] /. {p_, c_} /; p > 0 :> PrimePi[p] c], {n, 91}] (* Michael De Vlieger, Jul 12 2017 *)

A056239(n) = if(1==n,0,my(f=factor(n)); sum(i=1, #f~, f[i,2] * primepi(f[i,1]))); \\ Antti Karttunen, Oct 26 2014, edited Jan 13 2020

from sympy import primepi, factorint
def A056239(n): return sum(primepi(p)*e for p, e in factorint(n).items()) # Chai Wah Wu, Jan 01 2023

(require 'factor) ;; Uses the function factor available in Aubrey Jaffer's SLIB Scheme library.
(define (A056239 n) (apply + (map A049084 (factor n))))
;; Antti Karttunen, Oct 26 2014

Totally additive with a(p) = PrimePi(p), where PrimePi(n) = A000720(n).
a(n) = Sum_{k=1..A001221(n)} A049084(A027748(k))*A124010(k). - Reinhard Zumkeller, Apr 27 2013
From Antti Karttunen, Oct 11 2014: (Start)
a(n) = n - A178503(n).
a(n) = A161511(A156552(n)).
a(n) = A227183(A243354(n)).
For all n >= 0:
a(A002110(n)) = A000217(n). [Cf. Henry Bottomley's comment above.]
a(A005940(n+1)) = A161511(n).
a(A243353(n)) = A227183(n).
Also, for all n >= 1:
a(A241909(n)) = A243503(n).
a(A122111(n)) = a(n).
a(A242424(n)) = a(n).
A248692(n) = 2^a(n). (End)
a(n) < A329605(n), a(n) = A001222(A108951(n)), a(A329902(n)) = A112778(n). - Antti Karttunen, Jan 14 2020

A006530 Gpf(n): greatest prime dividing n, for n >= 2; a(1)=1.

Original entry on oeis.org

1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 5, 2, 17, 3, 19, 5, 7, 11, 23, 3, 5, 13, 3, 7, 29, 5, 31, 2, 11, 17, 7, 3, 37, 19, 13, 5, 41, 7, 43, 11, 5, 23, 47, 3, 7, 5, 17, 13, 53, 3, 11, 7, 19, 29, 59, 5, 61, 31, 7, 2, 13, 11, 67, 17, 23, 7, 71, 3, 73, 37, 5, 19, 11, 13, 79, 5, 3, 41, 83, 7, 17, 43

Offset: 1

N. J. A. Sloane

The initial term a(1)=1 is purely conventional: The unit 1 is not a prime number, although it has been considered so in the past. 1 is the empty product of prime numbers, thus 1 has no largest prime factor. - Daniel Forgues, Jul 05 2011
Greatest noncomposite number dividing n, (cf. A008578). - Omar E. Pol, Aug 31 2013
Conjecture: Let a, b be nonzero integers and f(n) denote the maximum prime factor of a*n + b if a*n + b <> 0 and f(n)=0 if a*n + b=0 for any integer n. Then the set {n, f(n), f(f(n)), ...} is finite of bounded size. - M. Farrokhi D. G., Jan 10 2021

M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 844.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section IV.1.
H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 210.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
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].
K. Alladi and P. Erdős, On an additive arithmetic function, Pacific J. Math., Volume 71, Number 2 (1977), 275-294. MR 0447086 (56 #5401).
G. Back and M. Caragiu, The greatest prime factor and recurrent sequences, Fib. Q., 48 (2010), 358-362.
A. E. Brouwer, Two number theoretic sums, Stichting Mathematisch Centrum. Zuivere Wiskunde, Report ZW 19/74 (1974): 3 pages. [Cached copy, included with the permission of the author]
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]
Mats Granvik, Mathematica program to check the conjectured formula, Feb 28 2021.
Nathan McNew, The Most Frequent Values of the Largest Prime Divisor Function, Exper. Math., 2017, Vol. 26, No. 2, 210-224.
OEIS Wiki, Greatest prime factor of n
H. P. Robinson, Letter to N. J. A. Sloane, Oct 1981
David Singmaster, Letter to N. J. A. Sloane, Oct 03 1982.
Eric Weisstein's World of Mathematics, Greatest Prime Factor
Index entries for "core" sequences

Cf. A000040, A020639 (smallest prime divisor), A034684, A028233, A034699, A053585.
See also A032742, A052126, A070087, A070089, A061395, A175723.
Cf. A046670 (partial sums), A104350 (partial products).
See A385503 for "popular" primes.

[ #f eq 0 select 1 else f[ #f][1] where f is Factorization(n): n in [1..86] ]; // Klaus Brockhaus, Oct 23 2008

with(numtheory,divisors); A006530 := proc(n) local i,t1,t2,t3,t4,t5; t1 := divisors(n); t2 := convert(t1,list); t3 := sort(t2); t4 := nops(t3); t5 := 1; for i from 1 to t4 do if isprime(t3[t4+1-i]) then return t3[t4+1-i]; fi; od; 1; end;
# alternative
A006530 := n->max(1,op(numtheory[factorset](n))); # Peter Luschny, Nov 02 2010

Table[ FactorInteger[n][[ -1, 1]], {n, 100}] (* Ray Chandler, Nov 12 2005 and modified by Robert G. Wilson v, Jul 16 2014 *)

A006530(n)=if(n>1,vecmax(factor(n)[,1]),1) \\ Edited to cover n=1. - M. F. Hasler, Jul 30 2015

from sympy import factorint
def a(n): return 1 if n == 1 else max(factorint(n))
print([a(n) for n in range(1, 87)]) # Michael S. Branicky, Aug 08 2022

def A006530(n): return list(factor(n))[-1][0] if n > 1 else 1
print([A006530(n) for n in range(1, 87)])  # Peter Luschny, Jan 07 2024

;; The following uses macro definec for the memoization (caching) of the results. A naive implementation of A020639 can be found under that entry. It could be also defined with definec to make it faster on the later calls. See http://oeis.org/wiki/Memoization#Scheme
(definec (A006530 n) (let ((spf (A020639 n))) (if (= spf n) spf (A006530 (/ n spf)))))
;; Antti Karttunen, Mar 12 2017

a(n) = A027748(n, A001221(n)) = A027746(n, A001222(n)); a(n)^A071178(n) = A053585(n). - Reinhard Zumkeller, Aug 27 2011
a(n) = A000040(A061395(n)). - M. F. Hasler, Jan 16 2015
a(n) = n + 1 - Sum_{k=1..n} (floor((k!^n)/n) - floor(((k!^n)-1)/n)). - Anthony Browne, May 11 2016
n/a(n) = A052126(n). - R. J. Mathar, Oct 03 2016
If A020639(n) = n [when n is 1 or a prime] then a(n) = n, otherwise a(n) = a(A032742(n)). - Antti Karttunen, Mar 12 2017
a(n) has average order Pi^2*n/(12 log n) [Brouwer]. See also A046670. - N. J. A. Sloane, Jun 26 2017

Edited by M. F. Hasler, Jan 16 2015

A007947 Largest squarefree number dividing n: the squarefree kernel of n, rad(n), radical of n.

Original entry on oeis.org

1, 2, 3, 2, 5, 6, 7, 2, 3, 10, 11, 6, 13, 14, 15, 2, 17, 6, 19, 10, 21, 22, 23, 6, 5, 26, 3, 14, 29, 30, 31, 2, 33, 34, 35, 6, 37, 38, 39, 10, 41, 42, 43, 22, 15, 46, 47, 6, 7, 10, 51, 26, 53, 6, 55, 14, 57, 58, 59, 30, 61, 62, 21, 2, 65, 66, 67, 34, 69, 70, 71, 6, 73, 74, 15, 38, 77, 78

Offset: 1

R. Muller, Mar 15 1996

Multiplicative with a(p^e) = p.
Product of the distinct prime factors of n.
a(k)=k for k=squarefree numbers A005117. - Lekraj Beedassy, Sep 05 2006
A note on square roots of numbers: we can write sqrt(n) = b*sqrt(c) where c is squarefree. Then b = A000188(n) is the "inner square root" of n, c = A007913(n), b*c = A019554(n) = "outer square root" of n, and a(n) = lcm(a(b),c). Unless n is biquadrateful (A046101), a(n) = lcm(b,c). [Edited by Jeppe Stig Nielsen, Oct 10 2021, and Andrey Zabolotskiy, Feb 12 2025]
a(n) = A128651(A129132(n-1) + 2) for n > 1. - Reinhard Zumkeller, Mar 30 2007
Also the least common multiple of the prime factors of n. - Peter Luschny, Mar 22 2011
The Mobius transform of the sequence generates the sequence of absolute values of A097945. - R. J. Mathar, Apr 04 2011
Appears to be the period length of k^n mod n. For example, n^12 mod 12 has period 6, repeating 1,4,9,4,1,0, so a(12)= 6. - Gary Detlefs, Apr 14 2013
a(n) differs from A014963(n) when n is a term of A024619. - Eric Desbiaux, Mar 24 2014
a(n) is also the smallest base (also termed radix) for which the representation of 1/n is of finite length.  For example a(12) = 6 and 1/12 in base 6 is 0.03, which is of finite length. - Lee A. Newberg, Jul 27 2016
a(n) is also the divisor k of n such that d(k) = 2^omega(n). a(n) is also the smallest divisor u of n such that n divides u^n. - Juri-Stepan Gerasimov, Apr 06 2017

			G.f. = x + 2*x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 6*x^6 + 7*x^7 + 2*x^8 + 3*x^9 + ... - _Michael Somos_, Jul 15 2018

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
Masum Billal, Divisible Sequence and its Characteristic Sequence, arXiv:1501.00609 [math.NT], 2015, theorem 11 page 5.
Henry Bottomley, Some Smarandache-type multiplicative sequences
Steven R. Finch, Unitarism and Infinitarism, February 25, 2004. [Cached copy, with permission of the author]
Jarosław Grytczuk, Thue type problems for graphs, points and numbers, Discrete Math., 308 (2008), 4419-4429.
Neville Holmes, Integer Sequences [Broken link]
Serge Lang, Old and New Conjectured Diophantine Inequalities, Bull. Amer. Math. Soc., 23 (1990), 37-75. see p. 39.
Wolfdieter Lang, Cantor's List of Real Algebraic Numbers of Heights 1 to 7, arXiv:2307.10645 [math.NT], 2023.
D. H. Lehmer, Euler constants for arithmetical progressions, Collection of articles in memory of Juriĭ Vladimirovič Linnik. Acta Arith. 27 (1975), 125--142. MR0369233 (51 #5468). See N_k on page 131.
Ivar Peterson, The Amazing ABC Conjecture
Paul Tarau, Emulating Primality with Multiset Representations of Natural Numbers, in Theoretical Aspects of Computing, ICTAC 2011, Lecture Notes in Computer Science, 2011, Volume 6916/2011, 218-238
Paul Tarau, Towards a generic view of primality through multiset decompositions of natural numbers, Theoretical Computer Science, Volume 537, 5 June 2014, Pages 105-124.
Wikipedia, Radical of an integer.

See A007913, A062953, A000188, A019554, A003557, A066503, A087207 for other properties related to square and squarefree divisors of n.
More general factorization-related properties, specific to n: A020639, A028234, A020500, A010051, A284318, A000005, A001221, A005361, A034444, A014963, A128651, A267116.
Range of values is A005117.
Cf. A048803, A019565, A024619, A053462, A060735, A073355 (partial sums), A079277, A097945, A129132, A225546.
Bisections: A099984, A099985.
Sequences about numbers that have the same squarefree kernel: A065642, array A284311 (A284457).
A003961, A059896 are used to express relationship between terms of this sequence.
Cf. A001615, A008683, A076479, A078615.

a007947 = product . a027748_row  -- Reinhard Zumkeller, Feb 27 2012

[ &*PrimeDivisors(n): n in [1..100] ]; // Klaus Brockhaus, Dec 04 2008

with(numtheory); A007947 := proc(n) local i,t1,t2; t1 := ifactors(n)[2]; t2 := mul(t1[i][1],i=1..nops(t1)); end;
A007947 := n -> ilcm(op(numtheory[factorset](n))):
seq(A007947(i),i=1..69); # Peter Luschny, Mar 22 2011
A:= n -> convert(numtheory:-factorset(n),`*`):
seq(A(n),n=1..100); # Robert Israel, Aug 10 2014
seq(NumberTheory:-Radical(n), n = 1..78); # Peter Luschny, Jul 20 2021

rad[n_] := Times @@ (First@# & /@ FactorInteger@ n); Array[rad, 78] (* Robert G. Wilson v, Aug 29 2012 *)
Table[Last[Select[Divisors[n],SquareFreeQ]],{n,100}] (* Harvey P. Dale, Jul 14 2014 *)
a[ n_] := If[ n < 1, 0, Sum[ EulerPhi[d] Abs @ MoebiusMu[d], {d, Divisors[ n]}]]; (* Michael Somos, Jul 15 2018 *)
Table[Product[p, {p, Select[Divisors[n], PrimeQ]}], {n, 1, 100}] (* Vaclav Kotesovec, May 20 2020 *)

a(n) = factorback(factorint(n)[,1]); \\ Andrew Lelechenko, May 09 2014

for(n=1, 100, print1(direuler(p=2, n, (1 + p*X - X)/(1 - X))[n], ", ")) \\ Vaclav Kotesovec, Jun 14 2020

from sympy import primefactors, prod
def a(n): return 1 if n < 2 else prod(primefactors(n))
[a(n) for n in range(1, 51)]  # Indranil Ghosh, Apr 16 2017

def A007947(n): return mul(p for p in prime_divisors(n))
[A007947(n) for n in (1..60)] # Peter Luschny, Mar 07 2017

(define (A007947 n) (if (= 1 n) n (* (A020639 n) (A007947 (A028234 n))))) ;; ;; Needs also code from A020639 and A028234. - Antti Karttunen, Jun 18 2017

If n = Product_j (p_j^k_j) where p_j are distinct primes, then a(n) = Product_j (p_j).
a(n) = Product_{k=1..A001221(n)} A027748(n,k). - Reinhard Zumkeller, Aug 27 2011
Dirichlet g.f.: zeta(s)*Product_{primes p} (1+p^(1-s)-p^(-s)). - R. J. Mathar, Jan 21 2012
a(n) = Sum_{d|n} phi(d) * mu(d)^2 = Sum_{d|n} |A097945(d)|. - Enrique Pérez Herrero, Apr 23 2012
a(n) = Product_{d|n} d^moebius(n/d) (see Billal link). - Michel Marcus, Jan 06 2015
a(n) = n/( Sum_{k=1..n} (floor(k^n/n)-floor((k^n - 1)/n)) ) = e^(Sum_{k=2..n} (floor(n/k) - floor((n-1)/k))*A010051(k)*M(k)) where M(n) is the Mangoldt function. - Anthony Browne, Jun 17 2016
a(n) = n/A003557(n). - Juri-Stepan Gerasimov, Apr 07 2017
G.f.: Sum_{k>=1} phi(k)*mu(k)^2*x^k/(1 - x^k). - Ilya Gutkovskiy, Apr 11 2017
From Antti Karttunen, Jun 18 2017: (Start)
a(1) = 1; for n > 1, a(n) = A020639(n) * a(A028234(n)).
a(n) = A019565(A087207(n)). (End)
Dirichlet g.f.: zeta(s-1) * zeta(s) * Product_{primes p} (1 + p^(1-2*s) - p^(2-2*s) - p^(-s)). - Vaclav Kotesovec, Dec 18 2019
From Peter Munn, Jan 01 2020: (Start)
a(A059896(n,k)) = A059896(a(n), a(k)).
a(A003961(n)) = A003961(a(n)).
a(n^2) = a(n).
a(A225546(n)) = A019565(A267116(n)). (End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = A065463/2. - Vaclav Kotesovec, Jun 24 2020
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} mu(n/gcd(n,k))^2.
a(n) = Sum_{k=1..n} mu(gcd(n,k))^2*phi(gcd(n,k))/phi(n/gcd(n,k)).
For n>1, Sum_{k=1..n} a(gcd(n,k))*mu(a(gcd(n,k)))*phi(gcd(n,k))/gcd(n,k) = 0.
For n>1, Sum_{k=1..n} a(n/gcd(n,k))*mu(a(n/gcd(n,k)))*phi(gcd(n,k))*gcd(n,k) = 0. (End)
a(n) = (-1)^omega(n) * Sum_{d|n} mu(d)*psi(d), where omega = A001221 and psi = A001615. - Ridouane Oudra, Aug 01 2025

More terms from several people including David W. Wilson

Definition expanded by Jonathan Sondow, Apr 26 2013

A020639 Lpf(n): least prime dividing n (when n > 1); a(1) = 1. Or, smallest prime factor of n, or smallest prime divisor of n.

Original entry on oeis.org

1, 2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 3, 2, 17, 2, 19, 2, 3, 2, 23, 2, 5, 2, 3, 2, 29, 2, 31, 2, 3, 2, 5, 2, 37, 2, 3, 2, 41, 2, 43, 2, 3, 2, 47, 2, 7, 2, 3, 2, 53, 2, 5, 2, 3, 2, 59, 2, 61, 2, 3, 2, 5, 2, 67, 2, 3, 2, 71, 2, 73, 2, 3, 2, 7, 2, 79, 2, 3, 2, 83, 2, 5, 2, 3, 2, 89, 2, 7, 2, 3, 2, 5, 2, 97

Offset: 1

David W. Wilson

Also, the largest number of distinct integers such that all their pairwise differences are coprime to n. - Max Alekseyev, Mar 17 2006
The unit 1 is not a prime number (although it has been considered so in the past). 1 is the empty product of prime numbers, thus 1 has no least prime factor. - Daniel Forgues, Jul 05 2011
a(n) = least m > 0 for which n! + m and n - m are not relatively prime. - Clark Kimberling, Jul 21 2012
For n > 1, a(n) = the smallest k > 1 that divides n. - Antti Karttunen, Feb 01 2014
For n > 1, records are at prime indices. - Zak Seidov, Apr 29 2015
The initials "lpf" might be mistaken for "largest prime factor" (A009190), using "spf" for "smallest prime factor" would avoid this. - M. F. Hasler, Jul 29 2015
n = 89 is the first index > 1 for which a(n) differs from the smallest k > 1 such that (2^k + n - 2)/k is an integer. - M. F. Hasler, Aug 11 2015
From Stanislav Sykora, Jul 29 2017: (Start)
For n > 1, a(n) is also the smallest k, 1 < k <= n, for which the binomial(n,k) is not divisible by n.
Proof: (A) When k and n are relatively prime then binomial(n,k) is divisible by n because k*binomial(n,k) = n*binomial(n-1,k-1). (B) When gcd(n,k) > 1, one of its prime factors is the smallest; let us denote it p, p <= k, and consider the binomial(n,p) = (1/p!)*Product_{i=0..p-1} (n-i). Since p is a divisor of n, it cannot be a divisor of any of the remaining numerator factors. It follows that, denoting as e the largest e > 0 such that p^e|n, the numerator is divisible by p^e but not by p^(e+1). Hence, the binomial is divisible by p^(e-1) but not by p^e and therefore not divisible by n. Applying (A), (B) to all considered values of k completes the proof. (End)
From Bob Selcoe, Oct 11 2017, edited by M. F. Hasler, Nov 06 2017: (Start)
a(n) = prime(j) when n == J (mod A002110(j)), n, j >= 1, where J is the set of numbers <= A002110(j) with smallest prime factor = prime(j). The number of terms in J is A005867(j-1). So:
a(n) = 2 when n == 0 (mod 2);
a(n) = 3 when n == 3 (mod 6);
a(n) = 5 when n == 5 or 25 (mod 30);
a(n) = 7 when n == 7, 49, 77, 91, 119, 133, 161 or 203 (mod 210);
etc. (End)
For n > 1, a(n) is the leftmost term, other than 0 or 1, in the n-th row of A127093. - Davis Smith, Mar 05 2019

D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section IV.1.

Daniel Forgues, Table of n, a(n) for n = 1..100000 (terms 1..10000 from T. D. Noe)
A. E. Brouwer, Two number theoretic sums, Stichting Mathematisch Centrum. Zuivere Wiskunde, Report ZW 19/74 (1974): 3 pages. [Copy included with the permission of the author.]
OEIS Wiki, Least prime factor of n
David Singmaster, Letter to N. J. A. Sloane, Oct 3 1982.
Eric Weisstein's World of Mathematics, Least Prime Factor
Index entries for "core" sequences

Cf. A090368 (bisection).
Cf. A000040, A009190, A006530, A034684, A028233, A034699, A053585.
See also A032742, A055396, A068319, A088377, A007978, A053669, A117818.
Cf. A046669 (partial sums), A072486 (partial products).
Cf. A002110, A005867.
Cf. A127093.

a020639 n = spf a000040_list where
  spf (p:ps) | n < p^2      = n
             | mod n p == 0 = p
             | otherwise    = spf ps
-- Reinhard Zumkeller, Jul 13 2011

A020639 := proc(n) if n = 1 then 1; else min(op(numtheory[factorset](n))) ; end if; end proc: seq(A020639(n),n=1..20) ; # R. J. Mathar, Oct 25 2010

f[n_]:=FactorInteger[n][[1,1]]; Join[{1}, Array[f,120,2]]  (* Robert G. Wilson v, Apr 06 2011 *)
Join[{1}, Table[If[EvenQ[n], 2, FactorInteger[n][[1,1]]], {n, 2, 120}]] (* Zak Seidov, Nov 17 2013 *)
Riffle[Join[{1},Table[FactorInteger[n][[1,1]],{n,3,101,2}]],2] (* Harvey P. Dale, Dec 16 2021 *)

A020639(n) = { vecmin(factor(n)[,1]) } \\ [Will yield an error for n = 1.] - R. J. Mathar, Mar 02 2012

A020639(n)=if(n>1, if(n>n=factor(n,0)[1,1], n, factor(n)[1,1]), 1) \\ Avoids complete factorization if possible. Often the smallest prime factor can be found quickly even if it is larger than primelimit. If factoring takes too long for large n, use debugging level >= 3 (\g3) to display the smallest factor as soon as it is found. - M. F. Hasler, Jul 29 2015

from sympy import factorint
def a(n): return 1 if n == 1 else min(factorint(n))
print([a(n) for n in range(1, 98)]) # Michael S. Branicky, Dec 09 2021

def A020639_list(n) : return [1] + [prime_divisors(n)[0] for n in (2..n)]
A020639_list(97) # Peter Luschny, Jul 16 2012

[trial_division(n) for n in (1..100)] # Giuseppe Coppoletta, May 25 2016

(define (A020639 n) (if (< n 2) n (let loop ((k 2)) (cond ((zero? (modulo n k)) k) (else (loop (+ 1 k))))))) ;; Antti Karttunen, Feb 01 2014

A014673(n) = a(A032742(n)); A115561(n) = a(A054576(n)). - Reinhard Zumkeller, Mar 10 2006
A028233(n) = a(n)^A067029(n). - Reinhard Zumkeller, May 13 2006
a(n) = A027746(n,1) = A027748(n,1). - Reinhard Zumkeller, Aug 27 2011
For n > 1: a(n) = A240694(n,2). - Reinhard Zumkeller, Apr 10 2014
a(n) = A000040(A055396(n)) = n / A032742(n). - Antti Karttunen, Mar 07 2017
a(n) has average order n/(2 log n) [Brouwer] - N. J. A. Sloane, Sep 03 2017

Deleted wrong comment from M. Lagneau in 2012, following an observation by Gionata Neri. - M. F. Hasler, Aug 11 2015
Edited by M. F. Hasler, Nov 06 2017
Expanded definition to make this easier to find. - N. J. A. Sloane, Sep 21 2020

A003961 Completely multiplicative with a(prime(k)) = prime(k+1).

Original entry on oeis.org

1, 3, 5, 9, 7, 15, 11, 27, 25, 21, 13, 45, 17, 33, 35, 81, 19, 75, 23, 63, 55, 39, 29, 135, 49, 51, 125, 99, 31, 105, 37, 243, 65, 57, 77, 225, 41, 69, 85, 189, 43, 165, 47, 117, 175, 87, 53, 405, 121, 147, 95, 153, 59, 375, 91, 297, 115, 93, 61, 315, 67, 111, 275, 729, 119

Offset: 1

Marc LeBrun

Meyers (see Guy reference) conjectures that for all r >= 1, the least odd number not in the set {a(i): i < prime(r)} is prime(r+1). - N. J. A. Sloane, Jan 08 2021
Meyers' conjecture would be refuted if and only if for some r there were such a large gap between prime(r) and prime(r+1) that there existed a composite c for which prime(r) < c < a(c) < prime(r+1), in which case (by Bertrand's postulate) c would necessarily be a term of A246281. - Antti Karttunen, Mar 29 2021
a(n) is odd for all n and for each odd m there exists a k with a(k) = m (see A064216). a(n) > n for n > 1: bijection between the odd and all numbers. - Reinhard Zumkeller, Sep 26 2001
a(n) and n have the same number of distinct primes with (A001222) and without multiplicity (A001221). - Michel Marcus, Jun 13 2014
From Antti Karttunen, Nov 01 2019: (Start)
More generally, a(n) has the same prime signature as n, A046523(a(n)) = A046523(n). Also A246277(a(n)) = A246277(n) and A287170(a(n)) = A287170(n).
Many permutations and other sequences that employ prime factorization of n to encode either polynomials, partitions (via Heinz numbers) or multisets in general can be easily defined by using this sequence as one of their constituent functions. See the last line in the Crossrefs section for examples.
(End)

			a(12) = a(2^2 * 3) = a(prime(1)^2 * prime(2)) = prime(2)^2 * prime(3) = 3^2 * 5 = 45.
a(A002110(n)) = A002110(n + 1) / 2.

Richard K. Guy, editor, Problems From Western Number Theory Conferences, Labor Day, 1983, Problem 367 (Proposed by Leroy F. Meyers, The Ohio State U.).

Indranil Ghosh, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)
Index entries for sequences computed from indices in prime factorization.
Index entries for sequences related to Heinz numbers.

See A045965 for another version.
Row 1 of table A242378 (which gives the "k-th powers" of this sequence), row 3 of A297845 and of A306697. See also arrays A066117, A246278, A255483, A308503, A329050.
Cf. A064989 (a left inverse), A064216, A000040, A002110, A000265, A027746, A046523, A048673 (= (a(n)+1)/2), A108228 (= (a(n)-1)/2), A191002 (= a(n)*n), A252748 (= a(n)-2n), A286385 (= a(n)-sigma(n)), A283980 (= a(n)*A006519(n)), A341529 (= a(n)*sigma(n)), A326042, A049084, A001221, A001222, A122111, A225546, A260443, A245606, A244319, A246269 (= A065338(a(n))), A322361 (= gcd(n, a(n))), A305293.
Cf. A191555, A252738.
Cf. A249734, A249735 (bisections).
Cf. A246261 (a(n) is of the form 4k+1), A246263 (of the form 4k+3), A246271, A246272, A246259, A246281 (n such that a(n) < 2n), A246282 (n such that a(n) > 2n), A252742.
Cf. A275717 (a(n) > a(n-1)), A275718 (a(n) < a(n-1)).
Cf. A003972 (Möbius transform), A003973 (Inverse Möbius transform), A318321.
Cf. A300841, A305421, A322991, A250469, A269379 for analogous shift-operators in other factorization and quasi-factorization systems.
Cf. also following permutations and other sequences that can be defined with the help of this sequence: A005940, A163511, A122111, A260443, A206296, A265408, A265750, A275733, A275735, A297845, A091202 & A091203, A250245 & A250246, A302023 & A302024, A302025 & A302026.
A version for partition numbers is A003964, strict A357853.
A permutation of A005408.
Applying the same transformation again gives A357852.
Other multiplicative sequences: A064988, A357977, A357978, A357980, A357983.
A056239 adds up prime indices, row-sums of A112798.
Cf. A000720, A076610, A296150.

a003961 1 = 1
a003961 n = product $ map (a000040 . (+ 1) . a049084) $ a027746_row n
-- Reinhard Zumkeller, Apr 09 2012, Oct 09 2011
(MIT/GNU Scheme, with Aubrey Jaffer's SLIB Scheme library)
(require 'factor)
(define (A003961 n) (apply * (map A000040 (map 1+ (map A049084 (factor n))))))
;; Antti Karttunen, May 20 2014

a:= n-> mul(nextprime(i[1])^i[2], i=ifactors(n)[2]):
seq(a(n), n=1..80);  # Alois P. Heinz, Sep 13 2017

a[p_?PrimeQ] := a[p] = Prime[ PrimePi[p] + 1]; a[1] = 1; a[n_] := a[n] = Times @@ (a[#1]^#2& @@@ FactorInteger[n]); Table[a[n], {n, 1, 65}] (* Jean-François Alcover, Dec 01 2011, updated Sep 20 2019 *)
Table[Times @@ Map[#1^#2 & @@ # &, FactorInteger[n] /. {p_, e_} /; e > 0 :> {Prime[PrimePi@ p + 1], e}] - Boole[n == 1], {n, 65}] (* Michael De Vlieger, Mar 24 2017 *)

a(n)=local(f); if(n<1,0,f=factor(n); prod(k=1,matsize(f)[1],nextprime(1+f[k,1])^f[k,2]))

a(n) = my(f = factor(n)); for (i=1, #f~, f[i, 1] = nextprime(f[i, 1]+1)); factorback(f); \\ Michel Marcus, May 17 2014

use ntheory ":all";  sub a003961 { vecprod(map { next_prime($) } factor(shift)); }  # _Dana Jacobsen, Mar 06 2016

from sympy import factorint, prime, primepi, prod
def a(n):
    f=factorint(n)
    return 1 if n==1 else prod(prime(primepi(i) + 1)**f[i] for i in f)
[a(n) for n in range(1, 11)] # Indranil Ghosh, May 13 2017

If n = Product p(k)^e(k) then a(n) = Product p(k+1)^e(k).
Multiplicative with a(p^e) = A000040(A000720(p)+1)^e. - David W. Wilson, Aug 01 2001
a(n) = Product_{k=1..A001221(n)} A000040(A049084(A027748(n,k))+1)^A124010(n,k). - Reinhard Zumkeller, Oct 09 2011 [Corrected by Peter Munn, Nov 11 2019]
A064989(a(n)) = n and a(A064989(n)) = A000265(n). - Antti Karttunen, May 20 2014 & Nov 01 2019
A001221(a(n)) = A001221(n) and A001222(a(n)) = A001222(n). - Michel Marcus, Jun 13 2014
From Peter Munn, Oct 31 2019: (Start)
a(n) = A225546((A225546(n))^2).
a(A225546(n)) = A225546(n^2).
(End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = (1/2) * Product_{p prime} ((p^2-p)/(p^2-nextprime(p))) = 2.06399637... . - Amiram Eldar, Nov 18 2022

cp's OEIS Frontend

A308495 a(n) is the position of the first occurrence of prime(n) in A027748.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A331016 Lexicographically earliest sequence of distinct positive terms that can be viewed as an irregular table where the n-th row has max(1, A001221(a(n))) terms and for n > 1, T(n, k) is a multiple of the k-th prime factor of a(n) (=A027748(a(n), k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A000203 a(n) = sigma(n), the sum of the divisors of n. Also called sigma_1(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Magma

Maple

Mathematica

Maxima

MuPAD

PARI

PARI

PARI

PARI

Python

Python

SageMath

Scheme

Scheme

Formula

A001222 Number of prime divisors of n counted with multiplicity (also called big omega of n, bigomega(n) or Omega(n)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Julia

Magma

Maple

Mathematica

PARI

Python

SageMath

SageMath

Scheme

Formula

Extensions

A056239 If n = Product_{k >= 1} (p_k)^(c_k) where p_k is k-th prime and c_k >= 0 then a(n) = Sum_{k >= 1} k*c_k.

Views

Author

Keywords

Comments