A083399 - OEIS

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 (list; graph; refs; listen; history; text; internal format)

	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`
	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.` `Sequence in context: A278293 A163671 A287841 * A105561 A294903 A087133` `Adjacent sequences: A083396 A083397 A083398 * A083400 A083401 A083402`
	KEYWORD	`nonn`
	AUTHOR	`Reinhard Zumkeller, Jun 12 2003`
	STATUS	`approved`