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

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

Links

R. J. Mathar, Table of n, a(n) for n = 1..999

Index entries for sequences computed from exponents in factorization of n

Formula

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

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

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

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

Example

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

Prog

(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

Crossrefs

Main diagonal of A108461.

Cf. A002774, A020557, A108463.

Sequence in context: A155936 A377296 A167594 * A327859 A343824 A182106

Adjacent sequences: A108459 A108460 A108461 * A108463 A108464 A108465

Keyword

nonn

Author

Christian G. Bower, Jun 03 2005

Status

approved