A108462 Number of factorizations of (n,n) into pairs (i,j) with i,j >= 1, not both 1.

1, 2, 2, 9, 2, 15, 2, 31, 9, 15, 2, 92, 2, 15, 15, 109, 2, 92, 2, 92, 15, 15, 2, 444, 9, 15, 31, 92, 2, 203, 2, 339, 15, 15, 15, 712, 2, 15, 15, 444, 2, 203, 2, 92, 92, 15, 2, 1903, 9, 92, 15, 92, 2, 444, 15, 444, 15, 15, 2, 1663, 2, 15, 92, 1043, 15, 203, 2, 92, 15, 203, 2

Offset: 1

Author

Christian G. Bower, Jun 03 2005

Keywords

• nonn

Comments

The rule of building products is (a,b)*(x,y) = (a*x,b*y).

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24=2^3*3 and 375=3*5^3 both have prime signature (3,1).

Examples

			From _Alois P. Heinz_ and _Antti Karttunen_, Nov 24 2017: (Start)
a(4) = 9 because for pair (4,4) there are nine factorizations:
  (4,4)
  (1,4)*(4,1)
  (1,2)*(4,2)
  (2,1)*(2,4)
  (2,2)*(2,2)
  (1,2)*(2,1)*(2,2)
  (1,4)*(2,1)*(2,1)
  (4,1)*(1,2)*(1,2)
  (1,2)*(1,2)*(2,1)*(2,1)
(End)
a(pq) = 15 for primes p<>q: (pq,pq); (p,1)(q,pq); (p,1)(q,1)(1,pq); (p,1)(q,1)(1,p)(1,q); (p,1)(q,q)(1,p); (p,1)(q,p)(1,q); (p,q)(q,p); (p,q)(q,1)(1,p); (p,p)(q,q) ; (p,p)(q,1)(1,q); (p,pq)(q,1); (pq,1)(1,pq); (pq,1)(1,p)(1,q); (pq,q)(1,p); (pq,p)(1,q). - _R. J. Mathar_, Nov 30 2017
		

Links

• R. J. Mathar, Table of n, a(n) for n = 1..999
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Main diagonal of A108461.

Cf. A002774, A020557, A108463.

Programs

PARI

a(n) = if(n==1, return(1)); my(b, c, r, x, y, v=List([]), w=List([[n]])); while(#w>r, c++; for(k=r+1, r=#w, y=w[k]; if(!isprime(x=y[c]), fordiv(x, d, if(d!=1&&d!=x, listput(w, concat([y[1..c-1], d, x/d]))))))); for(i=1, #w, x=w[i]; r=#x; for(j=1, #w, y=w[j]; for(k=0, 2^r-1, b=concat(b=binary(k), vector(r-#b)); if(#y>=t=vecsum(b), c=0; listput(v, vecsort(vector(r+#y-t, m, if(m>r, [1, y[m-r+t]], if(b[m], [x[m], y[c++]], [x[m], 1]))))))))); #Set(v); \\ Jinyuan Wang, Jan 17 2022

Formula

a(A025487(n)) = A108463(n).

a(p^k) = A002774(k).

a(A002110(n)) = A020557(n).

a(n) = A108461(n,n).