%I M0106 #60 Apr 20 2022 09:23:04
%S 0,0,0,0,1,0,2,1,2,2,4,1,5,4,4,4,7,4,8,5,7,8,10,5,10,10,10,9,13,8,14,
%T 11,13,14,14,10,17,16,16,13,19,14,20,17,17,20,22,15,22,20,22,21,25,20,
%U 24,21,25,26,28,19,29,28,26,26,29,26,32,29,31,28,34,25,35,34,32
%N a(n) = floor(n/2) + 1 - d(n), where d(n) is the number of divisors of n.
%C a(n) is the number of partitions of n into exactly two parts whose smallest part is a nondivisor of n (see example). If n is prime, all of the smallest parts (except for 1) are nondivisors of n. Since there are floor(n/2) total partitions of n into two parts, then a(n) = floor(n/2) - 1 for primes (since we exclude 1). Proof: n = p implies a(p) = floor(p/2) + 1 - d(p) = floor(p/2) + 1 - 2 = floor(p/2) - 1. Furthermore, if n is an odd prime, a(n) = (n-3)/2. - _Wesley Ivan Hurt_, Jul 16 2014
%C a(n) is the nullity of the (n-1) X (n-1) matrix M(n) with entries M(n)[i,j] = i*j mod n (matrices given by A352620). - _Luca Onnis_, Mar 27 2022
%D M. Newman, Integral Matrices. Academic Press, NY, 1972, p. 186.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Seiichi Manyama, <a href="/A003165/b003165.txt">Table of n, a(n) for n = 1..10000</a>
%F a(n) = A004526(n) - A000005(n) + 1.
%F a(n) = Sum_{i=1..floor(n/2)} ceiling(n/i) - floor(n/i). - _Wesley Ivan Hurt_, Jul 16 2014
%F a(n) = Sum_{i=1..n} ceiling(n/i) mod floor(n/i). - _Wesley Ivan Hurt_, Sep 15 2017
%F G.f.: x*(1 + x - x^2)/((1 - x)^2*(1 + x)) - Sum_{k>=1} x^k/(1 - x^k). - _Ilya Gutkovskiy_, Sep 18 2017
%F a(n) = Sum_{i=1..floor((n-1)/2)} sign((n-i) mod i). - _Wesley Ivan Hurt_, Nov 17 2017
%e a(20) = 5. The partitions of 20 into exactly two parts are: (19,1), (18,2), (17,3), (16,4), (15,5), (14,6), (13,7), (12,8), (11,9), (10,10). Of these, there are exactly 5 partitions whose smallest part does not divide 20: {3,6,7,8,9}. - _Wesley Ivan Hurt_, Jul 16 2014
%p with(numtheory): A003165:=n->floor(n/2)+1-tau(n): seq(A003165(n), n=1..100); # _Wesley Ivan Hurt_, Jul 16 2014
%t Table[Floor[n/2]+1-DivisorSigma[0,n],{n,80}] (* _Harvey P. Dale_, May 09 2011 *)
%o (Sage)
%o def A003165(n):
%o return sum(1 for k in (1..n//2) if n % k)
%o [A003165(n) for n in (1..75)] # _Peter Luschny_, Jul 16 2014
%o (PARI) a(n) = n\2 + 1 - numdiv(n); \\ _Michel Marcus_, Sep 18 2017
%Y Cf. A000005, A004526, A352620.
%K nonn,easy
%O 1,7
%A _N. J. A. Sloane_
%E More terms from _Ralf Stephan_, Sep 18 2004