56! Puzzle

> What values of n! have particular[ly] nice factorizations into n
integers?

See R.K.Guy, "Unsolved Problems in Number Theory", B22;
and Sloane's A034258, A034259.

I rather enjoyed extending 34259. If I remember correctly, I convinced
myself that 56! = 15 x ... is indeed optimal.

--
Don Reble

-------------------------------------------------------------------------------

56! puzzle: write 56! as a product of 56 integers, the smallest as
large as possible.
The greedy strategy -- multiplying each prime by the smallest factors
necessary to raise the product to a certain miminum value, starting
with the largest factors -- can be used in this case to show there is
no solution with a minimum 16. (It can also be used to find solutions
in many cases, but it may not work in every case.)

We are stuck with a number of primes larger than 16: 17^3, 19^2, 23^2,
29, 31, 37, 41, 43, 47, 53. This gives 14 elements of our solution.

Then we have 13^4 and 11^5. These each need an additional factor;
there is no reason to give them anything larger than 2s. Or more
specifically, if we give them anything larger, another valid solution
can be made by swapping it for a 2 which will end up making the other
number which the 2 in it larger, and still leave these large enough.
So we get 26^4 and 22^5 and 9 2s are used, forming a total of 23
factors.

Remaining are 2^44, 3^26, 5^13, 7^9.

Pair each 7 with a 3 to make 21^9. Now 32 factors are formed, 2^44,
3^17, 5^13 remaining.

To have a minimum factor of 16, each 5 must be paired with factors
totalling at least 4. The same rule applies; if you try to "save 2s"
by combining the 5s into 25s, you just end up using those 2s to form
16s, since there are enough 2s that you will end up making 16s anyway.
So we form 20^13 using the 5s and 26 2s. Now 45 factors are formed and
2^18 3^17 remains.

To use up the 3s, the smallest possible number is 18. Make 18^8 using
16 3s and 8 2s. Now 53 factors are formed and 2^10 3^1 remains.

You can now make two 16s leaving 2^2 3^1 for the last factor, which is
only 12. These factors are not large enough to make three 16s. If you
change factors in any other numbers, you will make them larger, with
the side-effect of making the leftovers for the last three factors
smaller.

The posted example solution is identical to this except with the
factors of the 12 and one 20 swapped to make a 15 and a 16. If you
apply the greedy strategy with a goal of minimum 15, you will make 13
15s when you use the 5s, leaving 2^44 3^4, which then make 2 18s and 9
16s, with 8 2s left over to place as you like.

Suggested extension: Solve this problem for other N in place of 56.

The greedy strategy can fail to prove a minimum is not possible and
yet not find a solution if you come down to the end and find a set of
factors which have a product larger than m^k, where m is the desired
minimum and k is the number of integers of at least that minimum, but
which cannot be factored into large enough numbers. For instance,
suppose the minimum is 19 and you end up with 9 2s, needing to make
two numbers. Then 2^9 = 512 which is larger than 19^2 = 361, but the
2s can only be split into 2^4=16 and 2^5=32, where the 16 is too
small. It is not clear that the 2s cannot be used somewhere else,
leaving you with a smaller set of factors at the end which can however
be split into two factors each 19 or larger.

Extension: Find the smallest N where splitting n! into N factors with
the smallest as large as possible by the greedy strategy for some
minimum value fails in this manner. Find the smallest N where the
greedy strategy fails in this way and yet there is actually a solution
for that minimum value.

Joseph DeVincentis

I wrote a program to implement my greedy algorithm for solving this
problem of writing N! as a product of N factors with the smallest as
large as possible. Some thoughts, concepts, etc.:

(1) Once it is proven N! can be solved with a minimum value k, I know
(N+1)! can be solved with minimum value k, simply using N+1 as the new
factor. Recall that my algorithm requires a target minimum value; I
solve the factorials in ascending order using the best solution for
each as the first target for the next and re-try each case, increasing
the target until it fails.

(2) My method does not necessarily find the solution with the fewest
instances of the smallest factor. A solution with two minimum factors
of 15 is arguably better than one with three 15s, but my algorithm may
not always find it. I could modify the algorithm to find it more
often, by making the minimum something like "15, until there are two
15s, then 16", but I haven't done this yet.

(3) I carried the algorithm on until I got enough factors. Sometimes
you end up with some small factors left over; in these cases I simply
took each remaining prime factor and multiplied it by the smallest
factor in the factorization at that point.

(4) As I think about the solidity of this algorithm in general (as
opposed to in the specific case of 56!) I think that there are a
number of ways that it can fail, so that programmatically looking for
holes in the algorithm is not easy. But if anybody wants to try it by
hand, I have provided a lot of targets below.

Here are the solutions I found up to 200! (only the smallest factorial
which was solved with each possible smallest factor are shown). 36,
49, 52, and 53 are not the smallest factors for any factorial.

1! = 1
4! = 2^3 * 3
9! = 3^3 * 4^3 * 5 * 6 * 7
14! = 4^3 * 5^2 * 6^5 * 7^2 * 11 * 13
16! = 5^3 * 6^6 * 7^2 * 8^3 * 11 * 13
20! = 6^8 * 7^2 * 8^2 * 10^4 * 11 * 13 * 17 * 19
24! = 7^3 * 8^6 * 9^5 * 10^4 * 11^2 * 13 * 17 * 19 * 23
27! = 8^4 * 9^6 * 10^6 * 11^2 * 12 * 13^2 * 14^3 * 17 * 19 * 23
32! = 9^7 * 10^7 * 11^2 * 13^2 * 14^4 * 16^5 * 17 * 19 * 23 * 29 * 31
34! = 10^7 * 11^3 * 12^10 * 13^2 * 14^4 * 17^2 * 18 * 19 * 23 * 27 * 29
* 31
38! = 11^3 * 12^9 * 13^2 * 14^5 * 15^8 * 16^3 * 17^2 * 19^2 * 23 * 29 *
31 * 37
40! = 12^9 * 13^3 * 14^5 * 15^9 * 16^3 * 17^2 * 19^2 * 22^3 * 23 * 29 *
31 * 37
46! = 13^3 * 14^6 * 15^10 * 16^6 * 17^2 * 18^5 * 19^2 * 22^4 * 23^2 *
24 * 29 * 31 * 37 * 41 * 43
49! = 14^7 * 15^10 * 16^6 * 17^2 * 18^6 * 19^2 * 22^4 * 23^2 * 26^3 *
28 * 29 * 31 * 37 * 41 * 43 * 47
51! = 15^12 * 16^9 * 17^3 * 18 * 19^2 * 21^8 * 22^4 * 23^2 * 24 * 26^3
* 29 * 31 * 37 * 41 * 43 * 47
57! = 16 * 17^3 * 18^9 * 19^3 * 20^13 * 21^9 * 22^5 * 23^2 * 26^4 * 29
* 31 * 32 * 37 * 41 * 43 * 47 * 53
58! = 17^3 * 18^9 * 19^3 * 20^13 * 21^9 * 22^5 * 23^2 * 26^4 * 29^2 *
31 * 32^2 * 37 * 41 * 43 * 47 * 53
62! = 18^9 * 19^3 * 20^14 * 21^9 * 22^5 * 23^2 * 24 * 26^4 * 29^2 *
31^2 * 32 * 34^3 * 37 * 41 * 43 * 47 * 53 * 59 * 61
65! = 19^3 * 20^15 * 21^10 * 22^5 * 23^2 * 24^6 * 26^5 * 27^4 * 29^2 *
31^2 * 34^3 * 36 * 37 * 41 * 43 * 47 * 53 * 59 * 61
68! = 20^15 * 21^10 * 22^6 * 23^2 * 24^6 * 26^5 * 27^5 * 29^2 * 31^2 *
34^4 * 37 * 38^3 * 41 * 43 * 47 * 53 * 59 * 61 * 67
72! = 21^10 * 22^6 * 23^3 * 24^17 * 25^8 * 26^5 * 27^2 * 29^2 * 31^2 *
34^4 * 37 * 38^3 * 41 * 42 * 43 * 47 * 53 * 59 * 61 * 67 * 71
77! = 22^7 * 23^3 * 24^9 * 25^9 * 26^5 * 27^8 * 28^12 * 29^2 * 31^2 *
34^4 * 36 * 37^2 * 38^4 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73
80! = 23^3 * 24^13 * 25^9 * 26^6 * 27^5 * 28^12 * 29^2 * 30 * 31^2 *
33^7 * 34^4 * 37^2 * 38^4 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73
* 79
84! = 24^11 * 25^9 * 26^6 * 27^7 * 28^13 * 29^2 * 30 * 31^2 * 33^7 *
34^4 * 37^2 * 38^4 * 41^2 * 43 * 46^3 * 47 * 48 * 53 * 59 * 61 * 67 *
71 * 73 * 79 * 83
87! = 25^9 * 26^6 * 27^11 * 28^13 * 29^3 * 31^2 * 32^7 * 33^7 * 34^5 *
36 * 37^2 * 38^4 * 41^2 * 43^2 * 46^3 * 47 * 50 * 53 * 59 * 61 * 67 *
71 * 73 * 79 * 83
90! = 26^5 * 27^5 * 28^13 * 29^3 * 30^21 * 31^2 * 32^4 * 33^8 * 34^5 *
37^2 * 38^4 * 41^2 * 43^2 * 46^3 * 47 * 52 * 53 * 59 * 61 * 67 * 71 *
73 * 79 * 83 * 89
93! = 27^2 * 28^14 * 29^3 * 30^21 * 31^3 * 32^5 * 33^8 * 34^5 * 37^2 *
38^4 * 39^7 * 41^2 * 43^2 * 46^4 * 47 * 53 * 54 * 59 * 61 * 67 * 71 *
73 * 79 * 83 * 89
94! = 28^14 * 29^3 * 30^21 * 31^3 * 32^3 * 33^8 * 34^5 * 36^4 * 37^2 *
38^4 * 39^7 * 41^2 * 43^2 * 46^4 * 47^2 * 48 * 53 * 59 * 61 * 67 * 71
* 73 * 79 * 83 * 89
100! = 29^2 * 30^8 * 31^3 * 32^10 * 33^9 * 34^5 * 35^16 * 36^12 * 37^2
* 38^5 * 39^7 * 41^2 * 43^2 * 46^4 * 47^2 * 53 * 58 * 59 * 61 * 67 *
71 * 73 * 79 * 83 * 89 * 97
104! = 30^7 * 31^3 * 32^10 * 33^9 * 34^6 * 35^16 * 36^12 * 37^2 * 38^5
* 39^8 * 41^2 * 43^2 * 46^4 * 47^2 * 53 * 58^3 * 59 * 60 * 61 * 67 *
71 * 73 * 79 * 83 * 89 * 97 * 101 * 103
108! = 31^2 * 32^5 * 33^9 * 34^6 * 35^17 * 36^18 * 37^2 * 38^5 * 39^8
* 40^8 * 41^2 * 43^2 * 46^4 * 47^2 * 53^2 * 58^3 * 59 * 61 * 62 * 67 *
71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107
111! = 32^3 * 33^10 * 34^6 * 35^17 * 36^18 * 37^3 * 38^5 * 39^8 * 40^9
* 41^2 * 43^2 * 46^4 * 47^2 * 53^2 * 58^3 * 59 * 61 * 62^3 * 64 * 67 *
71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109
114! = 33^10 * 34^6 * 35^18 * 36^18 * 37^3 * 38^6 * 39^8 * 40^8 * 41^2
* 43^2 * 46^4 * 47^2 * 48 * 53^2 * 58^3 * 59 * 61 * 62^3 * 64^4 * 67 *
71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113
116! = 34^6 * 35^18 * 36^20 * 37^3 * 38^6 * 39^8 * 40^9 * 41^2 * 43^2
* 44^10 * 46^5 * 47^2 * 53^2 * 54 * 58^4 * 59 * 61 * 62^3 * 67 * 71 *
73 * 79 * 81 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113
118! = 35^18 * 36^21 * 37^3 * 38^6 * 39^9 * 40^9 * 41^2 * 43^2 * 44^10
* 46^5 * 47^2 * 51^6 * 53^2 * 58^4 * 59^2 * 61 * 62^3 * 64 * 67 * 71 *
73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113
125! = 37^3 * 38^6 * 39^9 * 40^19 * 41^3 * 42^19 * 43^2 * 44^12 *
45^12 * 46^5 * 47^2 * 51^7 * 53^2 * 58^4 * 59^2 * 61^2 * 62^4 * 67 *
71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113
128! = 38^6 * 39^9 * 40^20 * 41^3 * 42^20 * 43^2 * 44^12 * 45^11 *
46^5 * 47^2 * 51^7 * 53^2 * 54 * 58^4 * 59^2 * 61^2 * 62^4 * 67 * 71 *
73 * 74^3 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127
130! = 39^10 * 40^22 * 41^3 * 42^20 * 43^3 * 44^12 * 45^9 * 46^5 *
47^2 * 51^7 * 53^2 * 57^6 * 58^4 * 59^2 * 60 * 61^2 * 62^4 * 67 * 71 *
73 * 74^3 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127
135! = 40^16 * 41^3 * 42^21 * 43^3 * 44^13 * 45^15 * 46^5 * 47^2 *
51^7 * 52^10 * 53^2 * 57^7 * 58^4 * 59^2 * 61^2 * 62^4 * 67^2 * 71 *
73 * 74^3 * 75 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127
* 131
142! = 41^3 * 42^22 * 43^3 * 44^13 * 45^15 * 46^6 * 47^3 * 50^9 * 51^8
* 52^10 * 53^2 * 57^7 * 58^4 * 59^2 * 60 * 61^2 * 62^4 * 64^7 * 67^2 *
71^2 * 73 * 74^3 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 *
127 * 131 * 137 * 139
144! = 42^21 * 43^3 * 44^14 * 45^16 * 46^6 * 47^3 * 48 * 50^9 * 51^8 *
52^11 * 53^2 * 57^7 * 58^4 * 59^2 * 61^2 * 62^4 * 64^6 * 67^2 * 71^2 *
73 * 74^3 * 79 * 82^3 * 83 * 84 * 89 * 97 * 101 * 103 * 107 * 109 *
113 * 127 * 131 * 137 * 139
148! = 43^3 * 44^14 * 45^28 * 46^6 * 47^3 * 49^12 * 50^3 * 51^8 *
52^11 * 53^2 * 57^7 * 58^5 * 59^2 * 61^2 * 62^4 * 64^11 * 67^2 * 71^2
* 73^2 * 74^4 * 79 * 80 * 82^3 * 83 * 89 * 97 * 101 * 103 * 107 * 109
* 113 * 127 * 131 * 137 * 139
152! = 44^14 * 45^28 * 46^6 * 47^3 * 49^12 * 50^4 * 51^8 * 52^11 *
53^2 * 57^8 * 58^5 * 59^2 * 61^2 * 62^4 * 64^11 * 67^2 * 71^2 * 73^2 *
74^4 * 79 * 80 * 82^3 * 83 * 86^3 * 89 * 97 * 101 * 103 * 107 * 109 *
113 * 127 * 131 * 137 * 139 * 149 * 151
154! = 45^22 * 46^6 * 47^3 * 48^13 * 49^12 * 51^9 * 52^11 * 53^2 *
55^15 * 56 * 57^8 * 58^5 * 59^2 * 61^2 * 62^4 * 64^8 * 67^2 * 71^2 *
73^2 * 74^4 * 79 * 82^3 * 83 * 86^3 * 89 * 97 * 101 * 103 * 107 * 109
* 113 * 127 * 131 * 137 * 139 * 149 * 151
159! = 46^6 * 47^3 * 48^21 * 49^12 * 50^11 * 51^9 * 52^12 * 53^3 *
54^3 * 55^15 * 56 * 57^8 * 58^5 * 59^2 * 60 * 61^2 * 62^5 * 67^2 *
71^2 * 73^2 * 74^4 * 79^2 * 81^7 * 82^3 * 83 * 86^3 * 89 * 97 * 101 *
103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157
160! = 47^3 * 48^24 * 49^12 * 50^12 * 51^9 * 52^12 * 53^3 * 54^3 *
55^15 * 56 * 57^8 * 58^5 * 59^2 * 61^2 * 62^5 * 67^2 * 69^6 * 71^2 *
73^2 * 74^4 * 79^2 * 81^5 * 82^3 * 83 * 86^3 * 89 * 97 * 101 * 103 *
107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157
164! = 48^25 * 49^13 * 50^12 * 51^9 * 52^12 * 53^3 * 54 * 55^15 * 57^8
* 58^5 * 59^2 * 61^2 * 62^5 * 67^2 * 69^7 * 71^2 * 73^2 * 74^4 * 79^2
* 81^7 * 82^4 * 83 * 86^3 * 89 * 94^3 * 97 * 101 * 103 * 107 * 109 *
113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163
168! = 50^12 * 51^9 * 52^12 * 53^3 * 54^19 * 55^16 * 56^27 * 57^8 *
58^5 * 59^2 * 61^2 * 62^5 * 67^2 * 69^7 * 71^2 * 73^2 * 74^4 * 79^2 *
82^4 * 83^2 * 86^3 * 89 * 94^3 * 96 * 97 * 101 * 103 * 107 * 109 * 113
* 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167
176! = 51^10 * 52^14 * 53^3 * 55^17 * 56^28 * 57^9 * 58^6 * 59^2 *
60^17 * 61^2 * 62^5 * 67^2 * 69^7 * 71^2 * 73^2 * 74^4 * 75^4 * 79^2 *
81^9 * 82^4 * 83^2 * 86^4 * 89 * 90 * 94^3 * 97 * 101 * 103 * 107 *
109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173
183! = 54^15 * 55^17 * 56^29 * 57^9 * 58^6 * 59^3 * 60^12 * 61^3 *
62^5 * 65^15 * 67^2 * 68^10 * 69^7 * 71^2 * 73^2 * 74^4 * 79^2 * 81^2
* 82^4 * 83^2 * 86^4 * 89^2 * 94^3 * 97 * 101 * 103 * 106^3 * 107 *
109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 162^2 * 163 *
167 * 173 * 179 * 181
187! = 55^18 * 56^29 * 57^9 * 58^6 * 59^3 * 60^12 * 61^3 * 62^6 *
65^15 * 67^2 * 68^11 * 69^8 * 71^2 * 72^5 * 73^2 * 74^5 * 79^2 * 81^12
* 82^4 * 83^2 * 86^4 * 89^2 * 94^3 * 97 * 101 * 103 * 106^3 * 107 *
108 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167
* 173 * 179 * 181
190! = 56^30 * 57^10 * 58^6 * 59^3 * 60^11 * 61^3 * 62^6 * 65^15 *
66^18 * 67^2 * 68^11 * 69^8 * 71^2 * 73^2 * 74^5 * 75^10 * 79^2 * 81^9
* 82^4 * 83^2 * 86^4 * 89^2 * 94^4 * 97 * 101 * 103 * 106^3 * 107 *
109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173
* 179 * 181

Joseph DeVincentis

-----------------------------------------------------------------------------------

There is no expression of 56! as the product of 56 integers
all of which are at least 16.

Given integer n and prime p, write d(n,p) for the degree to
which p divides n. ie d(n,p)=k if p^k is a factor of n, but
p^(k+1) is not.

Claim: If n>=16 and 56! is a multiple of n, then 2d(n,2)
+3d(n,3)+4d(n,5)+5d(n,7)+6d(n,11)+6d(n,13) +8d(n,17)
+8d(n,19)+8d(n,23)+8d(n,29)+8d(n,31)+8d(n,37)+8d(n,41)+
8d(n,43)+8d(n,47)+8d(n,53)>=8.

Proof: If n is divisible by any prime above 53, it is not a
factor of 56!. If it is divisible by any prime p above 17,
the term 8d(n,p) is at least 8, and therefore the whole sum
from the claim is at least 8. If it is divisible by 11 or
13, then since it is not equal to 11 or 13 (being at least
16), there must be some other prime factor, and the sum in
the claim is at least 8. Then we are left to check, for all
a,b,c,d with 2a+3b+4c+5d<8, 2^a*3^b*5^c*7^d<16. The reader
can do this. QED

Corollary: 56! is not the product of 56 integers, all
greater than 15.

Proof: Suppose 56!=a_1...a_56, with a_i>15. Then for all p,
d(56!,p)=\Sigma_i d(a_i,p). Therefore, 2d(56!,2)+3d(56!,3)
+... (the sum from the claim) =\Sigma_i 2d(a_i,2)+3d(a_i,3)
+...

Now each element of the right hand side sum, (being as a_i
is a factor of 56! and at least 16), is at least 8.
Therefore the right hand side is at least 8*56=448. The
left hand side is 447. QED

If we denote the sum from the claim by q(n), then we have
q(56!)=447=q(a_1)+q(a_2)+...+q(a_56).

Since q(15)=7, this means that if a_1=15<a_2,a_3,...,a_56,
then q(a_2)=q(a_3)=...=8. By inspection, we can find that
the values of n with n|56!, n>15 and q(n)=8 are
{16,17,18,19,20,21,22,23,25,26,29,31,37,41,43,47,53}.

The only multiple of 7 is 21. Thus 21 must occur 9 times.
Similarly (considering 11), 22 must occur 5 times. 26 must
occur 4 times, 17 3 times, 19 and 23 2 times each, and
29,31,37,41,43,47,53 must occur 1 time each. Therefore 33 of
the numbers are
15*17^3*19^2*21^9*22^5*23^2*26^4*29*31*37*41*43*47*53

We are left with 16 powers of 3 to get, and the only
remaining multiple of 3 is 18. Therefore we must have 18^8
in there as well.

The remaining 56-(1+3+2+9+5+2+4+1+1+1+1+1+1+1+8)=15 numbers
must multiply to give 2^36*5^12, and must come from
{16,20,25}={2^4,2^2*5,5^2}.

Therefore it must be 16^a*20^b*25^c, where 4a+2b=36, b+2c=12
and a+b+c=15. There are 6 possible solutions, a=9-k, b=2k,
c=6-k, where 0<=k<=6. The one that is last in the colex
order we are looking at, is the one you give on the page.
But you probably knew that.

To show the power of this method, I have also shown that if you express
100! as the product of 100 integers, the smallest has to be at most 29:

Let q(n)=2*d(n,2)+3*d(n,3)+5*d(n,5)+5*d(n,7)+7*d(n,11)+7*d(n,13)

+8*d(n,17)+8*d(n,19)+8*d(n,23)+8*d(n,29)+10*d(n,31)+10*d(n,37)
+...+10*d(n,all primes over 29)
Where d(n,p) is the power to which p appears in n.

Then: (i) q(a_1a_2...a_k)=q(a_1)+q(a_2)+...+q(a_k).
(ii) q(100!)=996

Therefore if 100!=a_1a_2...a_{100}, there exists some a_i with
q(a_i)<10. If q(a_i)<10, then a_i<30.

q(29)=8, so any expression with 29 as the smallest integer must have at
least an exponent of 2 on the 29. In any such, all the other integers must be
factors f of 100! with q(f)=10. Therefore they must be from the set
{30,31,32,33,34,35,36,37,38,39,41,42,43,46,47,49,53,58,59,
61,67,71,73,79,83,89,97}

Since 33 is the only multiple of 11, and 11 appears 9 times in 100!,
33^9 must appear. Similarly, we can see that

29^2*31^3*33^9*34^5*37^2*38^5*39^7*41^2*43^2*46^4*47^2*53*58*59*61*
67*71*73*79*83*89*97

This leaves us trying to make
2^82*3^32*5^24*7^16
out of 46 numbers, chosen from {2*3*5,2^5,5*7,2^2*3^2,2*3*7,7^2}.
Suppose we take a,b,c,d,e,f of these respectively.
We have 5 equations:
a+b+c+d+e+f=46
a+5b+2d+e=82
a+2d+e=32
a+c=24
c+e+2f=16

Solving in terms of e,f gives us a=e+2f+8, b=10, c=16-(e+2f),
d=12-(e+f).
We are interested in minimising a, so we make e=f=0, and we get

100!=29^2*30^8*31^3*32^10*33^9*34^5*35^16*36^12*37^2*38^5*39^7*41^2*43^2
*46^4*47^2*53*58*59*61*67*71*73*79*83*89*97.

1000!=
312^8*313^3*314^6*315^99*316^12*317^3*318^18*319^35*320^62*321^9*322^44*
323^54*324^23*325^5*326^6*327^9*328^24*329^21*330^30*331^3*332^12*333^27*
334^5*335^14*337^2*338^34*339^8*340^7*341^33*344^23*346^5*347^2*349^2*
353^2*354^16*355^14*356^11*358^5*359^2*362^5*365^13*366^16*367^2*373^2*
379^2*381^7*382^5*383^2*386^5*388^10*389^2*393^7*394^5*397^2*398^5*401^2*
404^9*409^2*411^7*412^9*417^7*419^2*421^2*422^4*431^2*433^2*439^2*443^2*
446^4*447^6*449^2*453^6*454^4*457^2*458^4*461^2*463^2*466^4*467^2*478^4*
479^2*482^4*487^2*491^2*499^2*502^3*503^1*509^1*514^3*521^1*523^1*526^3*
538^3*541^1*542^3*547^1*554^3*557^1*562^3*563^1*566^3*569^1*571^1*577^1*
586^3*587^1*593^1*599^1*601^1*607^1*613^1*614^3*617^1*619^1*622^3*631^1*
641^1*643^1*647^1*653^1*659^1*661^1*673^1*677^1*683^1*691^1*701^1*709^1*
719^1*727^1*733^1*739^1*743^1*751^1*757^1*761^1*769^1*773^1*787^1*797^1*
809^1*811^1*821^1*823^1*827^1*829^1*839^1*853^1*857^1*859^1*863^1*877^1*
881^1*883^1*887^1*907^1*911^1*919^1*929^1*937^1*941^1*947^1*953^1*967^1*
971^1*977^1*983^1*991^1*997^1

Luke Pebody