login
Sum of divisors of n minus the number of divisors of n.
41

%I #85 Jun 29 2024 23:00:40

%S 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,

%T 38,36,50,28,64,30,57,44,50,44,82,36,56,52,82,40,88,42,78,72,68,46,

%U 114,54,87,68,92,52,112,68,112,76,86,58,156,60,92,98,120,80,136,66,120,92

%N Sum of divisors of n minus the number of divisors of n.

%C 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

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

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

%C Not the same as A184396(n): a(66) = 136 while A184396(66) = 137. - _Wesley Ivan Hurt_, Dec 26 2013

%C From _Gus Wiseman_, Mar 25 2021: (Start)

%C 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:

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

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

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

%C (1,1,1,1) (4,1) (4,2) (4,3) (4,4)

%C (5,1) (5,2) (5,3)

%C (1,2,1,2) (6,1) (6,2)

%C (2,1,2,1) (7,1)

%C (1,1,1,1,1,1) (1,3,1,3)

%C (2,2,2,2)

%C (3,1,3,1)

%C (1,1,1,1,1,1,1,1)

%C The odd-length version is A062968.

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

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

%C Allowing odd lengths as well as even gives A342527.

%C (End)

%C Inverse Möbius transform of n-1. - _Wesley Ivan Hurt_, Jun 29 2024

%H Alois P. Heinz, <a href="/A065608/b065608.txt">Table of n, a(n) for n = 1..20000</a> (first 1000 terms from T. D. Noe)

%H M. Alekseyev, E. Deutsch, and J. H. Steelman, <a href="http://www.jstor.org/stable/40391132">Solution to problem 11281</a>, Amer. Math. Monthly, 116, No. 5, 2009, p. 465.

%H George E. Andrews, <a href="http://dx.doi.org/10.1007/BF01608779">Stacked lattice boxes</a>, Ann. Comb. 3 (1999), 115-130. See L_2(n).

%H Joerg Arndt, <a href="http://arxiv.org/abs/1202.6525">On computing the generalized Lambert series</a>, arXiv:1202.6525v3 [math.CA], (2012).

%H Masato Kobayashi, <a href="https://arxiv.org/abs/2207.05831">New recurrences for divisor sum functions and triangular numbers</a>, arXiv:2207.05831 [math.NT], 2022.

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

%F a(n) = Sum_{d|n} (d-1). - _Wesley Ivan Hurt_, Dec 26 2013

%F G.f.: Sum_{k>=1} x^(2*k)/(1-x^k)^2. - _Benoit Cloitre_, Apr 21 2003

%F G.f.: Sum_{n>=1} (n-1)*x^n/(1-x^n). - _Joerg Arndt_, Jan 30 2011

%F 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

%F 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

%F a(n) = A342527(n) - A062968(n). - _Gus Wiseman_, Mar 25 2021

%F 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

%p with(numtheory): seq(sigma(n)-tau(n),n=1..70); # _Emeric Deutsch_, Dec 22 2006

%t Table[DivisorSigma[1,n]-DivisorSigma[0,n], {n,100}] (* _Wesley Ivan Hurt_, Dec 26 2013 *)

%o (PARI) a(n) = sigma(n) - numdiv(n); \\ _Harry J. Smith_, Oct 23 2009

%o (GAP) List([1..100],n->Sigma(n)-Tau(n)); # _Muniru A Asiru_, Mar 19 2018

%o (Python)

%o from math import prod

%o from sympy import factorint

%o def A065608(n):

%o f = factorint(n).items()

%o 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

%Y Cf. A000203, A000005, A134857.

%Y Starting (1, 2, 4, 4, 8, 6, ...), = row sums of triangle A077478. - _Gary W. Adamson_, Nov 12 2007

%Y Starting with "1" = row sums of triangle A176919. - _Gary W. Adamson_, Apr 29 2010

%Y Column k=2 of A125182.

%Y A175342/A325545 count compositions with constant/distinct differences.

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

%K nonn,easy

%O 1,3

%A _Jason Earls_, Nov 06 2001