A003165 a(n) = floor(n/2) + 1 - d(n), where d(n) is the number of divisors of n.

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, 11, 13, 14, 14, 10, 17, 16, 16, 13, 19, 14, 20, 17, 17, 20, 22, 15, 22, 20, 22, 21, 25, 20, 24, 21, 25, 26, 28, 19, 29, 28, 26, 26, 29, 26, 32, 29, 31, 28, 34, 25, 35, 34, 32

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

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

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

Examples

			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
		

References

• M. Newman, Integral Matrices. Academic Press, NY, 1972, p. 186.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000005, A004526, A352620.

Programs

Maple

with(numtheory): A003165:=n->floor(n/2)+1-tau(n): seq(A003165(n), n=1..100); # Wesley Ivan Hurt, Jul 16 2014

Mathematica

Table[Floor[n/2]+1-DivisorSigma[0,n],{n,80}] (* Harvey P. Dale, May 09 2011 *)

PARI

a(n) = n\2 + 1 - numdiv(n); \\ Michel Marcus, Sep 18 2017

Sage

def A003165(n):
    return sum(1 for k in (1..n//2) if n % k)
[A003165(n) for n in (1..75)] # Peter Luschny, Jul 16 2014

Formula

a(n) = A004526(n) - A000005(n) + 1.

a(n) = Sum_{i=1..floor(n/2)} ceiling(n/i) - floor(n/i). - Wesley Ivan Hurt, Jul 16 2014

a(n) = Sum_{i=1..n} ceiling(n/i) mod floor(n/i). - Wesley Ivan Hurt, Sep 15 2017

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

a(n) = Sum_{i=1..floor((n-1)/2)} sign((n-i) mod i). - Wesley Ivan Hurt, Nov 17 2017

Extensions

More terms from Ralf Stephan, Sep 18 2004