A083399 Number of divisors of n that are not divisors of other divisors of n.

1, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 3, 2, 2, 3, 2, 3, 3, 3, 2, 3, 2, 3, 2, 3, 2, 4, 2, 2, 3, 3, 3, 3, 2, 3, 3, 3, 2, 4, 2, 3, 3, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 3, 2, 4, 2, 3, 3, 2, 3, 4, 2, 3, 3, 4, 2, 3, 2, 3, 3, 3, 3, 4, 2, 3, 2, 3, 2, 4, 3, 3, 3, 3, 2, 4, 3, 3, 3, 3, 3, 3, 2, 3, 3, 3, 2, 4

Offset: 1

Author

Reinhard Zumkeller, Jun 12 2003

Keywords

• nonn
• easy

Comments

a(n) <= tau(n); a(n) = tau(n) iff n is prime or n=1 (A008578, A000040); a(n)=tau(n)-1 iff n is semiprime (A001358).

Number of noncomposite divisors of n, (cf. A008578). - Jaroslav Krizek, Nov 25 2009

From Wilf A. Wilson, Jul 21 2017: (Start)

a(n) is the number of maximal subsemigroups of the annular Jones monoid of degree n.

a(n) is the number of maximal subsemigroups of the monoid of orientation-preserving mappings on a set with n elements.

a(n) + 1 is the number of maximal subsemigroups of the monoid of orientation-preserving partial mappings on a set with n elements.

(End)

This is the restricted growth sequence transform of A001221 (and thus also of A007875, A034444, A082476, A292586 and many other sequences). This follows from the formula a(n) = 1+A001221(n), and from the fact that for any n, A001221(n) <= 1+A001221(k) for all k = 1..(n-1). A067003 gives the ordinal transform of A001221. See also A292582, A292583, A292585. - Antti Karttunen, Sep 25 2017

Examples

			{1,2,3,4,6,8,12,24} are the divisors of n=24: 1, 2, 3, 4 and 6 divide not only 24, but also 8 or 12, therefore a(24) = 3.
{1,2,3,4,6,8,12,24} are the divisors of n=24: 1, 2 and 3 are noncomposites, therefore a(24) = 3. - _Jaroslav Krizek_, Nov 25 2009
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]

Crossrefs

Cf. A000005, A001221, A067003, A055212, A077761.

Programs

Haskell

a083399 = (+ 1) . a001221  -- Reinhard Zumkeller, Sep 14 2015

Magma

[(#(PrimeDivisors(n)))+1: n in [1..100]]; // Vincenzo Librandi, Feb 15 2015

Maple

A083399 := proc(n)
    1+nops(numtheory[factorset](n)) ;
end proc:
seq(A083399(n),n=1..100) ; # R. J. Mathar, Sep 26 2017

Mathematica

A083399[n_Integer]:=1+PrimeNu[n]; (* Enrique Pérez Herrero, Jun 25 2010 *)
Rest@ CoefficientList[ Series[(1/(1 - x)) + Sum[1/(1 - x^Prime[j]), {j, 200}], {x, 0, 111}], x] (* Robert G. Wilson v, Aug 16 2011 *)

PARI

a(n)=#factor(n)~+1 \\ Charles R Greathouse IV, Sep 14 2015

Formula

a(n) = omega(n) + 1, where omega = A001221.

a(n) = tau(n) - A055212(n) = A000005(n)-A055212(n).

a(n) = A000005(n) - A033273(n) + 1. - Jaroslav Krizek, Nov 25 2009

a(n) = A010553(A007947(n)) = A000005(A000005(A007947(n))) = tau_2(tau_2(rad(n))). - Enrique Pérez Herrero, Jun 25 2010

G.f.: x/(1 - x) + Sum_{k>=1} x^prime(k)/(1 - x^prime(k)). - Ilya Gutkovskiy, Mar 21 2017

Sum_{k=1..n} a(k) = n * (log(log(n)) + B + 1) + O(n/log(n)), where B is Mertens's constant (A077761). - Amiram Eldar, Sep 29 2024