A322437 Number of unordered pairs of factorizations of n into factors > 1 where no factor of one divides any factor of the other.

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2

Offset: 1

Author

Gus Wiseman, Dec 08 2018

Keywords

• nonn

Comments

First differs from A322438 at a(144) = 3, A322438(144) = 4.

From Antti Karttunen, Dec 11 2020: (Start)

Zeros occur on numbers that are either of the form p^k, or q * p^k, or p*q*r, for some primes p, q, r, and exponent k >= 0. [Note also that in all these cases, when x > 1, A307408(x) = 2+A307409(x) = 2 + (A001222(x) - 1)*A001221(x) = A000005(x)].

Proof:

It is easy to see that for such numbers it is not possible to obtain two such distinct factorizations, that no factor of the other would not divide some factor of the other.

Conversely, the complement set of above is formed of such composites n that have at least one unitary divisor that is either of the form

(1) p^x * q^y, with x, y >= 2,

or

(2) p^x * q^y * r^z, with x >= 2, and y, z >= 1,

or

(3) p^x * q^y * r^z * s^w, with x, y, z, w >= 1,

where p, q, r, s are distinct primes. Let's indicate with C the remaining portion of k coprime to p, q, r and s (which could be also 1). Then in case (1) we can construct two factorizations, the first having factors (p*q*C) and (p^(x-1) * q^(y-1)), and the second having factors (p^x * C) and (q^y) that are guaranteed to satisfy the condition that no factor in the other factorization divides any of the factors of the other factorization. For case (2) pairs like {(p * q^y * C), (p^(x-1) * r^z)} and {(p^x * C), (q^y * r^z)}, and for case (3) pairs like {(p^x * q^y * C), (r^z * s^w)} and {(p^x * r^z * C), (q^y * s^w)} offer similar examples, therefore a(n) > 0 for all such cases.

(End)

Examples

			The a(120) = 2 pairs of such factorizations:
   (6*20)|(8*15)
   (8*15)|(10*12)
The a(144) = 3 pairs of factorizations:
   (6*24)|(9,16)
   (8*18)|(12*12)
   (9*16)|(12*12)
The a(210) = 3 pairs of factorizations:
   (6*35)|(10*21)
   (6*35)|(14*15)
  (10*21)|(14*15)
[Note that 210 is the first squarefree number obtaining nonzero value]
The a(240) = 4 pairs of factorizations:
   (6*40)|(15*16)
   (8*30)|(12*20)
  (10*24)|(15*16)
  (12*20)|(15*16)
The a(1728) = 14 pairs of factorizations:
    (6*6*48)|(27*64)
   (6*12*24)|(27*64)
     (6*288)|(27*64)
    (8*8*27)|(12*12*12)
  (12*12*12)|(27*64)
  (12*12*12)|(32*54)
    (12*144)|(27*64)
    (12*144)|(32*54)
    (16*108)|(24*72)
     (18*96)|(27*64)
     (24*72)|(27*64)
     (24*72)|(32*54)
     (27*64)|(36*48)
     (32*54)|(36*48)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

Cf. A000688, A001055, A285572, A285573, A294068, A303362, A304713, A305149, A305150, A305193, A316476, A317144, A322435, A322436, A322441, A322442, A339626.

Cf. also comments A307408 and A307409.

Programs

Mathematica

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[Subsets[facs[n],{2}],And[!Or@@Divisible@@@Tuples[#],!Or@@Divisible@@@Reverse/@Tuples[#]]&]],{n,100}]

PARI

factorizations(n, m=n, f=List([]), z=List([])) = if(1==n, listput(z,Vec(f)); z, my(newf); fordiv(n, d, if((d>1)&&(d<=m), newf = List(f); listput(newf,d); z = factorizations(n/d, d, newf, z))); (z));
is_ndf_pair(fac1,fac2) = { for(i=1,#fac1,for(j=1,#fac2,if(!(fac1[i]%fac2[j])||!(fac2[j]%fac1[i]),return(0)))); (1); };
number_of_ndfpairs(z) = sum(i=1,#z,sum(j=i+1,#z,is_ndf_pair(z[i],z[j])));
A322437(n) = number_of_ndfpairs(Vec(factorizations(n))); \\ Antti Karttunen, Dec 10 2020

Formula

For n > 0, a(A002110(n)) = A322441(n)/2 = A339626(n). - Antti Karttunen, Dec 10 2020

Extensions

Data section extended up to a(120) and more examples added by Antti Karttunen, Dec 10 2020