A076709 Factors in factorizations of composite numbers into at least 2 factors > 1.

2, 2, 2, 3, 2, 4, 2, 2, 2, 3, 3, 2, 5, 2, 6, 2, 2, 3, 3, 4, 2, 7, 3, 5, 2, 8, 2, 2, 4, 2, 2, 2, 2, 4, 4, 2, 9, 2, 3, 3, 3, 6, 2, 10, 2, 2, 5, 4, 5, 3, 7, 2, 11, 2, 12, 2, 2, 6, 2, 2, 2, 3, 2, 3, 4, 3, 8, 4, 6, 5, 5, 2, 13, 3, 9, 3, 3, 3, 2, 14, 2, 2, 7, 4, 7, 2, 15, 2, 3, 5, 3, 10, 5, 6, 2, 16, 2, 2, 8, 2

Offset: 1

Author

Donald S. McDonald, Oct 26 2002

Keywords

• nonn

Comments

Each factorization is given in nondecreasing order. To determine which of two factorizations a_1 * a_2 * ... * a_r and b_1 * ... * b_s (of the same number) comes first, find the smallest index k such that a_k != b_k. If k=r then the a-factorization comes first. If k=s the b-factorization comes first. Otherwise, if a_k < b_k then the a-factorization comes first; if b_k < a_k the b-factorization comes first.

Examples

			The first 20 terms come from the factorizations of 4, 6, 8, 9, 10 and 12: 4 = 2*2, 6 = 2*3, 8 = 2*4 = 2*2*2, 9 = 3*3, 10 = 2*5, 12 = 2*6 = 2*2*3 = 3*4.
		

Links

• Donald S. McDonald, Posting to sci.math newsgroup, Feb 07 1999

Crossrefs

Cf. A028422, A056472.

Programs

Mathematica

mf[1, ds_] := {{}}; mf[n_, {}] := {}; mf[n_, ds_] := mf[n, ds]=If[Mod[n, ds[[1]]]==0, RotateRight[Join[Prepend[ #, ds[[1]]]&/@mf[n/ds[[1]], ds], RotateLeft[mf[n, Drop[ds, 1]]]]], mf[n, Drop[ds, 1]]]; mf[n_] := mf[n, Drop[Divisors[n], 1]]; Flatten[Drop[mf[ # ], 1]&/@Range[50]]

Extensions

Edited by Dean Hickerson, Dec 06 2002