%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