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

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

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]

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

Example

{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

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

Prog

(Magma) [(#(PrimeDivisors(n)))+1: n in [1..100]]; // Vincenzo Librandi, Feb 15 2015
(PARI) a(n)=#factor(n)~+1 \\ Charles R Greathouse IV, Sep 14 2015
(Haskell)
a083399 = (+ 1) . a001221  -- Reinhard Zumkeller, Sep 14 2015

Crossrefs

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

Sequence in context: A278293 A163671 A287841 * A105561 A294903 A087133

Adjacent sequences: A083396 A083397 A083398 * A083400 A083401 A083402

Keyword

nonn,easy

Author

Reinhard Zumkeller, Jun 12 2003

Status

approved