login
Number of divisors of n^n, or of A000312(n).
28

%I #54 Jun 06 2024 19:16:12

%S 1,1,3,4,9,6,49,8,25,19,121,12,325,14,225,256,65,18,703,20,861,484,

%T 529,24,1825,51,729,82,1653,30,29791,32,161,1156,1225,1296,5329,38,

%U 1521,1600,4961,42,79507,44,4005,4186,2209,48,9457,99,5151,2704,5565,54

%N Number of divisors of n^n, or of A000312(n).

%C From _Gus Wiseman_, May 02 2021: (Start)

%C Conjecture: The number of divisors of n^n equals the number of pairwise coprime ordered n-tuples of divisors of n. Confirmed up to n = 30. For example, the a(1) = 1 through a(5) = 6 tuples are:

%C (1) (1,1) (1,1,1) (1,1,1,1) (1,1,1,1,1)

%C (1,2) (1,1,3) (1,1,1,2) (1,1,1,1,5)

%C (2,1) (1,3,1) (1,1,1,4) (1,1,1,5,1)

%C (3,1,1) (1,1,2,1) (1,1,5,1,1)

%C (1,1,4,1) (1,5,1,1,1)

%C (1,2,1,1) (5,1,1,1,1)

%C (1,4,1,1)

%C (2,1,1,1)

%C (4,1,1,1)

%C The unordered case (pairwise coprime n-multisets of divisors of n) is counted by A343654.

%C (End)

%H Seiichi Manyama, <a href="/A062319/b062319.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from Harry J. Smith)

%F a(n) = A000005(A000312(n)). - _Enrique Pérez Herrero_, Nov 09 2010

%F a(2^n) = A002064(n). - _Gus Wiseman_, May 02 2021

%F a(prime(n)) = prime(n) + 1. - _Gus Wiseman_, May 02 2021

%F a(n) = Product_{i=1..s} (1 + n * m_i) where (m_1,...,m_s) is the sequence of prime multiplicities (prime signature) of n. - _Gus Wiseman_, May 02 2021

%F a(n) = Sum_{d|n} n^omega(d) for n > 0. - _Seiichi Manyama_ May 12 2021

%e From _Gus Wiseman_, May 02 2021: (Start)

%e The a(1) = 1 through a(5) = 6 divisors:

%e 1 1 1 1 1

%e 2 3 2 5

%e 4 9 4 25

%e 27 8 125

%e 16 625

%e 32 3125

%e 64

%e 128

%e 256

%e (End)

%t A062319[n_IntegerQ]:=DivisorSigma[0,n^n]; (* _Enrique Pérez Herrero_, Nov 09 2010 *)

%t Join[{1},DivisorSigma[0,#^#]&/@Range[60]] (* _Harvey P. Dale_, Jun 06 2024 *)

%o (PARI) je=[]; for(n=0,200,je=concat(je,numdiv(n^n))); je

%o (PARI) { for (n=0, 1000, write("b062319.txt", n, " ", numdiv(n^n)); ) } \\ _Harry J. Smith_, Aug 04 2009

%o (PARI) a(n)=local(fm);fm=factor(n);prod(k=1,matsize(fm)[1],fm[k,2]*n+1) \\ _Franklin T. Adams-Watters_, May 03 2011

%o (PARI) a(n) = if(n==0, 1, sumdiv(n, d, n^omega(d))); \\ _Seiichi Manyama_, May 12 2021

%o (Magma) [NumberOfDivisors(n^n): n in [0..60]]; // _Vincenzo Librandi_, Nov 09 2014

%o (Python 3.8+)

%o from math import prod

%o from sympy import factorint

%o def A062319(n): return prod(n*d+1 for d in factorint(n).values()) # _Chai Wah Wu_, Jun 03 2021

%Y Cf. A046798, A077592, A035116. - _Enrique Pérez Herrero_, Nov 09 2010

%Y Number of divisors of A000312(n).

%Y Taking Omega instead of sigma gives A066959.

%Y Positions of squares are A173339.

%Y Diagonal n = k of the array A343656.

%Y A000005 counts divisors.

%Y A059481 counts k-multisets of elements of {1..n}.

%Y A334997 counts length-k strict chains of divisors of n.

%Y A343658 counts k-multisets of divisors.

%Y Pairwise coprimality:

%Y - A018892 counts coprime pairs of divisors.

%Y - A084422 counts pairwise coprime subsets of {1..n}.

%Y - A100565 counts pairwise coprime triples of divisors.

%Y - A225520 counts pairwise coprime sets of divisors.

%Y - A343652 counts maximal pairwise coprime sets of divisors.

%Y - A343653 counts pairwise coprime non-singleton sets of divisors > 1.

%Y - A343654 counts pairwise coprime sets of divisors > 1.

%Y Cf. A000169, A000272, A002064, A002109, A009998, A048691, A143773, A146291, A176029, A327527, A343657.

%K easy,nonn

%O 0,3

%A _Jason Earls_, Jul 05 2001