|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,120
|
|
|
COMMENTS
|
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)
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
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])));
|
|
|
CROSSREFS
|
Cf. A000688, A001055, A285572, A285573, A294068, A303362, A304713, A305149, A305150, A305193, A316476, A317144, A322435, A322436, A322441, A322442, A339626.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Data section extended up to a(120) and more examples added by Antti Karttunen, Dec 10 2020
|
|
|
STATUS
|
approved
|
| |
|
|
