A065608 Sum of divisors of n minus the number of divisors of n.

0, 1, 2, 4, 4, 8, 6, 11, 10, 14, 10, 22, 12, 20, 20, 26, 16, 33, 18, 36, 28, 32, 22, 52, 28, 38, 36, 50, 28, 64, 30, 57, 44, 50, 44, 82, 36, 56, 52, 82, 40, 88, 42, 78, 72, 68, 46, 114, 54, 87, 68, 92, 52, 112, 68, 112, 76, 86, 58, 156, 60, 92, 98, 120, 80, 136, 66, 120, 92

Offset: 1

Author

Jason Earls, Nov 06 2001

Keywords

• nonn
• easy

Comments

Number of permutations p of {1,2,...,n} such that p(k)-k takes exactly two distinct values. Example: a(4)=4 because we have 4123, 3412, 2143 and 2341. - Max Alekseyev and Emeric Deutsch, Dec 22 2006

Number of solutions to the Diophantine equation xy + yz = n, with x,y,z >= 1.

In other words, number of ways to write n = (a + b) * k for positive integers a, b, k. - Gus Wiseman, Mar 25 2021

Not the same as A184396(n): a(66) = 136 while A184396(66) = 137. - Wesley Ivan Hurt, Dec 26 2013

From Gus Wiseman, Mar 25 2021: (Start)

Also the number of compositions of n into an even number of parts with alternating parts equal. These are finite even-length sequences q of positive integers summing to n such that q(i) = q(i+2) for all possible i. For example, the a(2) = 1 through a(8) = 11 compositions are:

(1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7)

(2,1) (2,2) (2,3) (2,4) (2,5) (2,6)

(3,1) (3,2) (3,3) (3,4) (3,5)

(1,1,1,1) (4,1) (4,2) (4,3) (4,4)

(5,1) (5,2) (5,3)

(1,2,1,2) (6,1) (6,2)

(2,1,2,1) (7,1)

(1,1,1,1,1,1) (1,3,1,3)

(2,2,2,2)

(3,1,3,1)

(1,1,1,1,1,1,1,1)

The odd-length version is A062968.

The version with alternating parts weakly decreasing is A114921, or A342528 if odd-length compositions are included.

The version with alternating parts unequal is A342532, or A224958 if odd-length compositions are included (unordered: A339404/A000726).

Allowing odd lengths as well as even gives A342527.

(End)

Inverse Möbius transform of n-1. - Wesley Ivan Hurt, Jun 29 2024

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 1000 terms from T. D. Noe)
• M. Alekseyev, E. Deutsch, and J. H. Steelman, Solution to problem 11281, Amer. Math. Monthly, 116, No. 5, 2009, p. 465.
• George E. Andrews, Stacked lattice boxes, Ann. Comb. 3 (1999), 115-130. See L_2(n).
• Joerg Arndt, On computing the generalized Lambert series, arXiv:1202.6525v3 [math.CA], (2012).
• Masato Kobayashi, New recurrences for divisor sum functions and triangular numbers, arXiv:2207.05831 [math.NT], 2022.

Crossrefs

Cf. A000203, A000005, A134857.

Starting (1, 2, 4, 4, 8, 6, ...), = row sums of triangle A077478. - Gary W. Adamson, Nov 12 2007

Starting with "1" = row sums of triangle A176919. - Gary W. Adamson, Apr 29 2010

Column k=2 of A125182.

A175342/A325545 count compositions with constant/distinct differences.

Cf. A001522, A002843, A008965, A010054, A064410, A064428, A325557, A342495.

Programs

GAP

List([1..100],n->Sigma(n)-Tau(n)); # Muniru A Asiru, Mar 19 2018

Maple

with(numtheory): seq(sigma(n)-tau(n),n=1..70); # Emeric Deutsch, Dec 22 2006

Mathematica

Table[DivisorSigma[1,n]-DivisorSigma[0,n], {n,100}] (* Wesley Ivan Hurt, Dec 26 2013 *)

PARI

a(n) = sigma(n) - numdiv(n); \\ Harry J. Smith, Oct 23 2009

Python

from math import prod
from sympy import factorint
def A065608(n):
    f = factorint(n).items()
    return prod((p**(e+1)-1)//(p-1) for p, e in f)-prod(e+1 for p,e in f) # Chai Wah Wu, Jul 16 2022

Formula

a(n) = sigma(n) - d(n) = A000203(n) - A000005(n).

a(n) = Sum_{d|n} (d-1). - Wesley Ivan Hurt, Dec 26 2013

G.f.: Sum_{k>=1} x^(2*k)/(1-x^k)^2. - Benoit Cloitre, Apr 21 2003

G.f.: Sum_{n>=1} (n-1)*x^n/(1-x^n). - Joerg Arndt, Jan 30 2011

L.g.f.: -log(Product_{k>=1} (1 - x^k)^(1-1/k)) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Mar 18 2018

G.f.: Sum_{n >= 1} q^(n^2)*( (n - 1) + q^n - (n - 1)*q^(2*n) )/(1 - q^n)^2 - differentiate equation 1 in Arndt with respect to t, then set x = q and t = q. - Peter Bala, Jan 22 2021

a(n) = A342527(n) - A062968(n). - Gus Wiseman, Mar 25 2021

a(n) = n * A010054(n) - Sum_{k>=1} a(n - k*(k+1)/2), assuming a(n) = 0 for n <= 0 (Kobayashi, 2022). - Amiram Eldar, Jun 23 2023