login
A322437
Number of unordered pairs of factorizations of n into factors > 1 where no factor of one divides any factor of the other.
8
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,120
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)
FORMULA
For n > 0, a(A002110(n)) = A322441(n)/2 = A339626(n). - Antti Karttunen, Dec 10 2020
EXAMPLE
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)
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}]
PROG
(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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 08 2018
EXTENSIONS
Data section extended up to a(120) and more examples added by Antti Karttunen, Dec 10 2020
STATUS
approved