Consider one of the factors q of a square-free factorization; suppose it appears d times. Let the binary expansion of d be 2^a1 + 2^a2 + ... + 2^ak Construct a repetition-free factorization by replacing q*q*q...*q with (q^2^a1)*(q^2^a2)*...*(q^2^ak), and similarly for all other factors. Conversely, any factor of a repetition-free factorization can be uniquely written as q^2^a where q is not a square. Collect all factors with the same non-square q as a base, call them q^2^a1, q^2^a2, ..., q^2^ak. Then the a_i are distinct (since the initial factorization is repetition-free), so let d = a1+a2+...+ak and construct a square-free factorization with d copies of q, and similarly for all other non-square bases that appear. J.P. Grossman On Wed, 14 May 2003, Marc LeBrun wrote:
Call a factorization distinct if there are no repeated factors, and call a factorization square-free if it contains no squares. For all positive integers > 1 I claim the number of each match.
For example of the sixteen factorizations of 72:
A 72 B 8.9 C 6.12 D 4.18 E 3.24 F 3.4.6 G 3.3.8 H 2.36 I 2.6.6 J 2.4.9 K 2.3.12 L 2.3.3.4 M 2.2.18 N 2.2.3.6 O 2.2.2.9 P 2.2.2.3.3
seven (GILMNOP) have repeated factors, and seven (BDFHJLO) contain 4, 9 or 36.
Do you know any citation for this? (Assuming it's in fact true!<;-)
Also, I'd like to see your proofs, to see how they differ from mine.
Particularly interesting would be an explicit construction mapping the factorizations 1-1. (At first I thought this was easy--just split q^2 into q.q--but it's unclear to me what the images of J or P, say, ought to be).
Thanks!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun