|
%I #110 Mar 14 2023 12:54:26
%S 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,
%T 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,
%U 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
%N a(0) = 0; for n > 0, a(n) = number of proper divisors of n (divisors of n which are less than n).
%C Number of d < n which divide n.
%C 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
%C 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
%C 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.
%C a(n) is also the number of factors of the n-th Fibonacci polynomial. - _T. D. Noe_, Mar 09 2006
%C Number of partitions of n into 2 parts with the second dividing the first. - _Franklin T. Adams-Watters_, Sep 20 2006
%C 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.
%C Differences of A002541. - _George Beck_, Feb 12 2012
%C For n > 1: number of ones in row n+1 of triangle A051778. - _Reinhard Zumkeller_, Dec 03 2014
%C For n > 0, a(n) is the number of strong divisors of n. - _Omar E. Pol_, May 03 2015
%C 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
%D André Weil, Number Theory, An approach through history, From Hammurapi to Legendre, Birkhäuser, 1984, page 5.
%H T. D. Noe, <a href="/A032741/b032741.txt">Table of n, a(n) for n = 0..10000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ProperDivisor.html">Proper divisors</a>.
%F a(n) = tau(n)-1 = A000005(n)-1. Cf. A039653.
%F G.f.: Sum_{n>=1} x^(2*n)/(1-x^n). - _Michael Somos_, Apr 29, 2003
%F G.f.: Sum_{i>=1} (1-x^i+x^(2*i))/(1-x^i). - _Jon Perry_, Jul 03 2004
%F a(n) = Sum_{k=1..floor(n/2)} A051731(n-k,k). - _Reinhard Zumkeller_, Nov 01 2009
%F G.f.: 2*Sum_{n>=1} Sum_{d|n} log(1 - x^(n/d))^(2*d) / (2*d)!. - _Paul D. Hanna_, Aug 21 2014
%F Dirichlet g.f.: zeta(s)*(zeta(s)-1). - _Geoffrey Critzer_, Dec 06 2014
%F a(n) = Sum_{k=1..n-1} binomial((n-1) mod k, k-1). - _Wesley Ivan Hurt_, Sep 26 2016
%F a(n) = Sum_{i=1..n-1} floor(n/i)-floor((n-1)/i). - _Wesley Ivan Hurt_, Nov 15 2017
%F a(n) = Sum_{i=1..n-1} 1-sign(i mod (n-i)). - _Wesley Ivan Hurt_, Sep 27 2018
%F 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
%e a(6) = 3 since the proper divisors of 6 are 1, 2, 3.
%p A032741 := proc(n)
%p if n = 0 then
%p 0 ;
%p else
%p numtheory[tau](n)-1 ;
%p end if;
%p end proc: # _R. J. Mathar_, Feb 03 2013
%t Prepend[DivisorSigma[0, Range[99]]-1, 0] (* _Jayanta Basu_, May 25 2013 *)
%o (PARI) a(n) = if(n<1,0,numdiv(n)-1)
%o (PARI) {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
%o (Haskell)
%o a032741 n = if n == 0 then 0 else a000005 n - 1
%o -- _Reinhard Zumkeller_, Jul 31 2014
%o (GAP) Concatenation([0],List([1..100],n->Tau(n)-1)); # _Muniru A Asiru_, Oct 09 2018
%o (Python)
%o from sympy import divisor_count
%o def A032741(n): return divisor_count(n)-1 if n else 0 # _Chai Wah Wu_, Mar 14 2023
%Y Column 2 of A122934.
%Y Cf. A003238, A001065, A027749, A027751 (list of proper divisors).
%Y Cf. A001620, A039653, A051778, A070824, A091818.
%K nonn,easy
%O 0,5
%A _Patrick De Geest_, May 15 1998
%E Typos in definition corrected by _Omar E. Pol_, Dec 13 2008
|
