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

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

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

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

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

Example

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

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 *)

Prog

(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
(PARI) a(n) = n\2 + 1 - numdiv(n); \\ Michel Marcus, Sep 18 2017

Crossrefs

Cf. A000005, A004526, A352620.

Sequence in context: A049823 A143775 A244329 * A337679 A158379 A122838

Adjacent sequences: A003162 A003163 A003164 * A003166 A003167 A003168

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

More terms from Ralf Stephan, Sep 18 2004

Status

approved