A083399 - OEIS

%I #58 Sep 29 2024 02:53:53

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

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

%U 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

%N Number of divisors of n that are not divisors of other divisors of n.

%C 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).

%C Number of noncomposite divisors of n, (cf. A008578). - _Jaroslav Krizek_, Nov 25 2009

%C From _Wilf A. Wilson_, Jul 21 2017: (Start)

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

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

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

%C (End)

%C 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

%H Reinhard Zumkeller, <a href="/A083399/b083399.txt">Table of n, a(n) for n = 1..10000</a>

%H James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, <a href="https://arxiv.org/abs/1706.04967">Maximal subsemigroups of finite transformation and partition monoids</a>, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]

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

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

%F a(n) = A000005(n) - A033273(n) + 1. - _Jaroslav Krizek_, Nov 25 2009

%F a(n) = A010553(A007947(n)) = A000005(A000005(A007947(n))) = tau_2(tau_2(rad(n))). - _Enrique Pérez Herrero_, Jun 25 2010

%F G.f.: x/(1 - x) + Sum_{k>=1} x^prime(k)/(1 - x^prime(k)). - _Ilya Gutkovskiy_, Mar 21 2017

%F 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

%e {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.

%e {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

%p A083399 := proc(n)

%p     1+nops(numtheory[factorset](n)) ;

%p end proc:

%p seq(A083399(n),n=1..100) ; # _R. J. Mathar_, Sep 26 2017

%t A083399[n_Integer]:=1+PrimeNu[n]; (* _Enrique Pérez Herrero_, Jun 25 2010 *)

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

%o (Magma) [(#(PrimeDivisors(n)))+1: n in [1..100]]; // _Vincenzo Librandi_, Feb 15 2015

%o (PARI) a(n)=#factor(n)~+1 \\ _Charles R Greathouse IV_, Sep 14 2015

%o (Haskell)

%o a083399 = (+ 1) . a001221  -- _Reinhard Zumkeller_, Sep 14 2015

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

%K nonn,easy

%O 1,2

%A _Reinhard Zumkeller_, Jun 12 2003