A039653 -id:A039653 - cp's OEIS frontend

A296082 a(1) = 0; for n > 1, a(n) = A032741(n) / gcd(A039653(n),A032741(n)).

0, 1, 1, 1, 1, 3, 1, 3, 1, 3, 1, 5, 1, 3, 3, 2, 1, 5, 1, 5, 3, 3, 1, 7, 1, 3, 1, 1, 1, 7, 1, 5, 3, 3, 3, 4, 1, 3, 3, 7, 1, 7, 1, 5, 5, 3, 1, 3, 1, 5, 3, 5, 1, 1, 3, 1, 3, 3, 1, 11, 1, 3, 5, 1, 3, 7, 1, 1, 3, 7, 1, 11, 1, 3, 5, 5, 3, 7, 1, 9, 1, 3, 1, 11, 3, 3, 3, 7, 1, 11, 1, 5, 3, 3, 3, 11, 1, 1, 1, 1, 1, 7, 1, 7, 7

Offset: 1

Antti Karttunen, Dec 05 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A032741, A039653, A296081, A296083, A296084.

Cf. A284288 (positions of ones).

(define (A296082 n) (if (= 1 n) 0 (/ (A032741 n) (gcd (A039653 n) (A032741 n)))))

a(1) = 0; for n > 1, a(n) = A032741(n) / gcd(A039653(n),A032741(n)) = A032741(n)/A296081(n).

a(n) = 1 iff A296084(n) = 1.

A296083 a(1) = 0; for n > 1, a(n) = A039653(n) / gcd(A039653(n),A032741(n)).

Original entry on oeis.org

0, 2, 3, 3, 5, 11, 7, 14, 6, 17, 11, 27, 13, 23, 23, 15, 17, 38, 19, 41, 31, 35, 23, 59, 15, 41, 13, 11, 29, 71, 31, 62, 47, 53, 47, 45, 37, 59, 55, 89, 41, 95, 43, 83, 77, 71, 47, 41, 28, 92, 71, 97, 53, 17, 71, 17, 79, 89, 59, 167, 61, 95, 103, 21, 83, 143, 67, 25, 95, 143, 71, 194, 73, 113, 123, 139, 95, 167, 79

Offset: 1

Antti Karttunen, Dec 05 2017

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384

Cf. A032741, A039653, A296081, A296082.

(define (A296083 n) (if (= 1 n) 0 (/ (A039653 n) (gcd (A039653 n) (A032741 n)))))

a(1) = 0; for n > 1, a(n) = A039653(n) / gcd(A039653(n),A032741(n)).

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

Original entry on oeis.org

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

A032741 a(0) = 0; for n > 0, a(n) = number of proper divisors of n (divisors of n which are less than n).

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 1, 3, 2, 3, 1, 5, 1, 3, 3, 4, 1, 5, 1, 5, 3, 3, 1, 7, 2, 3, 3, 5, 1, 7, 1, 5, 3, 3, 3, 8, 1, 3, 3, 7, 1, 7, 1, 5, 5, 3, 1, 9, 2, 5, 3, 5, 1, 7, 3, 7, 3, 3, 1, 11, 1, 3, 5, 6, 3, 7, 1, 5, 3, 7, 1, 11, 1, 3, 5, 5, 3, 7, 1, 9, 4, 3, 1, 11, 3, 3, 3, 7, 1, 11, 3, 5, 3, 3, 3, 11, 1, 5, 5

Offset: 0

Patrick De Geest, May 15 1998

Number of d < n which divide n.
Call an integer k between 1 and n a "semi-divisor" of n if n leaves a remainder of 1 when divided by k, i.e., n == 1 (mod k). a(n) gives the number of semi-divisors of n+1. - Joseph L. Pe, Sep 11 2002
a(n+1) is also the number of k, 0 <= k <= n-1, such that C(n,k) divides C(n,k+1). - Benoit Cloitre, Oct 17 2002
a(n+1) is also the number of factors of the n-th degree polynomial x^n + x^(n-1) + x^(n-2) + ... + x^2 + x + 1. Example: 1 + x + x^2 + x^3 = (1+x)(1+x^2) implies a(4)=2.
a(n) is also the number of factors of the n-th Fibonacci polynomial. - T. D. Noe, Mar 09 2006
Number of partitions of n into 2 parts with the second dividing the first. - Franklin T. Adams-Watters, Sep 20 2006
Number of partitions of n+1 into exactly one q and at least one q+1. Example: a(12)=5; indeed, we have 13 = 7 + 6 = 5 + 4 + 4 = 4 + 3 + 3 + 3 = 3 + 2 + 2 + 2 + 2 + 2 = 2 + 11*1.
Differences of A002541. - George Beck, Feb 12 2012
For n > 1: number of ones in row n+1 of triangle A051778. - Reinhard Zumkeller, Dec 03 2014
For n > 0, a(n) is the number of strong divisors of n. - Omar E. Pol, May 03 2015
a(n) is also the number of factors of the (n-1)-th degree polynomial ((x+1)^n-1)/x. Example: for n=6, ((x+1)^6-1)/x = x^5 + 6*x^4 + 15*x^3 + 20*x^2 + 15*x + 6 = (2+x)(1+x+x^2)(3+3x+x^2) implies a(6)=3. - Federico Provvedi, Oct 09 2018
Consider the polynomial P(n,z) = Sum_{i=1..q} d(i)*z^(i-1) where d(1), d(2), ..., d(q) are are the q ordered divisors of n. The sequence lists the numbers of zeros of P(n,z) strictly inside the unit circle. - Michel Lagneau, Apr 06 2025

			a(6) = 3 since the proper divisors of 6 are 1, 2, 3.

André Weil, Number Theory, An approach through history, From Hammurapi to Legendre, Birkhäuser, 1984, page 5.

T. D. Noe, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Proper divisors.

Column 2 of A122934.
Cf. A003238, A001065, A027749, A027751 (list of proper divisors).
Cf. A001620, A039653, A051778, A070824, A091818.

Concatenation([0],List([1..100],n->Tau(n)-1)); # Muniru A Asiru, Oct 09 2018

a032741 n = if n == 0 then 0 else a000005 n - 1
-- Reinhard Zumkeller, Jul 31 2014

A032741 := proc(n)
    if n = 0 then
        0 ;
    else
        numtheory[tau](n)-1 ;
    end if;
end proc: # R. J. Mathar, Feb 03 2013

Prepend[DivisorSigma[0, Range[99]]-1, 0] (* Jayanta Basu, May 25 2013 *)

PARI
```
a(n) = if(n<1,0,numdiv(n)-1)
```

{a(n)=polcoeff(2*sum(m=1,n\2+1,sumdiv(m,d,log(1-x^(m/d) +x*O(x^n) )^(2*d)/(2*d)!)), n)} \\ Paul D. Hanna, Aug 21 2014

from sympy import divisor_count
def A032741(n): return divisor_count(n)-1 if n else 0 # Chai Wah Wu, Mar 14 2023

a(n) = tau(n)-1 = A000005(n)-1. Cf. A039653.
G.f.: Sum_{n>=1} x^(2*n)/(1-x^n). - Michael Somos, Apr 29 2003
G.f.: Sum_{i>=1} (1-x^i+x^(2*i))/(1-x^i). - Jon Perry, Jul 03 2004
a(n) = Sum_{k=1..floor(n/2)} A051731(n-k,k). - Reinhard Zumkeller, Nov 01 2009
G.f.: 2*Sum_{n>=1} Sum_{d|n} log(1 - x^(n/d))^(2*d) / (2*d)!. - Paul D. Hanna, Aug 21 2014
Dirichlet g.f.: zeta(s)*(zeta(s)-1). - Geoffrey Critzer, Dec 06 2014
a(n) = Sum_{k=1..n-1} binomial((n-1) mod k, k-1). - Wesley Ivan Hurt, Sep 26 2016
a(n) = Sum_{i=1..n-1} floor(n/i)-floor((n-1)/i). - Wesley Ivan Hurt, Nov 15 2017
a(n) = Sum_{i=1..n-1} 1-sign(i mod (n-i)). - Wesley Ivan Hurt, Sep 27 2018
Sum_{k=1..n} a(k) ~ n*log(n) + 2*(gamma - 1)*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 27 2022

Typos in definition corrected by Omar E. Pol, Dec 13 2008

A039649 a(n) = phi(n)+1.

Original entry on oeis.org

2, 2, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 9, 9, 17, 7, 19, 9, 13, 11, 23, 9, 21, 13, 19, 13, 29, 9, 31, 17, 21, 17, 25, 13, 37, 19, 25, 17, 41, 13, 43, 21, 25, 23, 47, 17, 43, 21, 33, 25, 53, 19, 41, 25, 37, 29, 59, 17, 61, 31, 37, 33, 49, 21, 67, 33, 45, 25, 71, 25, 73, 37, 41

Offset: 1

David W. Wilson

a(p) = p for p prime.
Records give A000040. - Omar E. Pol, Jul 10 2014
Which n are divisible by phi(n)+1? See A085118 for a possible answer and references. - Peter Munn, Jun 03 2021

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A000010, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A085118.

a039649 = (+ 1) . a000010  -- Reinhard Zumkeller, Oct 07 2015

[EulerPhi(n)+1: n in [1..100]]; // Vincenzo Librandi, Aug 13 2013

Table[EulerPhi[n] + 1, {n, 100}] (* Vincenzo Librandi, Aug 13 2013 *)

a(n)=eulerphi(n)+1 \\ Charles R Greathouse IV, Mar 04 2017

a(n) = A000010(n) + 1.
a(n) <= n for n > 1.
G.f.: x/(1 - x) + Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 16 2017

Edited by Charles R Greathouse IV, Mar 18 2010.

A039654 a(n) = prime reached by iterating f(x) = sigma(x)-1 starting at n, or -1 if no prime is ever reached.

Original entry on oeis.org

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

Offset: 2

David W. Wilson

nonn

It appears nearly certain that a prime is always reached for n>1.
Since sigma(n) > n for n > 1, and sigma(n) = n + 1 only for n prime, the iteration either reaches a prime and loops there, or grows indefinitely. - Franklin T. Adams-Watters, May 10 2010
Guy (2004) attributes this conjecture to Erdos. See Erdos et al. (1990). - N. J. A. Sloane, Aug 30 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 149.

Franklin T. Adams-Watters, Table of n, a(n) for n=2..10000
Lucilla Baldini and Josef Eschgfäller, Random functions from coupled dynamical systems, arXiv preprint arXiv:1609.01750 [math.CO], 2016. Mentions the conjecture.
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 Erdos, 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]
Math Overflow discussion, Does iterating a certain function related to the sums of divisors eventually always result in a prime value?
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A039655 (the number of steps needed), A039649, A039650, A039651, A039652, A039653, A039656, A291301, A291302, A291776, A291777.
For records see A292112, A292113.
Cf. A177343: number of times the n-th prime occurs in this sequence.
Cf. A292874: least k such that a(k) = prime(n).

f[n_]:=Plus@@Divisors[n]-1;Table[Nest[f,n,6],{n,2,5!}] (* Vladimir Joseph Stephan Orlovsky, Mar 10 2010 *)
f[n_] := DivisorSigma[1,n]-1; Table[FixedPoint[f,n], {n,2,100}] (* T. D. Noe, May 10 2010 *)

a(n)=local(m);if(n<2,0,while((m=sigma(n)-1)!=n,n=m);n) \\ Franklin T. Adams-Watters, May 10 2010

A039654(n)=n>1&&until(n==n=sigma(n)-1,);n \\ M. F. Hasler, Sep 25 2017

Contingency for no prime reached added by Franklin T. Adams-Watters, May 10 2010

Changed escape value from 0 to -1 to be consistent with several related sequences. - N. J. A. Sloane, Aug 31 2017

A039650 Prime reached by iterating f(x) = phi(x)+1 on n.

Original entry on oeis.org

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

Offset: 1

David W. Wilson

nonn

Or, a(n) = lim_k {s(k,n)} where s(k,n) is defined inductively on k by: s(1,n) = n; s(k+1,n) = 1 + phi(s(k,n)). - Joseph L. Pe, Apr 30 2002
Sequence A229487 gives the conjectured largest number that converges to prime(n). - T. D. Noe, Oct 17 2013
For n>1, phi(n) <= n-1, with equality iff n is prime. So the trajectory decreases until it hits a prime. So a(n) always exists. - N. J. A. Sloane, Sep 22 2017

			s(24,1) = 24, s(24,2) = 1 + phi(24) = 1 + 8 = 9, s(24,3) = 1 + phi(9) = 1 + 6 = 7, s(24,4) = 1 + phi(7) = 1 + 6 = 7,.... Therefore a(24) = lim_k {s(24,k)} = 7.

Alexander S. Karpenko, Lukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 51.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A229487.

A039650 := proc(n)
    local nitr,niitr ;
    niitr := n ;
    while true do:
        nitr := 1+numtheory[phi](niitr) ;
        if nitr = niitr then
            return nitr ;
        end if;
        niitr := nitr ;
    end do:
end proc:
seq(A039650(n),n=1..40) ; # R. J. Mathar, Dec 11 2019

f[n_] := FixedPoint[1 + EulerPhi[ # ] &, n]; Table[ f[n], {n, 1, 75}]

A235796 2*n - 1 - sigma(n).

Original entry on oeis.org

0, 0, 1, 0, 3, -1, 5, 0, 4, 1, 9, -5, 11, 3, 5, 0, 15, -4, 17, -3, 9, 7, 21, -13, 18, 9, 13, -1, 27, -13, 29, 0, 17, 13, 21, -20, 35, 15, 21, -11, 39, -13, 41, 3, 11, 19, 45, -29, 40, 6, 29, 5, 51, -13, 37, -9, 33, 25, 57, -49, 59, 27, 21, 0, 45, -13, 65, 9, 41

Offset: 1

Omar E. Pol, Jan 25 2014

sign

Partial sums give A004125.
Also 0 together with A120444.
It appears that a(n) = 0 iff n is a power of 2.
Numbers n with a(n) = 0 are called "almost perfect", "least deficient" or "slightly defective" numbers.  See A000079. - Robert Israel, Jul 22 2014
a(n) = n - 2 iff n is prime.
a(n) = -1 iff n is a perfect number.
Also the alternating row sums of A239446. - Omar E. Pol, Jul 21 2014

			.     The positive     The sum of
n     odd numbers     divisors of n.      a(n)
1          1                1               0
2          3                3               0
3          5                4               1
4          7                7               0
5          9                6               3
6         11               12              -1
7         13                8               5
8         15               15               0
9         17               13               4
10        19               18               1
...

R. K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, New York, 2004.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A000079, A000203, A000396, A004125, A005408, A120444, A196020, A236104.

[2*n-1-SumOfDivisors(n): n in [1..100]]; // Vincenzo Librandi, Feb 25 2014

Table[2n-1-DivisorSigma[1,n],{n,70}] (* Harvey P. Dale, Jul 11 2014 *)

vector(100, n, (2*n-1)-sigma(n)) \\ Colin Barker, Jan 27 2014

a(n) = A005408(n-1) - A000203(n).
a(n) = -1 - A033880(n). - Michel Marcus, Jan 27 2014
a(n) =  n - 1 - A001065(n). - Omar E. Pol, Jan 29 2014
a(n) = A033879(n) - 1. - Omar E. Pol, Jan 30 2014
a(n) = 2*n - 2 - A039653(n). - Omar E. Pol, Jan 31 2014
a(n) = (-1)*A237588(n). - Omar E. Pol, Feb 23 2014
a(n) = 2*n - A088580(n). - Omar E. Pol, Mar 23 2014

A039655 Number of iterations of f(x) = sigma(x)-1 applied to n required to reach a prime, or -1 if no prime is ever reached.

Original entry on oeis.org

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

Offset: 2

David W. Wilson

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 2..10000
MathOverflow, Does iterating a certain function related to the sums of divisors eventually always result in a prime value?, 2014
Hugo Pfoertner, Terms a(2)...a(1000000).
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A039654, A039649, A039650, A039651, A039652, A039653, A039655, A039656.

For records see A292114 and A292115.

f[n_] := Plus @@ Divisors@n - 1; g[n_] := Length@ NestWhileList[ f@# &, n, !PrimeQ@# &] - 1; Table[ g@n, {n, 2, 106}] (* Robert G. Wilson v, May 07 2010 *)

a(n)=my(t);while(!isprime(n),n=sigma(n)-1;t++);t \\ Charles R Greathouse IV, Sep 16 2014

Escape clause added by N. J. A. Sloane, Aug 31 2017

A039651 Number of iterations of f(x) = phi(x)+1 on n required to reach a prime.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 2, 2, 0, 1, 0, 2, 1, 1, 0, 2, 2, 1, 1, 1, 0, 2, 0, 1, 2, 1, 3, 1, 0, 1, 3, 1, 0, 1, 0, 2, 3, 1, 0, 1, 1, 2, 3, 3, 0, 1, 1, 3, 1, 1, 0, 1, 0, 1, 1, 3, 2, 2, 0, 3, 4, 3, 0, 3, 0, 1, 1, 1, 1, 3, 0, 3, 2, 1, 0, 3, 3, 1, 2, 1, 0, 3, 1, 4, 1, 1, 1, 3, 0, 1, 1, 1, 0, 3, 0, 2, 2

Offset: 1

David W. Wilson

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A039649, A039650, A039651, A039652, A039653, A039654, A039655, A039656.

Table[Length[NestWhileList[EulerPhi[#] + 1 &, n, UnsameQ, All]] - 2, {n, 100}] (* T. D. Noe, Oct 17 2013 *)

cp's OEIS Frontend

A296082 a(1) = 0; for n > 1, a(n) = A032741(n) / gcd(A039653(n),A032741(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

A296083 a(1) = 0; for n > 1, a(n) = A039653(n) / gcd(A039653(n),A032741(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Scheme

Formula

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

A032741 a(0) = 0; for n > 0, a(n) = number of proper divisors of n (divisors of n which are less than n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A039649 a(n) = phi(n)+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

Formula

Extensions